big numbers

magic_guy · Post by **magic_guy** » Sat Aug 28, 2004 8:27 am

hi friends

I am green and trying to solve some big number problems. but i am always getting WA.Because my algorithm is not good.
can any body help me about this.I want some perfect big number algrithms such as multiplication ,division or mod operation

hiloshi · Post by **hiloshi** » Sat Aug 28, 2004 9:56 am

Hi, magic.

I using an array of short for big number.
For example, when the big number is 1234567890, the contents of the array are as follows.
array[0]=7890
array[1]=3456
array[2]=12

And same thing as computation on paper is done.
Be careful for carry operation.

magic_guy · Post by **magic_guy** » Sat Aug 28, 2004 10:17 am

addition and subtraction are easy,but multiplication and division are quite difficult

hiloshi · Post by **hiloshi** » Sat Aug 28, 2004 10:00 pm

Multiplication and division are like addition and subtraction.

If you want to calculate Big-number * short, it's very simple.
First, you shoud calculate Big-num[i(0 <= i < n)] * short_value + carry(this is 0 at first)= d.
And the carry is d / 10000, in addition Big-num = d % 10000, and so on.
Time to divison is same as this.

But, if you want to calculate Big-number * Big-number, it's not easy.
Big*Short algorithm is O(n), but Big*Big algorithm is O(n^2).
And (this is a crucial part) you should remember the FIRST Big-number.
It's the same as　computation on paper.
When mulplate 12 * 34, we will do as follows:

4 * 2 + 4 * 10 + 30 * 2 + 30 * 10

When calculate 30 * 12, we have to know the value "12".
But if it does similarly as Big-num * short, we can't know the value "12".
So we have to copy the value "12" to another array.