Racine carrée entière
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)
- 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...
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...
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.