Multiplying two long long ints C

Question

I am working on a program in C as a part of Homework in which I have to get the product of two long numbers which are taken as character string. eg: 123456789021 and 132456789098. Since it is taken as a string, I converted them to long long int for the multiplication. But the resulting product will be very large(larger than long long int I guess). Can anyone please suggest me a method to perform this multiplication?

Answer 1

Here's one approach: Consider how you would multiply these numbers by hand, on paper. Implement this method in C. You will have to discover:

• how to break up an integer (represented as a string) into digits
• how to convert each digit back to an integer 0 <= d < 10
• how to manage arrays of digits (ie. how big should you make the arrays?)
• how to write the loop(s) you might need to implement multiplication
• how to manage carrying products from one digit to the next
• how to convert those digits back to characters for output

Answer 2

usually big integers represented as byte arrays. You can look at Microsoft's BigInteger implementation in DLR. I think they've used algorithms developed by Knuth

Answer 3

Check this BigInteger library and a very basic sample code from World of Seven.

If you are interested in some of my home cooked codes in C (only multiplication) :

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

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

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

This works in some of the earlier programming contests I had participated ;)But if you are looking for even faster multiplication algorithm you can Implement Karatsuba algorithm,I personally use this now in real time contest.

Answer 4

Hey man,check this out,i just completed it yester day as a part of my homework:

#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

You can use a library for large integer arithmetik, Wikipedia has a list here.

Answer 6

Another approach would be to multiply the numbers as float/double and stip off the decimal when displaying the results.