RACINE CARRÉE ENTIÈRE racine, carré, cubique, entier, Source N°46994 Delphi

Information sur la source

Catégorie :Maths Classé sous : racine, carré, cubique, entier Niveau : Débutant Date de création : 14/06/2008 Vu : 2 659

Auteur : barbichette

Site perso

Ecrire un message privé

Note :

10,00 / 10

1
2
3
4
5
6
7
8
9
10

Commentaire sur cette source (7)

Ajouter un commentaire et/ou une note

Description

Rien de révolutionnaire ici.
Cette petite fonction recherche la racine carré (ou la racine cubique pour isqrt3) d'un entier en retournant un entier tronqué.

La fonction est peut-être plus lente que l'algorithme d'un gars que j'ai oublié le nom (Thalès, Héron, Pythagore???....), mais elle ne dépend pas de la grandeur du nombre à calculer.
Dans ce dernier algorithme, il faut faire des itérations jusqu'à ce que les deux valeurs successives diffères de 1. Un petit problème déjà est de savoir quel résultat il faut prendre.

Pour mon algo, c'est autre chose...

Si ont regarde la liste des racine, ça donne ça :
0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4...
on vois qu'il y a des répétitions et que
0 se répète 1 fois
1 se répète 3 fois
2 se répète 5 fois
3 se répète 7 fois
...
OOOOH!!!.... les nombres impaires dans l'ordre.
le chiffre p va donc se répéter p*2+1 fois.

Enfin, pour la boucle, on va regarder où ce trouve n dans la liste.
Est-il dans les 3 premier, 5 suivant, 7 suivant.....
En gros,
- si il est dans les 2p+1 premiers, c'est que sa racine est p
- sinon, on lui retranche 2p+1 et un avance d'un rang.
Ou encore,

=====================

Pour la racine cubique, c'est un peut plus compliqué...
mais c'est le même principe, la suite est celle des nombres hexagonaux centrés...
soit 1-7-19-37-61
la forulaire est donc au rang N -> 1+3*N*(N+1)

Source

function isqrt(n:integer):integer;
begin
result:=1;
while n>result*2+1 do begin n:=n-(result*2+1); inc(result); end;
end;
//================================
function isqrt3(n:integer):integer;
begin
result:=1;
while n>1+3*result*(result+1) do begin n:=n-(1+3*result*(result+1)); inc(result); end;
end;

function isqrt(n:integer):integer;
 begin
  result:=1;
  while n>result*2+1 do begin n:=n-(result*2+1); inc(result); end;
 end;

//================================

function isqrt3(n:integer):integer;
 begin
  result:=1;
  while n>1+3*result*(result+1) do begin n:=n-(1+3*result*(result+1)); inc(result); end;
 end;

Conclusion

- Ca ne marche que pour n > 0 (<<strictement>>)

- Ne cherchez pas à optimiser le fait qu'il y a deux calcul de (result*2+1) car le compilateur, en passant en code en assembleur, ne le calcul qu'une fois...
C'est magique...

- Il doit surement exister la même chose pour la racine quatrième ou autre... mais bon...

Sources du même auteur

ÉCRAN DE VEILLE FEU D'ARTIFICE

MESSAGE EN FEU D'ARTIFICE

ENCORE LOUPÉ

JEU LOGICOLOR

ENTRÉES SORTIES WAVE ET MIDI

Toutes les sources de barbichette

Sources de la même categorie

GÉNÉRATEUR DE NOMBRES PSEUDO-ALÉATOIRES par Bacterius

ALGORITHME DE HASH LEA-128 par Bacterius

STATUTILS - LES STATISTIQUES par Bacterius

CALCULATRICE POUR POËTES par fredelem

CALCULATRICE AVEC RADIOBUTTON par paix144

Toutes les sources de la catégorie Maths

Sources en rapport avec celle ci

MÉTHODE DICHOTOMIQUE : CALCUL DE RACINE CUBIQUE par bad_dark_spirit

MÉTHODE DE NEWTON : CALCUL D'UNE RACINE CARRÉE par bad_dark_spirit

CONVERSION LITTÉRALE D' 1 NOMBRE EN PORTUGAIS par MAURICIO

LES NEUFS CARRÉS MAGIQUES par hoby500

ENTIERS DE TAILLE ILLIMITÉ par RedDevlopper

