Asked By
Glane
240 points
N/A
Posted on - 05/15/2011
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++.

Answered By
Glane
240 points
N/A
#95917
## Trouble with Big Number in C++

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.

## Trouble with Big Number in C++

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
Glane
240 points
N/A
#95920
## Trouble with Big Number in C++

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?

## Trouble with Big Number in C++

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
Glane
240 points
N/A
#95922
## Trouble with Big Number in C++

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