Trouble with Big Number in C++

Asked By 240 points N/A Posted on -
qa-featured

Hi,

I have taken an assignment on C++ which at first glance looked very simple. Just multiply 2 numbers! The teacher smiled at me. But now I realized why!

The numbers I have to handle are more than 30 digits. So I won’t be able to just use * !

Looks like I am in big trouble. How do I do such big number multiplication in C++.

SHARE
Best Answer by AngelOfTech
Answered By 5 points N/A #95916

Trouble with Big Number in C++

qa-featured

Glane,

  1. First of all, I would like to give you a suggestion. Try adding 2 numbers not by using (+) and also using string to store the numbers. Remember the old primary school arithmetic?
  2. Add them 1 digit by 1 and move the carry. Simulate all the processes. This would be the back bone of your multiplication program.
  3. Then just take a single digit (1st one) of the multiplier. Multiply it with the subject number( again old school arithmetic). Then the 2nd digit. And so on.
  4. Finally, add them, just as you do when multiplying using pen and paper.
Answered By 240 points N/A #95917

Trouble with Big Number in C++

qa-featured

Thanks for the reply. The program didn't compile at first. Had to add some library and a few braces. Unfortunately they gave a bad result.

Enter a number (up to 30 digits in length)> 123

The first number is: 123

Enter a second number (up to 30 digits in length)> 1

The second number is: 1

The sum of the two numbers is: 110-875710266-19147776507-9801854178-1194415713-406201652-474099748-672935959-1600219442-959534433-4734392825-980972948-303969823-609235240
-1331633444-911438227-1663054639-1063101776-875047979-1770211641-891100696-761550896-2065179199774

The product of the two numbers is: 000000000000000000000000000000000000000000000000000000000000201333116

Process returned 0 (0x0)   execution time : 4.213 s
Press any key to continue.

Thanks for the help any way. But I would like to go for making a simple one myself, for better understanding.

@AngelOfTech,

Thanks for the suggestion.  I have modularized the problem as you said. For first one I added 2 single digits( passed as characters along with carry) and added them to the first parameter. It will also return if there is any carry.


int addchar(char &a,char b,int carry=0)
{
    int p=((int)a+b-'0'-'0')+carry;
    a= (p%10)+'0';
        if(p>9)return 1;
    else return 0;
}

And adding as follows

void addBigInt(string &i1,string i2)
{
    reverse(i1.begin(),i1.end());                        //reversing makes it easy to align the digits. As we add the right most digits first.
    reverse(i2.begin(),i2.end());

    int carry=0;
    for(int i=0;i<i2.size();++i)
    {
        if(i>=i1.size())
        {
            i1+= "0";
            carry=addchar(i1[i],i2[i],carry);
        }
        else
        {
            carry=addchar(i1[i],i2[i],carry);
        }
    }
    if(carry!=0)i1+="1";
        reverse(i1.begin(),i1.end());
       reverse(i2.begin(),i2.end());
}

This is working good for,

1
+9999
=10000

but

9999
+  1
=19990

Can't find why.

Best Answer
Best Answer
Answered By 5 points N/A #95918

Trouble with Big Number in C++

qa-featured

You have adjusted i1 whenever it is smaller than i2.. But you haven't done that when i1 is greater than i2. So the adding gets messed up.

Here is a simple corrected version.


void addBigInt(string &i1,string i2)
{
    reverse(i1.begin(),i1.end());
    reverse(i2.begin(),i2.end());
    if(i2.size()<i1.size())
    swap(i1,i2);                                               // since a+b == b+ a
    int carry=0;
    for(int i=0;i<i2.size();++i)
    {
        if(i>=i1.size())
        {
            i1+= "0";
            carry=addchar(i1[i],i2[i],carry);
        }
        else
        {
            carry=addchar(i1[i],i2[i],carry);
        }
    }
    if(carry!=0)i1+="1";
        reverse(i1.begin(),i1.end());
    reverse(i2.begin(),i2.end());

}

Answered By 240 points N/A #95920

Trouble with Big Number in C++

qa-featured

Thanks very much….

Here is my muliplier (single digit) very much like the adder

int multchar(char &a,int b,int carry=0)
{
    int p=(((int)a-'0')*b)+carry;
    a= (p%10)+'0';
        if(p>9)return (p/10);
    else return 0;
}

I am a little confused about how do i do a full multidigit multiplication multiplication?

Answered By 5 points N/A #95921

Trouble with Big Number in C++

qa-featured

We have our adder ready. So we can just multiply 1 digit at a time and then finally add all the results.

Here is a startup for the function you made:

void multBigInt(string &i1,int i2)         //Multiply big integer with single digit
{
    reverse(i1.begin(),i1.end());
    int carry=0;
    for(int i=0;i<i1.size();++i)
    {
            carry=multchar(i1[i],i2,carry);
    }

    if(carry!=0)
    {
        i1+=" ";
        i1[sz(i1)-1]=carry+'0';
    }
    reverse(i1.begin(),i1.end());
}

You just have to call this one for all the digits in the multiplier and add them gradually.

Answered By 240 points N/A #95922

Trouble with Big Number in C++

qa-featured

Thanks very much. It was very nice of all of you.

Related Questions