Racine carrée entière

Soyez le premier à donner votre avis sur cette source.

Snippet vu 9 437 fois - Téléchargée 18 fois

Contenu du snippet

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 / Exemple :


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...

A voir également

Ajouter un commentaire

Commentaires

Messages postés
267
Date d'inscription
mardi 24 juillet 2007
Statut
Membre
Dernière intervention
7 juin 2018

Re-salut,

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

A+
Messages postés
267
Date d'inscription
mardi 24 juillet 2007
Statut
Membre
Dernière intervention
7 juin 2018

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+
Messages postés
267
Date d'inscription
mardi 24 juillet 2007
Statut
Membre
Dernière intervention
7 juin 2018

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+
Messages postés
267
Date d'inscription
mardi 24 juillet 2007
Statut
Membre
Dernière intervention
7 juin 2018

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+
Messages postés
267
Date d'inscription
mardi 24 juillet 2007
Statut
Membre
Dernière intervention
7 juin 2018

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+
Afficher les 8 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.