begin process at 2012 02 11 06:47:07
  Trouver un code source :
 
dans
 
[ Dernières recherches ]
Accueil > 

Code

 > 

Maths

 > RACINE CARRÉE ENTIÈRE

RACINE CARRÉE ENTIÈRE


 Information sur la source

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

  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10
Catégorie :Maths Classé sous :racine, carré, cubique, entier Niveau :Débutant Date de création :14/06/2008 Vu :6 060
Auteur : barbichette

Ecrire un message privé
Site perso
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

Source avec Zip Source avec une capture COMPARATIF ALGO CERCLES
Source avec Zip Source avec une capture INTERPRETEUR DE LANGAGE PERSONNALISABLE BIS
Source avec Zip Source avec une capture INTERPRETEUR DE LANGAGE PERSONNALISABLE
Source avec Zip Source avec une capture RUBIK'S CUBE
Source avec Zip Source avec une capture SPINEDIT EN DÉCIMAL AVEC GESTION DES UNITÉS
Toutes les sources de barbichette

 Sources de la même categorie

Source avec Zip Source avec une capture RESOLUTION EQUATIONS DEGRE "N" + CALCULETTE SCIENTIFIQUE par pseudo3
Source avec Zip DEUX BIBLIOTHÈQUES POUR CALCULER AVEC DES ENTIERS TRÈS GRAND... par Rekin85
Source avec Zip Source avec une capture MOTEUR PHYSIQUE 2D CHIPMUNK.. EN DELPHI! par Bacterius
Source avec Zip Source avec une capture TABLEAU DE KARNAUGH par ADMR
Source avec Zip Source avec une capture FILTRAGE NUMÉRIQUE IIR par Pouillerot
Toutes les sources de la catégorie Maths

 Sources en rapport avec celle ci

Source avec Zip Source avec une capture CONJECTURE DU CARRÉ DES FACTEURS par Bacterius
Source avec Zip Source avec une capture MÉTHODE DICHOTOMIQUE : CALCUL DE RACINE CUBIQUE par bad_dark_spirit
Source avec Zip Source avec une capture MÉTHODE DE NEWTON : CALCUL D'UNE RACINE CARRÉE par bad_dark_spirit
Source avec Zip Source avec une capture CONVERSION LITTÉRALE D' 1 NOMBRE EN PORTUGAIS par MAURICIO
Source avec Zip Source avec une capture LES NEUFS CARRÉS MAGIQUES par hoby500

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 &gt; 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


Nos sponsors


Sondage...

Comparez les prix


Mio - Moov V735 - GPS Europe - Ecran 7"
Entre 305€ et 375€

Visiter le guide achat

CalendriCode

Février 2012
LMMJVSD
  12345
6789101112
13141516171819
20212223242526
272829    

Consulter la suite du CalendriCode

Photothèque

Photo Green Energy Solutions With Light Bulb Morphed Into LandscapePhoto Renewable Energy is Within Reach
Photo Monument Valley Utah known as The Mittens 

Visiter la photothèque
 
Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils.
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés

Google Coop CodeS-SourceS Google Coop CodeS-SourceS
Temps d'éxécution de la page : 4,025 sec (3)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales
Outils Convertisseur VB/C# Snippets et scripts Outils en ligne La ToolBox
Communauté Programmation Photographie Technologie Newsgroups Emploi Forum Blogs
Guide d'achat Téléphonie mobile Image et son Informatique Bureautique Jeux vidéo
Logiciels Internet & Réseau Développement Market Android Jeux & Loisirs Graphisme Multimédia Sécurité Pilotes
Loisirs Cartes virtuelles Vidéos droles Jeux en ligne Géoguide AndroLib (Android Market)