Multipliziert man zwei lange, lange Ints C

Question

Ich arbeite an einem Programm in C als Teil der Hausaufgaben, in denen ich muß das Produkt von zwei langen Zahlen erhalten, die als Zeichenfolge getroffen werden. zB: 123456789021 und 132456789098. Da es als String genommen wird, ich konvertiert sie zu lange long int für die Multiplikation. Aber das resultierende Produkt wird sehr groß sein (größer als long long int I guess). Kann jemand mir bitte eine Methode vorschlagen, diese Multiplikation durchführen?

Answer 1

Hier ist ein Ansatz: Überlegen Sie, wie Sie diese Zahlen mit der Hand multiplizieren würde, auf dem Papier. Implementieren Sie diese Methode in C. Sie haben zu entdecken:

• , wie eine ganze Zahl aufzubrechen in Ziffern (als Zeichenfolge dargestellt)
• , wie jede Ziffer zurück auf eine ganze Zahl 0 <= d < 10 konvertieren
• , wie Arrays von Stellen zu verwalten (dh., Wie groß sollten Sie die Arrays zu machen?)
• , wie die Schleife schreiben (en) müssen Sie möglicherweise Multiplikation implementieren
• , wie die Verwaltung Produkte von einer Stelle zur nächsten
Tragen
• , wie diese Ziffern zurück zum Zeichen für die Ausgabe
konvertieren

Answer 2

in der Regel große ganze Zahlen als Byte-Arrays dargestellt. Sie können BigInteger Implementierung in DLR auf Microsofts aussehen. Ich denke, sie von Knuth entwickelten Algorithmen haben

Answer 3

Überprüfen Sie diese BigInteger Bibliothek und ein sehr einfacher Beispielcode von World of Seven.

Wenn Sie daran interessiert sind, etwas von mir zu Hause gekocht Codes in C (nur Multiplikation):

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

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

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

Das funktioniert in einigen der früheren Programmierung Wettbewerbe ich teilgenommen hatte;) Aber wenn Sie für eine noch schnellere Multiplikationsalgorithmus suchen, können Sie implementieren Karatsuba Algorithmus ich dies persönlich jetzt in Echtzeit Wettbewerb nutzen.

Answer 4

Hey Mann, check this out, Ich habe gerade es yester Tag als Teil meiner Hausaufgaben:

#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

Sie eine Bibliothek für große Integer-Arithmetik verwenden können, hat Wikipedia eine Liste hier .

Answer 6

Ein weiterer Ansatz wäre die Zahlen als Float / Double zu multiplizieren und stip aus dem Dezimalsystem, wenn die Ergebnisse angezeigt werden.