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.

[SpiceGuid]

C'est bien le même principe, donc c'est faisable puisque tu as déjà les bases.

Je travaille sur des nombres de l'ordre d'une centaine de chiffre

Une centaine de décimales, en base 10^9, ça ne ferait plus qu'une dizaine de coefficients, pas intéressant, à cette échelle le diviser pour régner devient du atomiser pour s'éparpiller.

[Wachter]

Bonjour,

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.

Pour accélérer la recherche de la racine d'un carré parfait, on peut faire appel à la dichotomie. Voici donc la version rapide de l'algorithme sus-cité :

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
17
18
19
20
21
22
23
24
 
Lire(nombre);
 
racineGauche = 0;
racineDroite = nombre / 2;
carreTrouve = FAUX;
Tant que (racineGauche < racineDroite) et (!carreTrouve)
  racineMilieu = (racineGauche + racineDroite) / 2;
  carreParfait = racineMilieu * racineMilieu;
  Si nombre == carreParfait
    carreTrouve = VRAI;
  Sinon
    Si nombre > carreParfait
      racineGauche = racineMilieu + 1;
    Sinon
      racineDroite = racineMilieu - 1;
    Fin Si
  Fin Si
Fin Tant que
 
Si carreParfait alors
  Afficher(racine);
Sinon
  Afficher(le nombre n'est pas un carré parfait !);

--
Wachter

[TrexXx]

Petite erreur, je travaille avec des nombres de l'ordre de mille chiffres (et pas cents comme j'ai dit avant).

[Wachter]

Bonsoir,

Petite erreur, je travaille avec des nombres de l'ordre de mille chiffres (et pas cents comme j'ai dit avant).

L'algorithme que j'ai proposé permet la recherche de la racine carrée d'un carré parfait dans l'intervalle [0, nombre / 2]. Pourquoi nombre / 2 ? Parce que pour tout entier naturel n, on a racineCarrée(n) <= n / 2 et particulièrement pour n = 2.

Si on suppose donc que nombre est supérieur à 4, on pourra faire la recherche dans [0, nombre / 3], pour nombre > 9, la borne supérieure de l'intervalle sera nombre / 4 et ainsi de suite... À toi donc de trouver la bonne borne supérieure de l'intervalle de recherche selon tes données, ce qui te permettra d'accélérer encore la recherche.

Je précise que cela n'est pas valable que pour les carrés parfaits !

--
Wachter

[SpiceGuid]

@Wachter
Diviser pour régner, cela signifie qu'à chaque étape tu divises par deux le nombre de décimales.
Avec la dichotomie, tu divises par deux l'espace de recherche, mais ça ne simplifie guère le problème, car le nombre de décimales reste lui quasiment identique.
Ton algo fonctionne mais il est trop naif pour les grands nombres.

Je précise que cela n'est pas valable que pour les carrés parfaits !

Et d'ailleurs c'est valable pour l'inverse de n'importe quelle fonction croissante, et pas seulement le carré. C'est dire combien c'est (trop) général.

[FR119492]

Salut!

des nombres de l'ordre de mille chiffres

Excuse ma curiosité malsaine, mais à quoi cela peut-il bien servir?
Jean-Marc Blanc

[TrexXx]

Ta curiosité n'est pas malsaine, je suis en école d'info et je dois faire une calculatrice qui travaille sur des grands nombres (de l'ordre de 1000 chiffres justement), et donc j'essaye de regarder tout les algos qui sont liés aus grands nombres.

[pseudocode]

Ta curiosité n'est pas malsaine, je suis en école d'info et je dois faire une calculatrice qui travaille sur des grands nombres (de l'ordre de 1000 chiffres justement), et donc j'essaye de regarder tout les algos qui sont liés aus grands nombres.

Si tu as déjà codé les fonctions de base (+,-,*,/) alors la méthode de Héron (aka Newton-Raphson) me semble ce qu'il y a de plus simple.

[TrexXx]

Oui j'ai déjà codé toutes les opérations de bases ! La méthode de Héron est-elle rapide ?

[Wachter]

Bonsoir,

Et d'ailleurs c'est valable pour l'inverse de n'importe quelle fonction croissante, et pas seulement le carré. C'est dire combien c'est (trop) général.

Je pense que tu ne m'as pas bien compris. Je parlais de la borne droite de l'intervalle qui peut valoir n / 2, n / 3, n / 4... J'ai dit ceci :

Code :

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

1
2
3
4
5
6
7
8
 
Si n > 4 ==> borne droite = n / 3
Si n > 25 ==> borne droite = n / 5
Si n > 81 ==> borne droite = n / 9
Si n > 100 ==> borne droite = n / 10
Si n > 10000 ==> borne droite = n / 100
Si n > 10^12 ==> borne droite = n / 1000000
...

Donc, si on estime bien les bornes de l'intervalle de recherche (j'ai mis 0 comme borne gauche mais on peut l'augmenter), on pourra quand même obtenir rapidement des résultats, quoique ça reste un algorithme bourrin !

--
Wachter

[pseudocode]

Oui j'ai déjà codé toutes les opérations de bases ! La méthode de Héron est-elle rapide ?

Elle converge très rapidement. D'autant plus si on a une bonne estimation initiale.

[kremvax]

Tu as besoin d'une fonction rapide et précise, ou seulement rapide (et un peu approximative)? Dans le second cas, je t'invite à consulter ça : http://fr.wikipedia.org/wiki/John_Carmack