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