Algorithme de multiplication.

Bonjour.

je crée actuellement un type particulier qui peut accepter de grands nombres.
le système est simple et est découpé en quatre sous-nombres jusqu'à 10^28 manipulables par les opérations classiques tant qu'une valeur ne dépasse pas le seuil des 10^28 (pendant aussibien que dans le résultat).
j'ai réussi à faire la fonction d'adition et de soustraction de x nombres entres eux, mais je n'arrive pas à faire celle de multiplication.
en effetj'ai essayé au départ de faire x aditions mais la procédure est horriblement lente et inutilisable.

si quelqu'un à une idée...


merci

La première question est naturellement pourquoi tu ne veux pas récupérer une bibliothèque existante, il y en a à foison sur le web (gnu mp pour n'en citer qu'une)...

La deuxième question c'est d'où vient ces 10^28? Ca ne correspond à rien que je voie qui puisse servir de base à du calcul en précision multiple.

La technique est naturellement de vérifier avant de faire le calcul qu'il n'y a pas de dépassement de capacité (test du genre l < MAX/r où MAX serait ici 10^28 ).

Salut
je programme en vb6, et je n'ai pas trouvé ce genre de biblioteque.
les 10^28 vienntent en fait de la valeur de la plus grosse constante entièresans aproximations (soit à 1 pres) qui est disponible en vb.

Envoyé par Jean-Marc.Bourguet

La technique est naturellement de vérifier avant de faire le calcul qu'il n'y a pas de dépassement de capacité (test du genre l < MAX/r où MAX serait ici 10^28 ).

C'est ce que j'ai fait pour l'addition.

mon véritable problème, est de savoir connet programmer une multiplication.


salut

Envoyé par JC_Master

Le seul problème viendra de quand tu voudras multiplier deux "SuperNombre" entre eux.

Non, le problème n'est pas là, puisqu'il suffit de réappliquer la distributivité, mais il faut gérer le dépassement de capacité par contre... Ma suggestion est de découper le nombre en partie encore plus petite, de façon à ce que la multiplication de deux de ces parties ne puisse pas engendrer de dépassement de la limite de la représentation concrète choisie pour le stockage.

--
Jedaï

Justes quelques questions pour mieux t'aider :
- Tes grand nombres sont-ils de entiers ?
- Connais-tu l'ordre de grandeur maximal des nombres que tu devra gérer ? (plutôt 10^20, 10^50, 10^100... ?) Ou la précision doit être variable ?

Envoyé par Selenite

Justes quelques questions pour mieux t'aider :
- Tes grand nombres sont-ils de entiers ?
- Connais-tu l'ordre de grandeur maximal des nombres que tu devra gérer ? (plutôt 10^20, 10^50, 10^100... ?) Ou la précision doit être variable ?

oui, mes nombres sonts des entiers avec un plafond dans chaques parties de 10^28 et un plafond total de 10^112. jais une précision d'une unité, et je peut compter dans le négatif.

Envoyé par JC_Master

