Multiplication de grands nombres

Soyez le premier à donner votre avis sur cette source.

Snippet vu 10 879 fois - Téléchargée 30 fois

Contenu du snippet

C'est un de mes premiers programme en C.
Il effectue la multiplication de deux nombres quelque soit leur taille. Pour cela il utilise l'algorithme de la multiplication Egyptienne (aussi appelé multiplication Russe). Pour plus d'information sur l'algorithme : http://www.recreomath.qc.ca/dict_russe_multiplication.htm (n'est pas de moi).

Source / Exemple :


/* Exemple avec la multiplication de A=D91097D725BC9C2C et B=2E4376409371327  */

#include <stdio.h> 
#include <stdlib.h>

int main () {

 int a , b , n , i , ii, r; 

a= 1 ; b = 1 ; /* index supérieur des tableaux respectivement de A et B */
unsigned int *A = malloc (sizeof(int)*(a+1)) ; 
unsigned int *B = malloc (sizeof(int)*(a+b+2)) ; 
unsigned int *res = malloc (sizeof(int)*(a+b+2)) ; 
unsigned long long int c; 

/* A=D91097D725BC9C2C ; B=2E4376409371327 ; répartie dans leur tableau*/
A[0]=0x025BC9C2C ; B[0]=0x009371327 ; 
A[1]=0x0D91097D7 ; B[1]=0x02E43764 ;  

do {
if (A[0]%2==1) {

for (i=0 ; i<=b ; i++) {/* addition */

c=(long long int)res[i]+(long long int)B[i] ; res[i]=(c&0x0FFFFFFFF) ; 

n=i ; 
while(c>>32!=0){
n++ ; c=(long long int)res[n]+(long long int)1 ; 
if(c>>32==0){res[n]++ ;}else{res[n]=0;}
}

}/*   for 	*/
}/*   if%2	*/

r=0 ; /* décallage droite */
for (ii=0 ; ii<a ; ii++) {
r=(A[ii+1]&1)<<31 ; A[ii]=A[ii]>>1 ; A[ii]=A[ii]|r ;}
A[a]=A[a]>>1 ; if(A[a]==0){a--;}

/* décallage gauche*/
if ((B[b]&0x0EFFFFFFF)!=0) {b++ ; }
for(ii=b ; ii>=0 ; ii--) {r=(B[ii]&0x0EFFFFFFF)>>31 ; B[ii+1]=B[ii+1]|r ; B[ii]=B[ii]<<1; }
}while(a>-1) ;  

/* 160 premiers bit du résultat obtenue */
printf("\n                    %X%X%X%X%X" ,res[4] , res[3] , res[2] , res[1] ,res[0]) ; 

/* résultat du test */
printf("\n                     273A2EE4CD3E67E2EC34BC6D8C70EB4\n") ; 

free (A) ; free (B) ; free (res) ; 
return 0 ; 
} /* main */

Conclusion :


Compilé avec gcc sous gentoo :)

A voir également

Ajouter un commentaire

Commentaires

luhtor
Messages postés
2023
Date d'inscription
mardi 24 septembre 2002
Statut
Membre
Dernière intervention
28 juillet 2008
4 -
Bon pour te montrer un exemple de surchage d'addition. Si ta classe, on l'appelle VLI (very large integer) où chaque objet est constitué d'un tableau alloué statiquement (et non dynamiquement comme tu le fais dans ta source) de TAB_SIZE entiers (environ 1000 pour des grands chiffres). Ta classe a l'allure suivante:

classe VLI
{
public:
...

// on définie l'opérateur +. Puisque c'est opérateur est symétrique, il est plus logique de le déclarer en fonction ami et donc externe

friend VLI operator + (const VLI & _objet1, const VLI & _objet2);

private:

unsigned int tab[TAB_SIZE];
};

// et apres on définie la fonction d'addition
VLI operator + (const VLI & _objet1, const VLI & _objet2)
{
VLI new_VLI;
// la tu fais l'addition de ces deux VLI (_objet1 et _objet2), tu stockes le résultat dans new_VLI.

// et tu retournes le nouveau VLI créé.
return new_VLI;
}

Et maintenant dans ton programme, tu pourras écrire :

VLI c(a + b); // en utilisant l'opérateur de recopie et en considérant que a,b sont initialisés correctement.

Si tu surchares l'opérateur << du C++. Tu pourrais écrire: cout << a + b << endl;

Bon aller, voila pour une petite présentation. ++
luhtor
Messages postés
2023
Date d'inscription
mardi 24 septembre 2002
Statut
Membre
Dernière intervention
28 juillet 2008
4 -
Oke si tu débutes le C. J'ai pas fais assez attention. Tu précisais en C :)
Dans ma tete, le C++ permet tellement plus de chose, donc pour moi c'était du C++.
Mais meme si tu ne fais pas un système de classe. Tu peux te pencher sur les structures, et fournir une série de fonction avec. Comme des fonctions pour additionner, multiplier,... ces grands nombres.

Mon avis personnel étant que, ce site n'a pas pour but d'accueillir les essais personnels en matière de programmation. Si tu regardes ce site, il y a des quantités de sources très avancés qui ont un intérêt, car non seulement elle représente bcp de travail, ou elles présentent autre chose que ce que tout le monde sait à peu près faire.

Pour l'orienté objet, il y a des quantités de documents sur le C++ sur le web. En programmation basique, ton meilleur ami, c'est Google.

Pour ce qui est de la surchage des opérateurs, tu penses bien qu'il est hors de question de parser une string :)

Bon a part tout ca, bonne continuation en C :)
TRAX44
Messages postés
93
Date d'inscription
mercredi 18 septembre 2002
Statut
Membre
Dernière intervention
20 juillet 2006
-
j'ai commencé ce programme deux jour après avoir commencé a touché au C. Je ne saivais même pas (quand je l'ai fait) qu'il existait un system de classe en C.
Sinon pour surcharger les opérateur en orienté objet je vois pas comment il est possible de faire (a part parser une string).
Luthor, tu pourrais nous fair un petit tuto pour nous expliquer ? :D
Sinon, non c'est pas extraordinaire, ça permet juste de pas utiliser un truc tout pret que tu sais pas comment ça marche :)

@+
trax
luhtor
Messages postés
2023
Date d'inscription
mardi 24 septembre 2002
Statut
Membre
Dernière intervention
28 juillet 2008
4 -
C'est pas réutilisable comme code ca. Faut créer une classe pour gérer ca, surcharger les opérateurs. Enfin plein de truc qui feraient que quelqu'un d'autre puisse l'utiliser.
Car en lui meme, le principe n'a rien d'extraordinaire.

++
TRAX44
Messages postés
93
Date d'inscription
mercredi 18 septembre 2002
Statut
Membre
Dernière intervention
20 juillet 2006
-
j'ai déjà fait un gros effort avant de poster. et je veux pas la note d'un ami mais celle d'un regart critique ! :)

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.