Multiplication de grands nombres

Commenter

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

S'inscrire maintenant

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.

Du même auteur (TRAX44)