Large Integer Arithmetic. Addition, Subtraction, Multiplication and Division
Computers generally store integers as binary numbers in a byte, word of double word and have instructions to perform the basic arithmetic operations such as addition, subtraction, multiplication and division. This all works just fine until the numbers exceed the range that can be held in a word (32 bits) or double word (64 bits). This only allows for integers up to about 4.3 billion or 18.5 quintillion which is not very large in the grand scheme of numbers.
In order to handle larger numbers, software algorithms piece together bytes, words or double words to create an object which can hold an almost unlimited number of digits (unlimited up to the constraints placed on it by the amount of computer memory available). Two methods immediately pop into one’s mind. First one could piece together words or double words to create a very large binary number.
For example take one 32 bit word and follow it with several more to create
|
|
|
|
||
This gives us the equivalent binary number of: |
||||
|
|
||||
So we end up using three computer words for this particular number.
Alternatively we can utilize 8 bit bytes and store one digit in each byte. This means the same number above would take 96 bytes, or 24 (32 bit) words to store vs the 3 for the above.
|
|
|
|
|
|
There are advantages and disadvantages to both methods.
Addition and Subtraction
So how do we add these large numbers? The basic algorithm is almost the same in both cases. One starts with the lower order digit (or word) of one number and adds it to the lower order digit (word) of the second. Then do the same computation with the next lowest digit (word). Just like learned in first grade. Carries from a previous addition are added in to the next addition. This is fairly simple and straightforward.
Subtracting is done by simply negating one number and adding it to the other. So x – y becomes x + (-y). Essentially subtraction is nothing more than addition.
Multiplication
Again multiplication is handled similarly in both cases although there are several different algorithms to perform the actual multiplication. First we can multiply one number by another by simple addition remembering that m x n is really m + m + m … + m, n times. So one big multiplication is reduced to n - 1 big additions (n rows of numbers means n - 1 additions).
Another way to perform multiplication is the way one learned in grade school. Start with the lower order digit (word) of one number and proceed to multiply each digit (word) of the other number by it. Then take the next lower order digit (word) and do the same, this time placing the resulting number one digit (word) to the left of the first result. Continue doing this until all the digits (words) have been multiplied.
| 5 | 4 | 3 | 2 | 1 | ||||||
| x | 4 | 5 | 6 | |||||||
| 3 | 2 | 5 | 9 | 2 | 6 | |||||
| 2 | 7 | 1 | 6 | 0 | 5 | |||||
| + | 2 | 1 | 7 | 2 | 8 | 4 | ||||
| 2 | 4 | 7 | 7 | 0 | 3 | 7 | 6 |
This reduces one large number multiplication into a number of smaller multiplications capable of being done by the computer’s intrinsic instructions for multiply and a number of additions. A more detailed description can be found here.
Additional algorithms exist which purport to shorten the compute time by reducing the number of multiplications. One, the Karatsuba method, is explained here.
Division
We'll skip over division since it is not defined for integers. Multiplication is defined since n x m is an integer. However, although n / m is an integer for some n's and m's it is not an integer for all of them. Look at 2 / 3. Not an integer.