Deux longues ints multiplication longues C

Question

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

Answer 1

Voici une approche: Voyez comment vous multipliez ces chiffres à la main, sur le papier. Implémentent cette méthode en C. Vous devrez découvrir:

• comment diviser un nombre entier (représenté sous forme de chaîne) en chiffres
• comment convertir chaque chiffre d'un retour à 0 <= d < 10 entier
• comment gérer des tableaux de chiffres (ie. La taille devrait vous faire 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 revenir aux caractères pour la sortie

Answer 2

entiers généralement représentés comme grands tableaux d'octets. Vous pouvez regarder la mise en œuvre BigInteger de Microsoft DLR. Je pense qu'ils ont des algorithmes utilisés développés par Knuth

Answer 3

Cochez cette bibliothèque BigInteger et exemple de code très basique 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 êtes à la recherche d'algorithme de multiplication encore plus rapide, vous pouvez mettre en œuvre algorithme Karatsuba , j'utilise ce maintenant au concours en temps réel.

Answer 4

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");
}

Answer 5

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

Answer 6

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