Commentaires et avis

Commentaire de f0xi le 14/06/2008 10:26:00 administrateur CS

He ben ma barbichette, ... tu sais que ton code devrais etre sur Codyx et pas ici :)

bon, j'ai rien vus cette fois * favoritisme * :D

Commentaire de jackalunion le 25/06/2008 19:07:56 10/10

Trés bonne astuce amigo trés bonne

Commentaire de pseudo3 le 30/09/2008 16:13:12

Salut,

A propos de RacineCarrée(N) : En utilisant l'algo de Héron d'Alexandrie ou de Newton qui converge déjà relativent vite en l'amorçant avec une valeur approchée Xo = N/2 il est possible de multiplier par K sa vitesse de convergence en l'amorçant avec une valeur beaucoup plus proche du résultat sachant que si N est un nombre de NC chiffres avec NC > 1 alors RacineCarrée(N)
est un nombre de "NC div 2 chiffres" si NC est pair et de "(NC + 1) div 2 chiffres" lorsque NC est impair ...
Donc si N = XYZTUV alors Xo compris statistiquement entre 100 et 999 et pour simplifier on prend Xo = 555 dans le cas d'un N avec 6 chiffres.
(Pour NC = 1 on se contente de Xo = N div 2)

Exemples de résultats :
- RacineCarrée(999999999) obtenu en 5 tours de boucle au lieu de 18 soit un facteur d'accéllération de 3,6
- RacineCarrée(9111111111111111111) en 6 tours au lieu de 35 soit un facteur d'accéllération de 5,8
<-- ici N est proche de limite des Int64.
- RacineCarrée(99999999999999999999999999999999999999999) (NC = 41) obtenu en 7 intérations au lieu de 73 soit un facteur d'accéllération de 10 (Result = 316227766016837933199).

A+

Commentaire de pseudo3 le 30/09/2008 16:19:16

Salut,

A propos de RacineCarrée(N) : En utilisant l'algo de Héron d'Alexandrie ou de Newton qui converge déjà relativent vite en l'amorçant avec une valeur approchée Xo = N/2 il est possible de multiplier par K sa vitesse de convergence en l'amorçant avec une valeur beaucoup plus proche du résultat sachant que si N est un nombre de NC chiffres avec NC > 1 alors RacineCarrée(N)
est un nombre de "NC div 2 chiffres" si NC est pair et de "(NC + 1) div 2 chiffres" lorsque NC est impair ...
Donc si N = XYZTUV alors Xo compris statistiquement entre 100 et 999 et pour simplifier on prend Xo = 555 dans le cas d'un N avec 6 chiffres.
(Pour NC = 1 on se contente de Xo = N div 2)

Exemples de résultats :
- RacineCarrée(999999999) obtenu en 5 tours de boucle au lieu de 18 soit un facteur d'accéllération de 3,6
- RacineCarrée(9111111111111111111) en 6 tours au lieu de 35 soit un facteur d'accéllération de 5,8
<-- ici N est proche de limite des Int64.
- RacineCarrée(99999999999999999999999999999999999999999) (NC = 41) obtenu en 7 intérations au lieu de 73 soit un facteur d'accéllération de 10 (Result = 316227766016837933199).

A+

Commentaire de pseudo3 le 30/09/2008 16:19:27

Salut,

A propos de RacineCarrée(N) : En utilisant l'algo de Héron d'Alexandrie ou de Newton qui converge déjà relativent vite en l'amorçant avec une valeur approchée Xo = N/2 il est possible de multiplier par K sa vitesse de convergence en l'amorçant avec une valeur beaucoup plus proche du résultat sachant que si N est un nombre de NC chiffres avec NC > 1 alors RacineCarrée(N)
est un nombre de "NC div 2 chiffres" si NC est pair et de "(NC + 1) div 2 chiffres" lorsque NC est impair ...
Donc si N = XYZTUV alors Xo compris statistiquement entre 100 et 999 et pour simplifier on prend Xo = 555 dans le cas d'un N avec 6 chiffres.
(Pour NC = 1 on se contente de Xo = N div 2)

