↑ AbscissaMantissaSchmisha
Page Created: 6/25/2014 Last Modified: 6/14/2022 Last Generated: 10/22/2024
In 1989, one of my friends who was studying for a dual major in Electrical & Computer Engineering at Boston University said he was assigned a difficult project, to write a program to compute the factorial of 255. He said his class was given two weeks to complete this project.
He knew that I was obsessed with the Commodore64, but he thought he was in the big leagues at Boston using a more powerful IBM PC-compatible computer that I could not afford.
I said "I can do this on a Commodore 64 in 1 day."
"No way!" he said. "If you can do that, I will buy you dinner!" He said he would stop by the next day.
So I spent the rest of the day, and worked all night into the early hours in the morning to prove him wrong. I was also envious that he was bragging that he visited Isaac Asimov in his Boston University office and obtained his autograph. We were both Asimov fans.
Around 3 am, I ran the program, but I didn't know how many hours it would need to run (hoping it would be done by late morning) nor know how big the number would actually be (hoping it wouldn't exceed the RAM that I allotted for its processing), so I had it save the giant number to floppy disk and went to sleep.
If you're not familiar with performing math on a computer, mathematical operations are limited in size to a certain number of bytes. When numbers exceed that size, the computer only approximates to a limited amount of significant digits, like a calculator does when the number exceeds the screen size. But the task was to compute it exactly, not approximate it, and the factorial of such a number is huge.
My friend did not think I realized this, since he was just learning it himself, and even so, it is fairly difficult to overcome. What he didn't realize what that on my own, I was trying to compute Pi to thousands of digits and perform Public Key cryptography on the Commodore 64 based on an article I read in Scientific American called "The Mathematics of Public-Key Cryptography" by Martin E. Hellman, and cryptography uses very large numbers. Even so, I had never done it until then.
I didn't learn about recursion until years later, and the factorial can be computed using a recursive algorithm, but Commodore 64 BASIC variables are all global in scope, so recursion would require some tricks. And even if I knew how to do this, I would still have needed somewhere to store those gigantic numbers, which was the primary problem.
Awakening to the bright daylight, I checked and it was done processing. When my friend showed up, I showed him my program and the output via the sequential file.
I said, "I don't know if it is correct, since it ended with all of these zeros."
He then frowned and said "No, I think it is correct. It is supposed to end with a lot of zeros."
He then bought me dinner.
He couldn't understand how I did it and I explained to him that I created large arrays to hold the digits and simply performed a long multiplication algorithm on them. He was taught some other method of accomplishing this, but thought my method was clever.
I never knew if I was really right, but I just checked while writing this page, and Wolfram Alpha↗ concurs.
The Commodore 64, back in 1989, took several hours, but computed this:
Wolfram Alpha in 2014, in just a few seconds, computed this:
Wolfram Alpha LLC. 2014. Wolfram|Alpha. http://www.wolframalpha.com/input/?i=255!
They are an exact match.
My friend was no slouch. He was a gifted student, the captain of my cross-country team, and I greatly admire him. He went on to become a captain in the US Army Special Forces. But this was one of my greatest personal victories, since I was still stuck in the prison of Calculus Monte Cristo and was being mocked for still using a Commodore 64 in the PC era.
Here is my source code.
Comments