Optimisation des opérations sur les grands nombres, algorithme de Knuth

Bonjour à tous

J'ai codé un petit paquet de fonctions pour effectuer des opérations sur des grands nombres qui sont stocké dans des tableaux de char.

Mais je trouve ça trop lent, pour vous donner un ordre d'idée sur un C2D@2.5GHz :
Division :
longueur Nombre1 : 6466
longueur Nombre2 : 3775
durée : 6433ms

Multiplication :
longueur Nombre1 : 3775
longueur Nombre2 : 2691
durée : 3039ms

Alors je cherche des améliorations à y apporter. Je suis tombé sur l'algorithme de Knuth pour les divisions, mais je n'ai pas envie de le recopier bêtement sans comprendre. Quelqu'un aurait des explications sur cet algorithme ?

Merci d'avance.

Bonjour,

avant de vous lancer dans l'utilisation d'algorithmes avancés il faut :
1. vérifier que vous utilisez les bonnes options de compilation pour générer du code rapide,
2. profiler votre code pour identifier les fonctions les plus lentes.

et j'ajouterais aussi :

vérifier que l'on est dans un domaine où on a vraiment besoin de grands nombres à cette précision... :mrgreen:

C'est à dire seulement la cryptographie.... ou pour un exercice...


Dans la vraie vie, il y a des nombres réels faits pour ça (simples ou doubles)...
:aie::aie:

Citation:

---

Envoyé par Jackyzgood

des opérations sur des grands nombres qui sont stocké dans des tableaux de char.

---

... donc j'imagine que tu stoques les nombres en base 10 ? C'est certes plus facile à lire, mais vraiment pas optimisé pour l'ordinateur: ça veut dire que pour multiplier deux nombres de deux chiffres, tu va faire quatre multiplications et des additions, alors qu'une seule instruction machine suffirait. Je te conseille plutôt de stoquer tes nombres sur des entiers.

Il y a quelques années, j'ai également développé des fonctions de calculs sur les grands nombres, que j'avais essayé d'optimiser au maximum. Voici par exemple ma fonction de multiplication (le code est très crade, mais il est rapide) :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

typedef struct { unsigned short Chiffre[MAXNBCHIF]; short int Sgn; short int NbChif; } NUMBER;   BOOL Mult(NUMBER * N1, NUMBER * N2, NUMBER * N3) { NUMBER Tmp1; NUMBER * PN3; int i, j; int NbChif; int NbChif1; int NbChif2; unsigned int Chiffre1; unsigned int Chiffre2;     NbChif1 = N1->NbChif; NbChif2 = N2->NbChif; if (NbChif1 == 0 || NbChif2 == 0) { MiseAZero(N3); return TRUE; } NbChif = NbChif1 + NbChif2; if (NbChif > MAXNBCHIF) { MessageBox(hWndTop, "Nombre trop grand", szAppName, MB_OK); return FALSE; }   if (N3 != N1 && N3 != N2) PN3 = N3; else PN3 = &Tmp1; MiseAZero(PN3); PN3->Sgn = N1->Sgn * N2->Sgn;   for (j = 0; j < NbChif1; j++) { Chiffre1 = N1->Chiffre[j]; if (Chiffre1) { Chiffre2 = 0; for (i = 0; i < NbChif2; i++) { Chiffre2 = Chiffre1 * N2->Chiffre[i] + PN3->Chiffre[i + j] + (Chiffre2 >> 16); PN3->Chiffre[i + j] = (unsigned short) Chiffre2; } PN3->Chiffre[i + j] = (unsigned short) (Chiffre2 >> 16); } } if (NbChif > 0 && PN3->Chiffre[NbChif - 1] == 0) NbChif--; PN3->NbChif = NbChif; if (N3 != PN3) *N3 = *PN3;   return TRUE; }   void MiseAZero(NUMBER * N1) { memset(N1, 0, sizeof(NUMBER)); N1->Sgn = 1; }

---

Merci pour ces réponses

@Aleph69 :
qu'est ce que tu entends par :
"1. vérifier que vous utilisez les bonnes options de compilation pour générer du code rapide"

@souviron34 :
Oui je sais qu'il y a des types fait pour ça, le type double peut gérer des nombres de 308 chiffres. Mais on va dire que c'est pas curiosité personnelle que je cherche à faire ces fonctions là.

@10_GOTO_10 :
Oui ils sont stoqué en base 10, j'ai lu certains articles traitant de la manipulations des grands nombres ou il les stockait en base 2, mais j'ai pas tout bien saisi ...
Merci pour ton bout de code, je vais regarder ça.

Citation:

---

Mais je trouve ça trop lent, pour vous donner un ordre d'idée sur un C2D@2.5GHz :
Division :
longueur Nombre1 : 6466
longueur Nombre2 : 3775
durée : 6433ms

---

Je relance le sujet mais tu veux dire que tu multiplie deux nombres de longueurs 6466 chiffres et 3775 chiffres pour le deuxieme en 6433ms?? Car en ce cas ca me parait relativement rapide pour un code "fait maison". Et je serai vraiment interessé de voir une de tes fonctions!

Bonjour,

Citation:

---

Envoyé par Jackyzgood

@Aleph69 :
qu'est ce que tu entends par :
"1. vérifier que vous utilisez les bonnes options de compilation pour générer du code rapide"

---

Pour faire simple, les options de compilation -O2 ou -O3 (qui en fait correspondent à des packages de plusieurs options pour optimiser ton code). La documentation de ton compilateur doit a priori fournir toutes les options que tu peux utiliser.

Mon algorithme n'a rien de particulier, c'est simplement la multiplication et la division comme on les apprends à l'école primaire.

J'ai suivis ton conseil 10_GOTO_10, j'ai stocké mes nombres dans des tableaux d'entiers, effectivement ça va plus vite. Par contre j'ai pas encore eu le temps de bien regarder ton algo. Je pense que je regarderais tranquillement ça ce week end, en même temps que les options de compilations.

Merci encore pour ces réponses et conseils

Bonjour,

On peut utiliser un tableau de Int64 pour contenir 8 digits décimaux au lieu d'un int par digit.

On pourrait ainsi diviser le temps de calcul par un facteur 8.

on aura :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

// Au départ, on calcule T1[i] et T2[i] tels que // Tx[i] = conversion en Int64 de la sous-chaine de 8 digits entre i*8 et i*8+7.   // Avant la boucle principale de multiplication int64 Retenue= 0 ; int64 Produit ; .. // Dans la boucle pricipale Produit=T1[i]*T2[i]+Retenue ; T[i]=Produit modulo 10000000 ; Retenue=Produit/10000000

---

;