Une autre solution consiste a gèrer les calcule avec les bits. Imaginon un tronson de bit, il te sufit de répéter els actions effectuer sur les peits nombre avec ton gros troncon(Ou dans le cas ou il est diviser, t'arenger pour repartire les opérations avec la distributivitée).
Tu a normalement des opérateur de manipulation de bit(du style du |, du & et des <</>> en c++)

j'ai en effet une manipulation de bits même si ce n'est pas du C++. cependant, je ne comprend pas bien ce que tu veut dire; pourrais tu t'exprimer plus clairement ou me donner un bout de code s'il te plait?

Envoyé par Jedai

JC_Master a écrit:
Le seul problème viendra de quand tu voudras multiplier deux "SuperNombre" entre eux.


Non, le problème n'est pas là, puisqu'il suffit de réappliquer la distributivité, mais il faut gérer le dépassement de capacité par contre... Ma suggestion est de découper le nombre en partie encore plus petite, de façon à ce que la multiplication de deux de ces parties ne puisse pas engendrer de dépassement de la limite de la représentation concrète choisie pour le stockage.

Si, c'est maleureusement un problème car si 33*33= 33*3+ 33*30, si, j'avais des nombres par exemples limités à la dizaine simple, 33*3 <>3*3+3*3*10^2....

merci à tous, et si vous avez encore des idées...


salut

Si, c'est maleureusement un problème car si 33*33= 33*3+ 33*30, si, j'avais des nombres par exemples limités à la dizaine simple, 33*3 <>3*3+3*3*10^2....

merci à tous, et si vous avez encore des idées...

salut

Supposons que tu veuilles calculer des nombres limités à 10^4-1 avec des nombres limités à 10^2-1
Alors tu dois faire tes multiplications avec des nombres limités à 10^1-1 pour éviter les dépassements :
soit A = a*10^3 + b*10^2 + c*10^1 + d
B = a'*10^3 + b'*10^2 + c'*10^1 + d'
Alors, A*B = (a*10^3 + b*10^2 + c*10^1 + d) * (a'*10^3 + b'*10^2 + c'*10^1 + d')
A*B = (a*10^3 * (a'*10^3 + b'*10^2 + c'*10^1 + d') + b*10^2 * (a'*10^3 + b'*10^2 + c'*10^1 + d') + c*10^1 * (a'*10^3 + b'*10^2 + c'*10^1 + d') + d * (a'*10^3 + b'*10^2 + c'*10^1 + d') )
A*B = a*a' * 10^6 + a*b' * 10^5 + a*c' * 10^4 + a*d' * 10^3 + .....

Donc dans le tas il te suffit de vérifier que a*a' = 0, a*b' = 0, etc.. (ce qu'on peut éviter en vérifiant seulement que la multiplication du nombre de plus haut degré des deux nombres ne dépasse pas un certain seuil), puis tu fais les additions à la fin de façon raisonnée (en faisant des "retenues"). Ainsi il n'y a pas de problème de dépassement de capacité de tes entiers natifs. (tu calcules juste les x * y, pas les x * y * 10^z)
Je pense également qu'on doit pouvoir adapter l'algorithme de Karatsuba pour les polynômes pour faire ça un peu plus rapidement.

(Dans tout ça j'ai supposé que ton implémentation était une sorte de tableau contenant un découpage selon des puissances (de 10 ici, mais plutôt de 2 dans une vraie implémentation), si ce n'est pas le cas, j'aimerais bien savoir ce que tu fais ?)

--
Jedaï

Envoyé par Jedai

(Dans tout ça j'ai supposé que ton implémentation était une sorte de tableau contenant un découpage selon des puissances (de 10 ici, mais plutôt de 2 dans une vraie implémentation), si ce n'est pas le cas, j'aimerais bien savoir ce que tu fais ?)

c'est une implémentation de 10 en fait car j'utilise des fonctionsdéja définies allant jusqu'a 10^28.

sinon, merci JC master, pas eu le temps de tout regarder, mais ça me parait une bonne solution (par contre, je suis pas sûr que je vais réussir ça tout seul, on verra.)

merci à tous

Envoyé par méphistopheles

Envoyé par Jedai

(Dans tout ça j'ai supposé que ton implémentation était une sorte de tableau contenant un découpage selon des puissances (de 10 ici, mais plutôt de 2 dans une vraie implémentation), si ce n'est pas le cas, j'aimerais bien savoir ce que tu fais ?)

c'est une implémentation de 10 en fait car j'utilise des fonctionsdéja définies allant jusqu'a 10^28.

sinon, merci JC master, pas eu le temps de tout regarder, mais ça me parait une bonne solution (par contre, je suis pas sûr que je vais réussir ça tout seul, on verra.)

merci à tous

Des fonctions définies jusqu'à une puissance de dix.... Mais qu'est ce que c'est que ce truc !
(Pour les opérations sur les bits, je suis pas sûr que ce soit une bonne idée (pas plus rapide que d'utiliser les opérations normales) mais bon., à toi de voir)
J'aimerais un peu plus de détail sur ton implémentation.
--
Jedaï

j'ai pas tout bien suivi alor je m'excuse si c'est hors sujet mais pourquoi ne pas le gerer dans le tas en faisant une classe spécialle qui travaillerais sur du binnaire(ou hexa) ou un array de binaire(ou hexa) ?

avantages : la au moin les calculs sont precis et on connait les methodes.
pour l'array quant tu a une retenue tu la passe au bloc precedent
normalement des operations bit a bit son plus rapides que des operateurs entiers ou autres.

mais bon je suis pas specialiste bas niveau memoire !

Moué, c'est tentable, mais l'endianess risque pas de poser des soucis.

Par contre j'ai eu l'occasion de coder une calculatrice en nombres et bases infinis, et c'est vrai que la multiplication c'est la galère.

C'est pas dur en soit avec la méthode scolaire, cad multiplication de chaque chiffre, addition du total, mais si ta structure de données n'est pas extensible, effectivement tu devras gerer les dépassements, qui arrivent assez vite avec des multiplications sur de tels nombres ...

Sinon faut implémenter Karatsuba pour vraiment gagner en performances, mais là encore pour ce genre de projets ta structure de données est primordiale. A quoi ressemble t elle ?

Est ce juste un gros entiers ? une liste entier / puissances comme la gestion de polynomes ?

Envoyé par doccpu

normalement des operations bit a bit son plus rapides que des operateurs entiers ou autres.

mais bon je suis pas specialiste bas niveau memoire !

Bien sûr qu'elles sont plus rapides, mais uniquement parce que le nombre d'opérations bit à bit nécessaire pour faire une opération comme l'addition est non négligeable (nombre d'opération optimisé par le processeur lors d'une opération entière ! Ne pas oublier non plus que les processeurs actuels ont des gros pipelines pour les opérations comme la multiplication) ! (c'est pourquoi utiliser du bit à bit pour simuler des opérations ne m'apparaît pas comme immédiatement bénéficiaire, sauf en calculant très bien son coup)

--
Jedaï

je me suis peut etre mal exprimé je voulais dire des opperations au niveau binaire avec des operateurs qui gerent le binaire comme and, or, XOR, N-XOR etc...

Envoyé par méphistopheles

oui, mes nombres sonts des entiers avec un plafond dans chaques parties de 10^28 et un plafond total de 10^112. jais une précision d'une unité, et je peut compter dans le négatif.

Parfait.
Alors voilà une manière de procédé.

Utilise non pas des parties de 10^28, mais 10^14. Ce faisant, tu n'aura pas de dépassement de capacité lors des additions, mais surtout lors des multiplications (10^14*10^14 <= 10^28 ). (Au fait, quel type VB te permet de gérer des nombres avec une aussi grande précision ?)

Ensuite crée une routine qui reporte les retenues. C'est-à-dire que si le nombre de la première partie dépasse 10^14, tu reporte l'éxcédent sur le seconde, etc.

Code :

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

1
2
3
4
5
6
 
Nombre a ;
 
for i in 0..6     // En espérant qu'il n'y ait pas de retenue sur la dernière partie...
	a[i] += ( c[i-1] modulo 10^14 )
endfor

Ces opérations de modulo seront grandement optimisée si tu travaille en base 2 plutôt qu'en base 10.


Pour l'addition tu additionnes chaque partie de même rang, et tu reporte les retenues.

Code :

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

1
2
3
4
5
6
7
8
 
Nombre a, b ;		// Opérande.
Nombre c = {0, 0, 0, 0, 0, 0, 0, 0} ;		// Résultat.
 
for i in 0..7
	c[i] = a[i] + b[i]
endfor
Report des retenues de c.

Pour la multiplication, c'est un peu plus compliqué. Etant donné que tu n'aura que des nombres de 8 parties, tu peut sans problème utiliser un algorithme naïf, qui utilisera 16 multiplications de bases.

Voici l'algo:

Code :

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

1
2
3
4
5
6
7
8
9
10
 
Nombre a, b ;
Nombre c = {0, 0, 0, 0, 0, 0, 0, 0} ;
 
for i in 0..3
	for j in 0..3
		c[j+i] += a[i]*b[j]
	endfor
	Report des retenues de c.
endfor

Tes nombres en entrée ne devront pas dépasser 10^56. C'est-à-dire que leurs quatre dernières parties devront être mises à zéro.

Tu pourras éventuellement optimiser la multiplication avec Karatsuba qui peut-être sera efficace ici (réduction à 9 multiplications, mais plus d'additions). Je te renvoie à Google si tu es intéressé.

Merci à tous, et désolé de ne pas avoir pu répondre ce matin.

pour les opérations binaires, j'ai lu le document de jc master.
cependant, je voudrais savoir comment multiplier par autre-chose que des puissance de 2.
j'aimerasi égualement savoir comment effeectuer des opérations qui dépassent les 10^28.

Envoyé par Selenite

(Au fait, quel type VB te permet de gérer des nombres avec une aussi grande précision ?)

c'est une fonction qui peut convertir des chaines string en nombre de type variant. apres cela, les nombres sont manipulables normalement.
la fonction est la fonction "Cdec".


sinon, j'ai déja fait un algo d'addition, mais j'ai utilisé une methode plus simple: pour additionner deux nombres < 10^28, je prend le premier, je lui retire 10^28 et j'ajoute le second, puis je regarde le signe du résultat. s'il est positif ou nul, je prend le résulta pour cette partie et je rajoute une unité à la partie supérieure,s'il est négatif, j'ajoute les deux nombres.

Envoyé par Selenite

Code :

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

1
2
3
4
5
6
7
8
9
Nombre a, b ; 
Nombre c = {0, 0, 0, 0, 0, 0, 0, 0} ; 
 
for i in 0..3 
   for j in 0..3 
      c[j+i] += a[i]*b[j] 
   endfor 
   Report des retenues de c. 
endfor

heu, je n'ai pas bien compris ce qu'étais C pourrais-tu expliquer?


merci

"c" c'est le résultat.

Je te conseille vivement d'employer les méthodes de Sélénite : il s'agit de la solution que je t'ai préconisé (mais explicité ).

Et oublie les opérateur binaires.

je me suis peut etre mal exprimé je voulais dire des opperations au niveau binaire avec des operateurs qui gerent le binaire comme and, or, XOR, N-XOR etc...

On s'est très bien compris et visiblement tu n'as pas fait d'étude des processeurs... Ta méhode n'est pas intéressante dans le cas général (sans parler du fait qu'un bon compilateur/interpréteur optimisera tout seul les opérations normales en opérations binaires dans les cas particuliers où c'est intéressant).
--
Jedaï

Merci, je n'avais pas bien lu.
je vais bosser ça, je vous doonerais des nouvelles quand j'aurais résolu (ou pas) mon problème.


salut

j'ai pu résoudre mon problème, merci à tous.
par contre, pour les seizes opérations de base de sélénite, je me suis débrouillé avec une petite double boucle imbriquée.


salut