/*
Topic Submitted by : Gultu
Dept. : CTE
Institution : United International University
Submitted at : 01/11/09
*/
Often we have to calculate the value of 100! or 1000! or 2^1000.
Surely, it’s a very large value even for double/long double. One of the efficient way is to split the value in array. In next few paragraphs we are going to discuss the process. You can use this process in manipulating,
1. Big Integer Addition
2. Big Integer Subtraction
3. Big Integer Multiplication
4. Factorial of 1000!, 10000!……….
5. Combination nCm (tho combination have another more efficient algorithm, we will discuss later)
6. Exponential value i.e. 2^1000, 1000^1000………..
and many mores.
Lets start……..
Suppose, we are calculating 1234 * 999. Let, A = 999
1234
x A
3996 (4 * A = 4 * 999 = 3996)
2997 (3 * A = 3 * 999 = 2997)
1998 (2 * A = 2 * 999 = 1998)
0999 (1 * A = 1 * 999 = 999)
Now, 3996 + 2997 + 1998 + 999 = 1232766
1. Split the Number 1234 in an Array. u can use string to take the value and then just subtract 48, to convert it into integer. Or, u can use (atoi) function in C/C++.
1 | 2 | 3 | 4 |
2. Now, we multiply First Index with 999 and keep the carry in hand, I.e
999 * 4 = 3996
Assign (3996 % 10) in the First index (by replacing 4) and keep the (3996 / 10 = 399) in Carry. Array will look like,
1 | 2 | 3 | 6 |
Carry = 399
3. Second Index * 999 = 3 * 999 = 2997 + Carry = 2997 + 399 = 3396
Assign (3396 % 10) in the Second index (by replacing 3) and keep the (3396 / 10 = 339) in Carry.
1 | 2 | 6 | 6 |
Carry = 339
4. Third Index * 999 = 2 * 999 = 1998 + Carry = 1998 + 339 = 2337
Assign (2337 % 10) in the Third index (by replacing 2) and keep the (2337 / 10 = 233) in Carry.
1 | 7 | 6 | 6 |
Carry = 233
5. Forth Index * 999 = 1 * 999 = 999 + Carry = 999 + 233 = 1232
Assign (1232 % 10) in the Forth index (by replacing 1) and keep the (1232 / 10 = 123) in Carry.
2 | 7 | 6 | 6 |
Carry = 123
6. All index are multiplied by 999 successfully. Concatenate Carry with the Array.
For instance, our array values are 2766 and Carry = 123
So, final output: 1234 * 999 = 1232766.
/*
Solution Submitted by : Gultu
Dept. : CTE
Institution : United International University
Submitted at : 02/11/09
*/