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.
Division
Again, with division there are several ways to attack it. Recall from your school days that a / b can be expressed as a = q x b + r where q is the quotient and r is the remainder (a and b are the dividend and divisor, respectively).
One can perform division simply by subtracting b from a, q times. This is simple to implement but the number of subtractions can be enormous, resulting in this method taking eons to compute a result.
Alternatively one can proceed as they did in elementary school using long division. Consider the following.
| 5 | 4 | 3 | 2 | 1 | |||||||||
| 4 | 5 | 6 | ) | 2 | 4 | 7 | 7 | 0 | 3 | 7 | 6 | ||
| - | 2 | 2 | 8 | 0 | |||||||||
| 1 | 9 | 7 | 0 | ||||||||||
| - | 1 | 8 | 2 | 4 | |||||||||
| 1 | 4 | 6 | 3 | ||||||||||
| - | 1 | 3 | 6 | 8 | |||||||||
| 0 | 9 | 5 | 7 | ||||||||||
| - | 9 | 1 | 2 | ||||||||||
| 0 | 4 | 5 | 6 | ||||||||||
| - | 4 | 5 | 6 | ||||||||||
| 0 |
where the red signifies we are bringing down that digit from the dividend. In this particular case the remainder is 0 so the quotient evenly divides the dividend. The important thing to note is that this reduces the division to several multiplications and a few subtractions. Rest assured it is much quicker than the subtraction method.
Again a more detailed description can be found here.