begin process at 2008 09 06 08:16:35
1 237 661 membres
52 nouveaux aujourd'hui
14 313 membres club

Vous ne trouvez pas de réponse à votre problème ? Alors posez la question dans le forum.
Souvenez-vous qu'il n'y a jamais de question bête, mais rester dans l'ignorance parce que l'on n'ose pas poser une question, ça c'est une erreur !

RACINE CARRÉE ENTIÈRE


Information sur la source

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

Note :
10 / 10 - par 1 personne
10,00 / 10

  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10

Commentaire sur cette source (2)
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...
  • signaler à un administrateur
    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

  • signaler à un administrateur
    Commentaire de jackalunion le 25/06/2008 19:07:56 10/10

    Trés bonne astuce amigo trés bonne

Ajouter un commentaire

Pub



Appels d'offres

CalendriCode

Septembre 2008
LMMJVSD
1234567
891011121314
15161718192021
22232425262728
2930     

Téléchargements

Logiciels à télécharger sur le même thème :

Boutique

Boutique de goodies CodeS-SourceS