[TonighT]

Bonjour,

J'aimerais savoir quelles sont mes possibilités en C++ pour multiplier 2 nombres de plus de 100 chiffres.

J'attends de vous des astuces au niveau du stockage des données (vu qu'un long int ne suffit pas), du déroulement de la multiplication (je suppose qu'il faille découper les nombres avant) et de l'obtention du résultat le plus rapide possible (donc comment coder ça proprement).


Merci d'avance.

[Cosima von Bülow]

Un double ne suffit pas ?

[harermuir]

Citation :

Publié par Cosima von Bülow

Un double ne suffit pas ?

Naivement, je dirais fait une classe qui assemble des int et definit une multplication sur ca (et un affichage si nécessaire, et toute les opérations dont tu as besoin).

[TonighT]

Citation :

Publié par Cosima von Bülow

Un double ne suffit pas ?

Oula non

[Caherryan]

A ma connaissance, le plus simple est d'utiliser une librairie conçue pour manipuler des grands nombres tel GMP ou NTL

[thanatosX]

J'ai souvenir d'un prof de math qui parce qu'on faisait trop de bruit en classe nous avait donner une grosse multiplication a faire.
Avec deux nombre a plus de 10 chiffre pour rendre toute utilisation de calculatrice (calculette a l'époque) inutile.

Si mes souvenir sont bon j'avais utiliser l'astuce suivante (a l'époque je n'était qu'en 6eme):
Decouper les deux nombres en plusieurs partie (de 6 chiffre par exemple) pour faire des sous multiplication.
Et a la fin tu as juste a additionner les résultats.

Juste pour le fun je retente l'expérience a la volée et sans filet :

Code:

   123'456
   x   789 
97'406'784

Si on coupe le 1er nombre par tranche de "Y" chiffres (3 dans ce cas la), ça doit donner un truc du style :

Code:

  (123   x9 x100 + 456   x9)      x100 c'est pour le découpage par Y chiffre, soit : x 10^Y
+ (123  x80 x100 + 456  x80) x 10^0    x80 et x700 c'est le décalage décimale due a toute
+ (123 x700 x100 + 456 x700) x 10^1    multiplication

Vous suivez ?

Code:

  ( 1'107'000 +   4'104)
+ ( 9'840'000 +  36'480)
+ (86'100'000 + 319'200)
   97'047'000 + 359'784

ça suis toujours ? bon je continue

Code:

   1'111'104
+  9'876'480
+ 86'419'200
  97'406'784

On obtient bien le meme resultat.
Bien sure, ce n'est qu'un exemple, mais il est applicable a une operation bien plus complexe.
Le plus long a ete de poser et surtout verifier l'exactitude de mes calcul, c'est la quon aime les tableurs.

P.S. : Bon ça merde quelque part, mais cette logique marche, c'est sur.
P.P.S. : Je me plante a la 2eme partie quant on rassemble les bout de multiplication.
P.P.P.S. : ça marche toujours pas j'appelle super-excel pour m'aider a résoudre ça et je reviens.
P.P.P.P.S. : CA MARCHE ! (Maintenant je doit le remettre en forme pour que ce soit plus lisible.)
P.P.P.P.P.S. : Bon j'ai rejouer des espace pour les millier je ne sais pas si c'est plus visible avec ou sans.

[Melchiorus]

Citation :

Publié par Korika

P.S. : Je me plante a la 2eme partie quant on rassemble les bout de multiplication.

C'est x1000 et pas x100

Citation :

Publié par Korika

si je multiplie par 100 c'est a cause
du découpage par par Y chiffre, soit : x 10^(Y-1).

x 10^Y

[thanatosX]

J'ai commence ça de tête, sans calculatrice ni tableur pour m'aider a faire ça.
Je corrige de moi même, je te remercie quant même c'est pas évident a trouver. /KISS

Je ne sais pas si c'est applicable a ta programmation, mais ça doit pouvoir soulager un peut tes DLL je pense en "splitant" les calcules.
Bon on est dimanche matin et je me suis pris la tête pendant 2 plombe rien que pour çà, j'adore !
/emm vas se recoucher

[TonighT]

Je te remercie bien Korika, c'est ce genre de reponses que j'attendais

[alababa]

J'aimerai savoir l'intérêt de multiplier deux grands nombres pour obtenir un résultat à 10 000 chiffres : aucun type numérique ne peut contenir un nombre à 10 000 chiffres.

Il ne serait pas plus simple de ne multiplier que les parties significatives pour obtenir une approximation affichée en puissance de 10 ?

[Noth]

En fait ca dépend ce que tu fais ... Ce genre de calcul peut être utile pour certains types de simulation, ou en crypto ...
(Mais c'est sur que si c'est pour calculer les coordonnées de ton perso dans un univers en 3d, y'a un pb qque part )

Après pour le résultat, il faut le stocker dans un structure/tableau, ou ce que tu veux ... bref, ca te complique bien la vie après...

[AskA]

j'avais fais un truc comme ca en C. Le principe est de stocker ca dans une chaine de caractères (ou un int *, mais la chaine de caractere prend moins de place), et de faire la multiplication à l'unité, dans le même style que si tu faisait ta multiplication à la main.

Si tu veux les sources en C, dit le moi, je te l'enverrai.

[Kathar - Alleria - Lango]

Citation :

Publié par Ackshel

J'aimerai savoir l'intérêt de multiplier deux grands nombres pour obtenir un résultat à 10 000 chiffres : aucun type numérique ne peut contenir un nombre à 10 000 chiffres.

Il ne serait pas plus simple de ne multiplier que les parties significatives pour obtenir une approximation affichée en puissance de 10 ?

Je veux pas dire, mais quand tu multiplies deux nombres de 100 chiffres, tu obtiens un nombre de 200 chiffres, pas de 10.000 chiffres.

Sinon, pour l'auteur du fil :
tu fais une classe MyLongInt, qui comprend un tableau d'entiers (tu peux choisir d'autres types numériques, comme caractère ou entier long, mais question vitesse l'entier est le plus intéressant puisqu'il a la taille des registres du processeur, et que donc le processeur fait des opérations dessus en une instruction)

Et tu surcharges l'opérateur * pour cette classe.
L'algorithme de multiplication que l'on apprend à l'école primaire est directement utilisable :

Code:

       1 2 3
   × 4 5 6
----------
       7 3 8  (123×6)
+   6 1 5 -  (123×5)
+ 4 9 2 - - (123×4)
----------
  5 6 0 8 8

À noter que pour cela il te faudra implémenter la multiplication d'un MyLongInt par un entier, l'addition de deux MyLongInt, et le décalage d'une case vers les poinds forts dans ton tableau.
Par exemple:

Code:

MyLongInt MyLongInt::operator*(const MyLongInt &a) const
{
    MyLongInt result(size); // tableau de size entiers, intialisé à 0
    unsigned int i;
    for (i=0; i<size; i++)
    {
        result = result.decalage() + a*data[i]
    }
    return result;
}

[Noth]

Je plussoie la méthode de Lango ... c'est un très bon compromis facilité d'implémentation/performances !
Par ailleurs, la redéfinition de l'opérateur simplifie pas mal la vie ensuite pour se servir de tout ca ...

[TonighT]

Citation :

Publié par Noth

En fait ca dépend ce que tu fais ... Ce genre de calcul peut être utile pour certains types de simulation, ou en crypto ...
(Mais c'est sur que si c'est pour calculer les coordonnées de ton perso dans un univers en 3d, y'a un pb qque part )

Après pour le résultat, il faut le stocker dans un structure/tableau, ou ce que tu veux ... bref, ca te complique bien la vie après...

Oui il s'agit de cryptologie


Merci pour ta technique Lango

[Galin]

Pour la multiplication de long nombre il ya karatsuba.