A bit of maths, and computing frustrations
I started my weekend contemplating on an experiment to program a calculator that will be able to manipulate large numbers. By large, I was trying to go beyond the 32 bit (4.29 billion) limit for integers. I was hoping for an initial target of 30 digits, well beyond the abilities of an average computer. With the proposed algorithm, the mechanism can be easily expanded to 100 digits, 500 digits, 1000 digits…
Consider our brain. It cannot explicitly handle large numbers. Its limit is probably 10, but with various methods developed in primary school, we can easily manipulate multiple digit numbers. 34562 + 764356, for example. This large number problem is easily solved by doing lining the numbers up and doing the operations column by column. The problem is simplified, although it is a bit more tedious. Nevertheless, it is perfectly reasonable to expect it to be solved in a minute. Similarly, by simplifying a long number into a series of small numbers, I can expect the computer to add numbers of a hundred digits.
It is easy to see that 537 is equivalent to 5×100 + 3×10 + 7×1. Since a computer can work with large numbers, there was no reason to limit it to base-10. Working with larger bases would significantly reduce the number of operations involved. For example, the large number 1,234,567,890 can be expressed as 1×1,000,000,000 + 234×1,000,000 + 567×1000 + 890×1. By expressing it in base-1000, it has been simplified from a 10 digit number to a 4 'digit' number. However, these 'digits' are large- 1, 234, 567 & 890.
To add 2 large numbers, they are lined up in columns, with the 'digits' added, and the excess 1000s carried over to the next column as a 1s. Here, 2 arbitrary large numbers are added:
235921634 + 56365275 = 292286909
235 921 634
+ 56 365 275
292 286 909
Here is the operation detailed in steps. Add the 'digits' of the right most column: 634 + 275 = 909, write 909. Add the 'digits' of the second column: 921 + 365 = 1286, write 286 and carry the excess 1000 over to the next column as a 1. Add the 'digits' of the third column, including any carried 1s: 1 + 235 + 56 = 299.
With this in mind, I proceeded to design my calculator. It will need to take user inputs as a sentence of number symbols, not as a real number. Remember, the computer cannot cope with large numbers. These strings of numeric symbols will be then partitioned into groups like the above example, and then the individual groups converted into numbers. By now, 292 should really mean two hundred and ninety two, not 3 unidentified smears on my monitor.
Here was the major problem of a computer. A human can partition the numbers easily. We draw a line, imaginary or otherwise, across the numbers every 3 digits, right to left. We go on and on, to the 50th digit, 125th digit, 784th digit, till the end. For a computer, you would need to count how long was the user input to establish when you stop partitioning. After that, the individual symbols in the groups had to be converted to numbers, and the relationship between the position and the digit clearly established. In 53154, the 1 is clearly a 100, not 100000. However, this subtle fact is not visible to your average computer. Hence I have to tell it.
So far, I’m still stuck with finding a way of telling the facts to the idiot, in an efficient manner.
That said, I must say that 100 digits is nothing big. While it is doubtful that banks will need 100 digit addition in the near future, mathematics has been on huge numbers for a while. Mathematicians talk of finding billion or trillion digit prime numbers. A particularly interesting number that cropped up in the past is e^e^e^79. It is a number of 10^billion trillion trillion digits. Again, 10^billion trillion trillion is not the number. It is the number of digits in the number. This number is known as Skewes’ Number, the largest number ever to emerge in natural mathematics at the time of its discovery (1933). In contrast, the number of atoms in the cosmos is estimated to be only of the order of 80 digits. (Derbyshire, 236)
References:
John Derbyshire, Prime Obsession- Bernhard Riemann and the greatest unsolved problem in mathematics, 2003
Consider our brain. It cannot explicitly handle large numbers. Its limit is probably 10, but with various methods developed in primary school, we can easily manipulate multiple digit numbers. 34562 + 764356, for example. This large number problem is easily solved by doing lining the numbers up and doing the operations column by column. The problem is simplified, although it is a bit more tedious. Nevertheless, it is perfectly reasonable to expect it to be solved in a minute. Similarly, by simplifying a long number into a series of small numbers, I can expect the computer to add numbers of a hundred digits.
It is easy to see that 537 is equivalent to 5×100 + 3×10 + 7×1. Since a computer can work with large numbers, there was no reason to limit it to base-10. Working with larger bases would significantly reduce the number of operations involved. For example, the large number 1,234,567,890 can be expressed as 1×1,000,000,000 + 234×1,000,000 + 567×1000 + 890×1. By expressing it in base-1000, it has been simplified from a 10 digit number to a 4 'digit' number. However, these 'digits' are large- 1, 234, 567 & 890.
To add 2 large numbers, they are lined up in columns, with the 'digits' added, and the excess 1000s carried over to the next column as a 1s. Here, 2 arbitrary large numbers are added:
235921634 + 56365275 = 292286909
235 921 634
+ 56 365 275
292 286 909
Here is the operation detailed in steps. Add the 'digits' of the right most column: 634 + 275 = 909, write 909. Add the 'digits' of the second column: 921 + 365 = 1286, write 286 and carry the excess 1000 over to the next column as a 1. Add the 'digits' of the third column, including any carried 1s: 1 + 235 + 56 = 299.
With this in mind, I proceeded to design my calculator. It will need to take user inputs as a sentence of number symbols, not as a real number. Remember, the computer cannot cope with large numbers. These strings of numeric symbols will be then partitioned into groups like the above example, and then the individual groups converted into numbers. By now, 292 should really mean two hundred and ninety two, not 3 unidentified smears on my monitor.
Here was the major problem of a computer. A human can partition the numbers easily. We draw a line, imaginary or otherwise, across the numbers every 3 digits, right to left. We go on and on, to the 50th digit, 125th digit, 784th digit, till the end. For a computer, you would need to count how long was the user input to establish when you stop partitioning. After that, the individual symbols in the groups had to be converted to numbers, and the relationship between the position and the digit clearly established. In 53154, the 1 is clearly a 100, not 100000. However, this subtle fact is not visible to your average computer. Hence I have to tell it.
So far, I’m still stuck with finding a way of telling the facts to the idiot, in an efficient manner.
That said, I must say that 100 digits is nothing big. While it is doubtful that banks will need 100 digit addition in the near future, mathematics has been on huge numbers for a while. Mathematicians talk of finding billion or trillion digit prime numbers. A particularly interesting number that cropped up in the past is e^e^e^79. It is a number of 10^billion trillion trillion digits. Again, 10^billion trillion trillion is not the number. It is the number of digits in the number. This number is known as Skewes’ Number, the largest number ever to emerge in natural mathematics at the time of its discovery (1933). In contrast, the number of atoms in the cosmos is estimated to be only of the order of 80 digits. (Derbyshire, 236)
References:
John Derbyshire, Prime Obsession- Bernhard Riemann and the greatest unsolved problem in mathematics, 2003
posted by Tan Yee Wei at 3/13/2005 01:30:00 am
<< Home