Exemples de résultats :
- RacineCarrée(999999999) obtenu en 5 tours de boucle au lieu de 18 soit un facteur d'accéllération de 3,6
- RacineCarrée(9111111111111111111) en 6 tours au lieu de 35 soit un facteur d'accéllération de 5,8
<-- ici N est proche de limite des Int64.
- RacineCarrée(99999999999999999999999999999999999999999) (NC = 41) obtenu en 7 intérations au lieu de 73 soit un facteur d'accéllération de 10 (Result = 316227766016837933199).

A+

Commentaire de pseudo3 le 30/09/2008 16:19:31

Salut,

A propos de RacineCarrée(N) : En utilisant l'algo de Héron d'Alexandrie ou de Newton qui converge déjà relativent vite en l'amorçant avec une valeur approchée Xo = N/2 il est possible de multiplier par K sa vitesse de convergence en l'amorçant avec une valeur beaucoup plus proche du résultat sachant que si N est un nombre de NC chiffres avec NC > 1 alors RacineCarrée(N)
est un nombre de "NC div 2 chiffres" si NC est pair et de "(NC + 1) div 2 chiffres" lorsque NC est impair ...
Donc si N = XYZTUV alors Xo compris statistiquement entre 100 et 999 et pour simplifier on prend Xo = 555 dans le cas d'un N avec 6 chiffres.
(Pour NC = 1 on se contente de Xo = N div 2)

Exemples de résultats :
- RacineCarrée(999999999) obtenu en 5 tours de boucle au lieu de 18 soit un facteur d'accéllération de 3,6
- RacineCarrée(9111111111111111111) en 6 tours au lieu de 35 soit un facteur d'accéllération de 5,8
<-- ici N est proche de limite des Int64.
- RacineCarrée(99999999999999999999999999999999999999999) (NC = 41) obtenu en 7 intérations au lieu de 73 soit un facteur d'accéllération de 10 (Result = 316227766016837933199).

A+

Commentaire de pseudo3 le 30/09/2008 16:24:13

Re-salut,

Comment se fait-il que mon commentaire apparaise Ixe-fois ?
Peut-on supprimer soi-même l'un des commentaires redondants ?

A+

Ajouter un commentaire

Discussions en rapport avec ce code source dans le forum

Racine cubique [ par lanosic ] J'aimerais savoir comment on fait pour calculer une racine cubique. Pour une racine carée c'est avec (Sqrt), mais il n'y a pas de fonction pour la rac ???TRES FORT:COMMENT ROMPRE AVEC UNE FORM CARRé [ par djamel001 ] Voila j'aimerais donner une forme à ma form (ah ah ah) genre un rond pour une horloge ou une forme de télé.....vous voyez koi! je vous remercie d'avan Problème avec le carré magique [ par Gokuan ] Salut tout le monde, j'ai encore un problème avec le carré magique, mais bon pour ceux qui ne savent pas exactement ce qui est le bute dans le carré m Comparer deux images [ par jperret2 ] Bonjour,Je cherche a détecter les changements sur l'écran de l'ordinateur ou tourne mon soft. Mon idée est de quadriller l'écran carré par carré (diso Copie d'un répertoire entier. [ par Ark1 ] Hello, J'aimerais copier un répertoire entier, j'ai essayer de cette manière:CopyFile('C:\repertoire', 'E:\repertoire');Mais ceci ne marche que quand ouvrir un fichier >"en entier" >int64 [ par Kentoo ] je sais le titre n'est pas très explicite. Voilà j'ai besoin de chiffre entier et pour des raisons de place j'enregistre sous forme caractère:donc ju racine d'un polynome de degré N [ par yvessimon ] yvessimon Je souhaite trouver les racines d'un polynome de degré N > 4.Il existe différente méthodes et certainement des librairies ou progrmmes en Tester si un nombre reel est entier [ par Sylvainlefou ] boujourJe cherche une fonction qui test si un reel est entier.Ce genre de fonction existe dans d'autres languages sous le nom de "isint" mais je n'est VERIFIER SI LE CONTENU D'UN TEDIT EST UN NOMBRE ENTIER [ par yvescollet ] j'aimerais savoir comment on peut controler que la saisie dans un TEdit soit bien un nombre entier? (donc pas de caractères, juste une suite de chiffr Associer TTreeView à TComboBox [ par skorpios27 ] Salut à tous, J'avais sauvé les données dans TTreeView sur le disque dur, ainsi récupéré les données dans TComboBox, d'ici là pas de problème, mais le