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

This question already has answers here: Closed 11 years ago.

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 i开发者_如何学Pythons 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.

---

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.

---

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.

---

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.

---

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.