Big Integer in Array


Algorithm:
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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s