92/06/27
To: Dr. Clifford A. Pickover,
From: Harry J. Smith, 19628 Via Monte Dr., Saratoga, CA 95070
Dear Cliff,
In your book Computers and the Imagination, page 380, you
offered an award. I quote you: "An award of 50 dollars is offered
by the publisher for a printout of the largest Juggler number
computed by a reader. . . The award will be given on or about
September, 1993, . . . Currently, the largest juggler number
computed is a 45,391-digit giant for the starting number 30817. It
was computed by Harry J. Smith. . .."
I have now computed a larger juggler number. It is a 972,463-
digit super giant for the starting number 48443. Using my notation
for documenting large juggler sequences, the sequence is:
x(0) = 48443 (5)
x(1) = 106,62193 (8)
. . .
x(60) = 17834,...,78952 (972463)
. . .
x(157) = 1 (1)
Length = 158
I am including with this letter the complete sequence in this
notation. Also included is a single page format of x(60) and a
printout of the first and last to pages of a WordPerfect file
containing the complete number. I have not printed the entire
number, it would take 360 pages. Do I need to send you the
complete hard copy printout of these 360 pages to claim the award?
Do you want me to send you a diskette containing the number?
The software package I used to perform the multiple precision
integer arithmetic is a new package I wrote in the object-oriented
programming (OOP) Turbo C++ for Windows Version 3.0, by Borland
International, Inc. The program ran in Microsoft Windows 3.0,
later upgraded to 3.1. My computer is an IBM AT compatible 33 Mhz
486 with 16 Megabytes of RAM and a 330 Megabyte hard disk drive.
The research and development I had to do to compute this
number on a PC was quite interesting. I knew from my earlier work
that starting from x(0) = 48443 produced a very large juggler
number because my program ran out of memory while computing this
sequence. Actually, what was happening was that the numbers were
getting too large to be held in a Turbo Pascal array. In Turbo
Pascal, arrays are limited to 65536 bytes. I knew that Turbo C
could handle what they call huge arrays and huge pointers to these
arrays, and the index to these arrays can be a 31 bit integer.
Since my program was written in an object-oriented programming
language, it needed to be converted to C++.
The Turbo C++ program extended the juggler sequence (starting
at x(0) = 48443) a little farther but it soon ran out of the 640K
byte limit of DOS. This forced me to move up to Turbo C++ for
Windows. In the Windows' environment C++ can use the 16 megabytes
of RAM in my system and about 20 megabytes of virtual memory from
the hard disk.
Now that the memory problem was hopefully solved, what was the
next problem? . . . Running time! On an up step, the new number
has 1.5 times as many digits as the previous. On two consecutive
up steps the second step takes 2.25 times as long to compute as the
first. It would sometimes take a week to compute the next number
in the sequence.
A few years ago I developed an algorithm that used the Fast
Fourier Transform (FFT) to speedup a multiple precision integer
multiply. The algorithm ran in the order of nLog(n) time instead
of n^2, but the overhead was too great. The algorithm was not
practical for numbers that would fit in the machine I was using.
The juggler sequence was getting into the range where the FFT
would help speed up the multiply operations. The multiple routine
was changed to use the FFT when numbers were large enough for the
FFT to speed up the process. Next problem? . . . The square root
routine was too slow on these very large numbers. It too, had a
running time of the order of n^2. I could convert the square root
routine to use Newton's method for root-finding, but that requires
a long divide on each iteration, x = (x + a/x)/2.
The divide routine for large numbers was changed to compute
a/b by first computing 1/b and then multiplying a * (1/b). This
was done because the Newton's method for solving for the result of
a divide requires a divide itself. The new routine for the
reciprocal r = 1/b was done with a Newton's method that only used
multiplies, an add, and a subtract, r = r+r - b*r*r.
This was the end of the problem solving. I now had a program
that could take the square root of a 2,000,000-digit number and all
long operations were of the order of nLog(n). The entire juggler
sequence starting from 48443 was computed in 28 hours.
I am including some documentation I did with the program
Mathcad 3.1 for Windows. This shows a graph of the running time of
the multiply routines.
Sincerely,
Harry
times since October 20, 2004.