A bit of Maths and Computational Frustration (376 hits)
Category: NoneRating: 0.4 on 13 reviews (Rate this item) (V)
Submitted by Lee & Tan (View user info) at 2006-09-27 15:04:27 EDT
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, Im 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)
User Reviews
Submitted by fclo002 (user info) at 2006-12-21 12:54:00 EST (#)
Ranking: -2
No Comment
Submitted by CaptainThorns (user info) at 2006-09-28 08:22:55 EDT (#)
Ranking: 1
Umm...uhh...
My cat's breath smells like cat food.
Submitted by Beano312003 (user info) at 2006-09-28 06:28:01 EDT (#)
Ranking: 0
Submitted by OdwinOddball (user info) at 2006-09-27 16:56:07 (#)
Ranking: 0
You're over complicating this.
Don't treat the input as a number, treat it as a string. So the user can just input the number, however long it is, and its stored as a null terminated string. Then, loop thru the string, from right to left, removing the last 3 digits and storing them as their base 1000 counterpart.
Store them in an array of ints. store them in order from 1000 on up. So array entry 1 would be 1000, entry 2 would be 1000x1000, and so on. Thus the array index becomes your exponent when figuring out the number later on.
----------
I was about to say that.
Submitted by JonnyX (user info) at 2006-09-27 18:09:38 EDT (#)
Ranking: 2
you asian guys are smart
Submitted by drgoatcabin (user info) at 2006-09-27 17:09:39 EDT (#)
Ranking: 0
Thanks for reminding me why I fucking HATE math.
Submitted by OdwinOddball (user info) at 2006-09-27 16:56:07 EDT (#)
Ranking: 0
You're over complicating this.
Don't treat the input as a number, treat it as a string. So the user can just input the number, however long it is, and its stored as a null terminated string. Then, loop thru the string, from right to left, removing the last 3 digits and storing them as their base 1000 counterpart.
Store them in an array of ints. store them in order from 1000 on up. So array entry 1 would be 1000, entry 2 would be 1000x1000, and so on. Thus the array index becomes your exponent when figuring out the number later on.
Submitted by COMountain (user info) at 2006-09-27 15:47:30 EDT (#)
Ranking: 0
are you still in remedial math?
...this is child's play.
AND IT'S CALLED A DARK & TAN, DAMNIT.
Submitted by Samo (user info) at 2006-09-27 15:38:39 EDT (#)
Ranking: 0
Wait, I see.
I'm trying to automate this motherfucker, this is the end result:
z13s
z16r
x83i
417
x91y
y23q
y51u
y92f
b7me
313
z23g
z15a
x53d
x52i
b8ze
z18t
z25r
x12a
438
y81e
y21p
b4ku
a4oo
414
x13w
x16s
xyri
Submitted by Gingerly (user info) at 2006-09-27 15:26:28 EDT (#)
Ranking: 2
EXCELLENT post.
... it seems to me that any number above that one which represents the total count of atoms in the cosmos is a completely inconsequential one.
Ok, perhaps not *completely*, but listen to reason:
Because a number is merely a cognitive label and not a *real* entity (though Pythagoras would take issue here), any number above the 80-digit long one you reference above, wouldn't represent anything.
How could it?
Even if you say that it might represent different classifications or 'orders' of all the atoms in existence, the number would then still be smaller than the 80 digit one.
Ok I'm done.
Submitted by Samo (user info) at 2006-09-27 15:23:54 EDT (#)
Ranking: 0
I don't see why you can't just start from the end and check to see if there are three, if so then store the output and move to the next three until the system checking finds only one or two?
Submitted by Wrightcopy (user info) at 2006-09-27 15:20:16 EDT (#)
Ranking: 1
...
<head explodes>
Submitted by retrospect (user info) at 2006-09-27 15:16:46 EDT (#)
Ranking: 0
who hasnt done that?
Submitted by Amontillado (user info) at 2006-09-27 15:08:11 EDT (#)
Ranking: 2
good luck