Moltiplicazione di due long long int C

Question

Sto lavorando su un programma in C come una parte della casa che ho per ottenere il prodotto di due numeri che sono presi come stringa di caratteri.ad esempio:123456789021 e 132456789098.Dal momento che si è preso come una stringa, li ho convertiti in long long int per la moltiplicazione.Ma il prodotto risultante sarà molto grande(più grande di long long int credo).Qualcuno può per favore mi suggerisce un metodo per eseguire questa moltiplicazione?

Answer 1

Ecco un esempio di approccio:Prendere in considerazione come si dovrebbe moltiplicare questi numeri a mano, su carta.Implementare questo metodo in C.Da scoprire:

• come rompere un numero intero (rappresentato come una stringa) in cifre
• come convertire ogni cifra indietro di un numero intero 0 <= d < 10
• come gestire gli array di cifre (ie.quanto grande dovrebbe fare l'array?)
• come scrivere il loop(s) potrebbe essere necessario implementare la moltiplicazione
• come gestire il trasporto di prodotti da una cifra per la prossima
• come convertire quelle cifre indietro di caratteri per l'uscita

Answer 2

di solito grossi numeri interi rappresentati come matrici di byte. Potete guardare l'implementazione Microsoft BigInteger in DLR. Penso che abbiano algoritmi utilizzati sviluppati da Knuth

Answer 3

Controlla questo BigInteger biblioteca e un molto semplice codice di esempio da World of Seven.

Se siete interessati ad alcuni dei miei fatti in casa codici in C (solo la moltiplicazione):

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

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

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

Questo funziona in alcune delle gare di programmazione precedenti avevo partecipato;) Ma se siete alla ricerca di algoritmi di moltiplicazione ancora più veloce è possibile implementare Karatsuba algoritmo , io personalmente uso questo ora in gara tempo reale.

Answer 4

Hey man, check this out, ho appena completato esso giorno yester come una parte del mio lavoro:

#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

È possibile utilizzare una libreria per grandi arithmetik intero, Wikipedia ha una lista qui .

Answer 6

Un altro approccio sarebbe quello di moltiplicare i numeri come float / double e stip fuori dal decimale durante la visualizzazione dei risultati.