Multiplier deux longs longs C

Question

Je travaille sur un programme en C dans le cadre de Devoirs dans lequel je dois obtenir le produit de deux longs nombres qui sont pris comme chaîne de caractères. par exemple: 123456789021 et 132456789098. Comme il est pris comme une chaîne, je les ai convertis en long long int pour la multiplication. Mais le produit résultant sera très grand (plus grand que long long je suppose). Quelqu'un peut-il me suggérer une méthode pour effectuer cette multiplication?

Answer 1

Voici une approche: Pensez à comment vous pourriez multiplier ces nombres à la main, sur papier. Mettre en œuvre cette méthode en C. Vous devrez découvrir:

• comment briser un entier (représenté sous forme de chaîne) en chiffres
• comment convertir chaque chiffre de retour à un nombre entier 0 <= d < 10
• comment gérer des tableaux de chiffres (ie. la taille si vous faites les tableaux?)
• comment écrire la boucle (s) que vous pourriez avoir besoin de mettre en œuvre la multiplication
• comment gérer les produits portant d'un chiffre à l'autre
• comment convertir ces chiffres en caractères pour la sortie

Answer 2

Vous pouvez utiliser une bibliothèque pour grand arithmetik entier, Wikipedia a une liste here.

Answer 3

généralement de grands entiers représentés sous forme de tableaux d'octets. Vous pouvez regarder l'implémentation BigInteger de Microsoft dans DLR. Je pense qu'ils ont utilisé des algorithmes développés par Knuth

Answer 4

Une autre approche serait de multiplier les nombres comme float/double et stipuler la décimale lors de l'affichage des résultats.

Answer 5

Cochez cette case BigInteger library et very basic sample code de World of Seven.

Si vous êtes intéressé par certains de mes codes cuisinés maison en C (seulement la multiplication):

//////////////////////////////////////////////////////////////////////////////// 

Code removed after I checked the home-work tag ;) 

/////////////////////////////////////////////////////////////////////////////////////// 

Cela fonctionne dans certains des concours de programmation précédentes j'avais participé;) Mais si vous recherchez même algorithme de multiplication plus rapide, vous pouvez mettre en œuvre Karatsuba algorithm, j'utilise personnellement ce maintenant en concours en temps réel.

Answer 6

Hey man, vérifier cela, je viens de terminer ce jour yester comme une partie de mes devoirs:

#include<stdio.h> 
#include<string.h> 

int main() 
{ 
    char one[195]; 
    char two[195]; 
    char temp[195]; 
    int a[195],c[195],b[195]; 
    int x,i,j,k,l,p,add; 

    for(;;)/*determining the larger number...*/ 
    { 
     printf("Input A:"); 
      gets(one); 
     printf("Input B:"); 
      gets(two); 

     k=strlen(one); 
     l=strlen(two); 
     if(l>k) 
     { 
      strcpy(temp,one); 
      strcpy(one,two); 
      strcpy(two,temp); 
      break; 
     } 
     else 
     { 
      break; 
     } 
    } 
     k=strlen(one); 
     l=strlen(two); 
    for(p=0;p<195;p++)/*assigning all initial values to 0*/ 
    { 
     a[p]=0; 
     b[p]=0; 
     c[p]=0; 
    } 

    for(i=0;one[i];i++)/*converting char to integer(note:1,as a character assigned as 49.)*/ 
    { 
     a[i]=((one[--k])-48); 
    } 

    for(i=0;i<two[i];i++) 
    { 
     b[i]=((two[--l])-48); 
    } 


    for(i=0;i<=strlen(two);i++)/*main algorithm*/ 
    { 
     add=0; 
     p=0; 
     for(j=i;j<=(2*strlen(one)-1);j++) 
     { 
      x=c[j]+b[i]*a[p]+add; 
      c[j]=x%10; 
      add=x/10; 
      p++; 
     } 
    } 

    printf("\nMultiplication:"); 
    for(p=(2*strlen(one)-1);p>=0;p--) 
    { 
     if(p>strlen(one)&&c[p]==0) 
     { 
      continue; 
     } 
     printf("%d",c[p]); 
    } 
    printf("\n"); 
}