Discussion :

[TrexXx]

Bonsoir à tous,
Je chercher des algorithmes pour extraire la racine carrée d'un nombre (entiers seulement). J'ai déjà trouvé des algo telle que la méthode de Héron, et je voudrais surtout savoir lequel est le plus rapide. J'ai aussi vu quelque chose sur l'algorithme "Karatsuba square root", mais je ne l'ai pas bien compris, si quelqu'un pouvait m'expliquer un peu mieux.
Merci d'avance.

[FR119492]

Salut!

extraire la racine carrée d'un nombre (entiers seulement)

Tu dois d'abord décider ce qui doit se passer si ton nombre n'est pas un carré parfait.
Jean-Marc Blanc

[pseudocode]

Wikipedia à un article dédié à ce sujet.

[Wachter]

Bonsoir,

Si tu veux un algorithme simple mais bourrin, tu peux procéder comme ceci, mais à condition que le nombre soit un carré parfait comme dit précédemment :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
Lire(nombre);
 
racine = 1;
carreTrouve = FAUX;
Tant que (racine <= nombre / 2) et (!carreTrouve)
  carreParfait = racine * racine;
  Si carreParfait == nombre
    carreTrouve = VRAI;
  racine = racine + 1;
Fin Tant que
 
Si carreParfait alors
  Afficher(racine);
Sinon
  Afficher(le nombre n'est pas un carré parfait !);

--
Wachter

[SpiceGuid]

J'ai aussi vu quelque chose sur l'algorithme "Karatsuba square root", mais je ne l'ai pas bien compris, si quelqu'un pouvait m'expliquer un peu mieux.

J'ai écrit un article sur les méthodes Karatsuba, notamment la multiplication et la division.
La performance de la méthode Karatsuba (diviser pour régner) est relative au nombre de décimales.
C'est le même principe que pour un tri, si tu n'as que 3 éléments à trier alors le quicksort n'est pas la méthode la plus rapide, par contre si tu as 100000 éléments à trier alors le quicksort est très efficace (sous certaines conditions).
Ça s'explique par les courbes de complexité, des fonctions qui sont au dessus de y=x, comme par exemple y=x², passent en dessous pour des x suffisamment petits.
Réciproquement, des fonctions qui sont au dessous de y=x, comme par exemple y=√x, passent au dessus pour des x suffisamment petits.
Il est donc impossible de te recommander la méthode Karatsuba si tes entiers sont de petite taille.

Quelques pistes de réflexion :

• d'après mes tests personnels la multiplication Karatsuba est plus rapide que la multiplication naive à partir d'une trentaine de décimales (avec base=10)
• pour implémenter la racine carrée Karatsuba il te faudra d'abord implémenter la division Karatsuba, sinon tu n'as pas d'accélération
• si tu choisi cette implémentation alors le plus sage est de prototyper dans un langage de haut niveau (qui détecte les débordements de tableau) et de mettre plein d'assertions, puis ensuite de traduire dans un langage de bas niveau si tel est le but
• attends toi à un exercice difficile, on implémente pas la racine carrée Karatsuba par choix mais par obligation
• l'algorithme dans sa forme la plus aboutie est du à Michel Quercia, la définition la plus lisible est donnée dans son TD multiprécision
• éventuellement, la bibliothèque Numerix, toujours par Michel Quercia, doit contenir une implantation prête à l'utilisation

[TrexXx]

Merci SpcieGuid, je vais regarder ton lien. J'ai déjà codé la multiplication de Karatsuba, donc si c'est le même principe je devrais pouvoir me débrouiller avec les autres algo de Karatsuba. Je travaille sur des nombres de l'ordre d'une centaine de chiffre, donc c'est utile d'avoir des algo qui vont plus vite sur des nombres de cet ordre de grandeur. Et j'avais aussi prévu de faire des tests de rapidité pour voir quand est ce que les algos 'de base' sont plus rapides.