Atari 520 ST and the Decimal Expansion of Fermat 9.

In 1990 Dr. Arjen Lenstra published the factorization of Fermat's 9th number. At the time, the commercially available Arbitrary Integer Arithmetic was Mathematica, with a decimal expansion limit of 99 digits. He published the factors of the 155 digit number, having 7 digits, 49 digits and 99 digits respectively.

I had an Atari 520ST with 4MB of RAM, screaming along at 8 MHz, when IBM compatibles were limited to 6 MHz. The Atari, with its Motorola 68030 processor had a true 32 bit bus, while IBM compatibles were making a 16 bit bus do double duty for long ints.

I wrote a small program named "Muncher," in (compiled) GFA Basic to multiply the factors, and expand Fermat's 9th number in decimal. 

To do so, I employed the Trachtenburg algorithm, taking each digit as a tuple, multiplying two numbers together at a time. The principle was to multiply the connected set of digits together, keeping track of the power of ten, and then add the columns vertically, in an array. In the process, I wrote procedures for addition and subtraction.

It was not very efficient using memory, and I was able to improve "Muncher," by modifying the code to take three digit tuples*, instead of one digit tuples. The 32 bit register was capable of squaring a three digit number with ample room left over for addition in a column. It would square some four digit tuples, but not all, and then there would be a question of the register being able to carry the overflow in each column as it added them up. The resulting program, I named "Cruncher." 

Not satisfied that multiplying the factors together and coming up with Fermat 9 was enough (I had no published decimal expansion for reference,) I wrote a procedure to do long division as well. This entailed taking the divisor, and building a table of each multiple, 0 thru 9, such that I could take the length of the divisor+1 from the dividend, and look up the resulting digit from the answer, by comparing the two strings until I found the first multiple that exceeded the nibble, and choosing the digit corresponding to the previous multiple, 0 if necessary. That digit became the first digit of the answer. I then subtracted the table value from the "nibble" of the dividend, read the necessary nibble of the dividend, and repeated the process, building up the resulting answer concatenating left to right. When I got to the end, the leftover divisor was the integer remainder.

The division routine, while not elegant, was not limited by the array size, and I could check the division of numbers that I could not verify except by the program. It was even pretty quick, but I never expanded it to three digit tuples, since that would have entailed building a table of some 1000 products of the divisor.

Using Cruncher, I was able to expand up to Fermat 13, in 4 MB of RAM, storing the intermediate products on a 1.44 MB floppy disk.

As I recall, I was able to expand Fermat 13 in less than 300 seconds.

In 2000, I published the accomplishment on the alt.hacker IRC news group, although my explanation of division could have been clearer.

Later, I expanded F14, F15 and F16 using SAGE, but that was long after the Atari and GFA Basic.

Updated 12/03/2021

Tuples were discovered by Dr. Nowell of Auburn University at Montgomery, in Alabama (AUM) and found their first application in Graph theory. Calling a three digit nibble of an integer a "tuple," may be taking license,  but it may be a valid application of the concept. Likewise, considering a part of an equation, say a polynomial, and calling (6x) or (x^2) a tuple, and using it in the place of a single x in a variation of the same equation is another application of the same concept.

Ex: x^6 + x^3 is also (x^2)(x^3 + x), where x is a tuple and x^2 is a tuple. While apparently trivial, this may have application against Integral tables, especially when employing object oriented programming to analyze them for application.