multiplication of string [ containing integer], output also stored in string, How?

Question

Possible Duplicates:
Inputting large numbers in c++?
Arbitrary-precision arithmetic Explanation

I need to multiply two huge huge integers, like:

 a=1212121212121212121212121212121212121212121212121212;
 b=1212121212121212121212121212121212121212121212121212;

I think there are no data types in C and C++ to hold this huge an integer, so I thought to keep it as a string format like:-

char *number1="1212121212121212121212121212121212121212121212121212";
char *number2="1212121212121212121212121212121212121212121212121212";

during the time of multiplication I convert it into string with help of atoi() function like:

atoi(number1)*atoi(number2);

As usual the output of this multiplication will be obviously huge, so I need to change the output in string format.
I know there is an itoa() function which converts an integer to a string but it is not compatible with all compilers. Can any body tell me what I should do in this scenario?

I am using Ubuntu-10.04 and the g++ compiler.

See http://stackoverflow.com/questions/1218149/arbitrary-precision-arithmetic-explanation/1218185#1218185 — paxdiablo, Apr 25 '11 at 05:53
If your strings are too big, atoi() won't do the trick, your result will be a completely different number.. — amit, Apr 25 '11 at 05:54
@Sayem Ahmed- sir i m trying to implement rsa so i m bound to do this...... — rohitamitpathak, Apr 25 '11 at 06:05

score 5 · Answer 1 · answered Apr 25 '11 at 05:54

5

Since C and C++ do not offer a native type that supports big numbers, it makes no sense to call atoi() to parse such numbers. atoi() returns a native int which is capped at 2,147,483,647 on 32-bit platforms.

You can use one of the numerous bignum libraries, like GMP for instance.

answered Apr 25 '11 at 05:54

Frédéric Hamidi

258,201
41
486
479

I would advise against using GMP for serious stuff. In my opinion, it fails miserably as a general purpose library since out-of-memory errors lead to immediate exit of your program, yanking the rug out from underneath you. It's a very good tool provided you don't mind that little "foible". – paxdiablo Apr 25 '11 at 06:01
@paxdiablo, to their defense, handling that case correctly seems to be [very tricky to do](http://gmplib.org/list-archives/gmp-discuss/2008-December/003479.html). – Frédéric Hamidi Apr 25 '11 at 06:09
My opinion is that they should have handled this from the start. But don't get me wrong, it's a damn fine piece of code other than that. In fast, I "lifted" some of their algorithms to produce a less user-abusive approach for my own code :-) – paxdiablo Apr 25 '11 at 08:55

score 0 · Answer 2 · answered Apr 25 '11 at 05:55

0

I think, the best variant besides using some math libraries is to split those numbers into int arrays with some fixed limit. Then just perform multiplication using basic math multiplication methods. And do not forget about overflows.

answered Apr 25 '11 at 05:55

xappymah

1,624
10
14

score 0 · Answer 3 · answered Apr 25 '11 at 05:55

Multiplying the large numbers is very difficult, however we can do it by applying the logarithm of multiplication of two numbers formula and now we are going know how we derived the product of two numbers’ logarithm.

Let us consider a, m and n are positive real numbers but a does not equal to 1 which means ‘a’ belongs to R+ – {1}. Logarithm of m and n to base a are x and y respectively by satisfying ax is equal to m and ay is equal to n condition.

loga (m.n) = x + y

As we already know x = loga m and y = loga n.

loga (m.n) = loga m + loga n

logarithm of multiplication of two values is equal to summation of the same values’ logarithms. The same logarithmic fundamental can now help us in multiplying the two large numbers by adding the logarithm of those values. If you don’t have a calculator, just take the logarithmic table help to perform this.

This won't help. Since the final result is also large, taking antilog would give a number that won't fit in standard int data type. — Shamim Hafiz - MSFT, Apr 25 '11 at 05:58

score 0 · Answer 4 · edited Apr 25 '11 at 06:02

0

Using atoi() is also not helpful since the number itself won't fit in integer data type.

You have to simulate the method you did in elementary school.

 121
 *23
----
 363
242*
----
2783

The implementation is left as an exercise. You would also need to know how to add big numbers.

edited Apr 25 '11 at 06:02

Tony Delroy

102,968
15
177
252

answered Apr 25 '11 at 05:57

Shamim Hafiz - MSFT

21,454
43
116
176

adding is not a big deal , multiplication showing problem, – rohitamitpathak Apr 25 '11 at 06:09

multiplication of string [ containing integer], output also stored in string, How?

4 Answers4