English 中文(简体)
Multiplying two long long ints C
原标题:

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?

最佳回答

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
问题回答

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

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.

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("
Multiplication:");
    for(p=(2*strlen(one)-1);p>=0;p--)
    {
        if(p>strlen(one)&&c[p]==0)
        {
            continue;
        }
        printf("%d",c[p]);
    }
    printf("
");
}

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

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





相关问题
Fastest method for running a binary search on a file in C?

For example, let s say I want to find a particular word or number in a file. The contents are in sorted order (obviously). Since I want to run a binary search on the file, it seems like a real waste ...

Print possible strings created from a Number

Given a 10 digit Telephone Number, we have to print all possible strings created from that. The mapping of the numbers is the one as exactly on a phone s keypad. i.e. for 1,0-> No Letter for 2->...

Tips for debugging a made-for-linux application on windows?

I m trying to find the source of a bug I have found in an open-source application. I have managed to get a build up and running on my Windows machine, but I m having trouble finding the spot in the ...

Trying to split by two delimiters and it doesn t work - C

I wrote below code to readin line by line from stdin ex. city=Boston;city=New York;city=Chicago and then split each line by ; delimiter and print each record. Then in yet another loop I try to ...

Good, free, easy-to-use C graphics libraries? [closed]

I was wondering if there were any good free graphics libraries for C that are easy to use? It s for plotting 2d and 3d graphs and then saving to a file. It s on a Linux system and there s no gnuplot ...

Encoding, decoding an integer to a char array

Please note that this is not homework and i did search before starting this new thread. I got Store an int in a char array? I was looking for an answer but didn t get any satisfactory answer in the ...

热门标签