Multipliziert zwei lange lange Ganzzahlen C

Arbeite ich an einem Programm in C als ein Teil der Hausaufgaben, in dem ich das Produkt erhalten Sie zwei lange Zahl, die als Zeichenkette. eg: 123456789021 und 132456789098. Da Sie als string, ich Sie konvertiert long long int für die Multiplikation. Aber das resultierende Produkt wird sehr groß sein(größer als long long int, die ich denke). Kann bitte jemand mir empfehlen eine Methode zur Durchführung dieser Multiplikation?

InformationsquelleAutor Light_handle | 2009-12-06
  1. 15

    Hier ist ein Ansatz: Überlegen Sie, wie würden Sie multiplizieren Sie diese Zahl per hand auf Papier. Implementieren Sie diese Methode in C. Sie haben zu entdecken:

    • wie zu brechen eine Ganzzahl (als Zeichenfolge dargestellt) in Ziffern
    • wie konvertiert jede Ziffer zurück in einen integer 0 <= d < 10
    • wie verwalten von arrays von zahlen (dh. wie groß sollte Sie machen die arrays?)
    • wie schreibt der Schleife(N), die Sie implementieren müssen, Multiplikation
    • wie zu verwalten, die Produkte zu tragen, die aus einer Ziffer zur nächsten
    • wie konvertiert man die Ziffern wieder Zeichen für die Ausgabe
    • Und wenn es nicht für die Tatsache, dass Ihr input und output wurden in der Basis 10, die Sie tun könnten, alle diese effizienter durch die Verwendung der Basis 2^32 (Ziffern statt in einer 64-bit-Typ) oder Basis 2^16 (in einem 32-bit-Typ) anstelle der Basis 10.
    InformationsquelleAutor Greg Hewgill
  2. 1

    in der Regel große Integer-zahlen dargestellt als byte-arrays. Sie können sich bei Microsoft die BigInteger-Implementierung der DLR. Ich denke, Sie haben sich entwickelten algorithmen von Knuth

    InformationsquelleAutor Ilya Khaprov
  3. 1

    Überprüfen Sie diese BigInteger Bibliothek und ein sehr basic-Beispielcode von der Welt der Sieben.

    Wenn Sie Interesse an einigen meiner Wohnung gekocht-codes in C (nur Multiplikation) :

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

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

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

    Dies funktioniert in einigen der früheren Programmierung Wettbewerben ich teilgenommen hatte ;), Aber wenn Sie sind auf der Suche nach noch schnelleren Algorithmus zur Matrixmultiplikation, die Sie Umsetzen können Karatsuba-Algorithmus,ich persönlich benutze diese jetzt in Echtzeit bestreiten.

    • (Der erste war ein link zu Mahbub Murshed Suman's BigInteger-Klasse (Version 6.7.28, Juli 30, 2004), die zweite war von Welt der Sieben - Wettbewerbsfähige Programmierung, auch wenn die URL lautet "steven".)
    InformationsquelleAutor whacko__Cracko
  4. 1

    Hey Mann,check das aus,ich Schloss es gestern am 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");
}
    InformationsquelleAutor Ahnaf Sakib
  5. 0

    Können Sie eine Bibliothek für große integer-arithmetik, Wikipedia hat eine Liste hier.

    • Obwohl große Anzahl von Bibliotheken sind oft hilfreich, ich glaube, es würde gegen den Gedanken und Zweck hinter dem problem.
    InformationsquelleAutor Doc Brown
  6. 0

    Ein anderer Ansatz wäre, multiplizieren Sie die zahlen als float/double und stip aus der Dezimalstellen bei der Anzeige der Ergebnisse.

    • Sie könnten möglicherweise verlieren eine Menge Präzision, dies zu tun.
    • Das wird nicht eine genaue Antwort geben wenn es zu viele Ziffern zwar. Es kann gut genug sein-je nach Anwendungsfall -, aber ich glaube nicht, dass das der Punkt, der die Abtretung mitteilt.
    InformationsquelleAutor Pratik Bhatt
Schreibe einen Kommentar