Thread: perform basic operations on large numbers algorithm?

is there such an algorithm for doing something like add a large integral numbers in sections?

the reason i ask is in computer science numbers can't be bigger than 2^32, so to emulate operations of a number of 2^256 you have to calcuate it doing many smaller calculations.

now i know that to mulitply two large(positive) numbers you can put them in a box, say 153 * 86 can be represented as (100*80)+(100*6)+(50*80)+(50*6)+(3*80)+(3*6) which is the only idea i have to work this out

basically the result of a small calcuation can't result in a number −2,147,483,648 to +2,147,483,647 (-2^31 to 2^31)

so i guess all calcuations should be done with two numbers below 2^16 so that the outcome can't be greater than 2^32

any help would be apprecitated, this isn't homework or anything just trying to write something?

thanks for your time

Originally Posted by i_heart_pandas

is there such an algorithm for doing something like add a large integral numbers in sections?

Yes, there is, and this is like how you learnt to add numbers at school: Begin from the right. Add the corresponding sections, this gives you a number that fits in a section plus a carry. Then add the carry to the next section (to the left) of any of the numbers you're adding. And do the same for the next section.
To do this, you must be sure that the sum of any two sections + a carry (hence 3 times the maximum number in a section) does not exceed the capacity of the type of variable you use.

For the multiplication, this is the same: like at school, to multiply a by b, first multiply a by the right-most section of b (you do this by multiplying section after section and adding the carries like before), then multiply a by the next section of b, and sum this with the previous result, and so on.
To do this, you must be sure that the product of any two sections + a carry is not too large (you can use another type of variable to store the product before you compute and substract the carry).

Multiplying numbers is a long task, that's why people tried to find faster algorithms. The most efficient one relies on FFT (fast fourier transform), it is much more efficient than the "school algorithm" but more complex to implement.

To take better advantage of the structure of computers, the "sections" are usually defined using the binary expression for a number, and the translation from/to digits (base 10) is done at the beginning/end, once and for all. But it is easier to define sections in base 10 if you want to write a sample program of addition/multiplication of large numbers.

There must be a lot of ressource on the internet about this, you should look for it.

yes thanks, i've looked into these algorithms and found out that they where easier to find than i thought, thanks