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

Return to Harry's Home Page

This page accessed times since October 20, 2004.

Page created by: hjsmithh@sbcglobal.net

Changes last made on Saturday, 14-May-05 12:49:16 PDT