|CALCULATING MANY DIGITS OF PI|
Message #1 Posted by Gene Wright on 19 Mar 2004, 9:40 a.m.
Gene: This is a write-up I just received from Palmer Hanson, who edited the TI PPC Notes for many years in the 1980s - early 1990s. Thought it might be interesting. Looks like the race to 1000 digits on a machine prior to 1990 now belongs to TI? Can we beat the 5.81 hours on the TI95 with the HP71B? :-)
CALCULATING MANY DIGITS OF PI
by Palmer Hanson, editor of TI PPC Notes
Students of calculus may remember that converging series can be used for calculation of trigonometric and exponential functions; e.g.,
sin(x) = x - x^3/3! + x^5/5! - x^7/7! + ...
pi = 4(1 - 1/3 + 1/5 - 1/7 + 1/9 - ...
where the series for sin(x) converges rapidly but the series for pi converges very, very slowly. That equation for finding pi is ascribed to Leibniz and is a special case of the series for finding the arc tangent
arctan(x) = x - x^3/3 + x^5/5 - x^7/7 ...
evaluated for x = 1/4 radian. For more rapid convergence pi may be calculated as the sum of two arc tangents
pi = 16*arctan(1/5) - 4*arctan(1/239)
In June 1980 the PPC Calculator Journal (V7N5P9-11) presented an HP-41 program by Ron Knapp which would calculate 1000 digits in 11.5 hours and 1160 digits of pi in 15.25 hours. Editor Richard Nelson wrote to Maurice Swinnen, the editor of TI PPC Notes, saying "... if the TI-59 club wants to accept a real challenge, compute the first 1,000 digits of pi in less than 11 hours, 30 minutes. Printout time of the answer need not be included." The challenge was repeated in the "Calcu-Letter" column of the July 1981 issue of Popular Science. A revised version of Ron's program which would calculate 1000 digits of pi in 8.5 hours was published in late 1981 (V8N6P69 of the PPC Calculator Journal). There was no response in the pages of TI PPC Notes until mid 1982 when Bob Fruit submitted a program which would find 460 digits in 6 hours 18 minutes (V7N4/5P26). The size of the TI-59 memory prevented calculation of additional digits using Bob's method. Bob's program runs in three stages. The first stage enters fast mode and calculates the value of 16*arctan (1/5). The second stage calculates the value of 4*arctan(1/239) and subtracts it from the value found in the first stage. The third stage formats and prints the results. It seemed likely that the TI-59 programmers would not be able to overcome the advantage of the larger memory and faster speed of the HP-41. Bob's submission also included a table of the first 10,000 digits of pi (V7N4/5P28).
In February 1983 TI PPC Notes (V8N1P21) reported that Jovan Puzovic of Yugoslavia had found a way to calculate 1188 digits of pi with a TI-59, but even with his program running in fast mode the solution required eighty hours. The program uses the same equations as that of Bob Fruit and proceeds in three stages. First the arctan(1/5) portion is calculated and stored on magnetic cards. This requires about 62 hours. Second, the arctan(1/239) is calculated and stored on magnetic cards. That requires an additional 18 hours. Finally, a short routine combines the two intermediate solutions. It seemed likely that 1188 digits was about as much as could be obtained considering the memory limitations of the TI-59.
In April 1983 TI PPC Notes (V8N2P4) reported that the French scientific journal Science et Vie had published a program by Renaud de La Taille which could deliver 1287 digits of pi on a TI-59. The solution occupies 13 digits per data register times 99 registers for the total of 1287 digits with only one data register (R00) reserved for dsz control. The program is painfully S - L - O - W ; it runs for 24.55 days! In June 1983 TI PPC Notes (V8N3P8) published the program and instructions for its use. In August 1983 TI PPC Notes (V8N4P21) published a Maurice Swinnen's translation of the Science et Vie article which explained the method of calculation as follows:
"The entire art consists of finding the right formula in order to design a short and simple program, and to use the largest possible number of memory registers. ... ... start with the series
pi/2 = 1 + 1/3 + (1*2)/(3*5) + (1*2*3)/(3*5*7) + (1*2*3*4)/(3*5*7*9) + ...
Thus, pi/2 = ((...((2n/(2n+1) + 2)(n-1)/(2n-1) + 2)(n-2)/(2n-3) + 2)(n-3)/...)1/3 +2
This method avoids the addition of terms in the series to the preceding sums. The resulting program contains only a multiplication and a division. ..."
The same issue of TI PPC Notes presented Palmer Hanson's modification of the Science et Vie program to run in fast mode and complete the calculations in 13.39 days. Palmer's modification also provided automatic calculation of the number of registers and iterations to be used when calculating fewer than 1287 digits. Correspondents of Science et Vie used similar techniques with other programmable calculators and reported the following results
250 digits of pi on an HP-67
576 digits of pi on a TI-58
and, finally, 3600 digits of pi on an HP-41, a calculation which requires four months! The longest continuous calculation for a TI-59 may have been a search for "amicable numbers" by Bob Fruit. V8N5P13 of TI PPC Notes reported that he ran his search program for 2662 hours -- nearly 111 days. If nothing else the successful completion of calculations which extend to more than one hundred days attests to the reliability of the devices used.
In 1986 Robert Prins of the Netherlands published a book "Extended Precision Programs for the TI-59". He included a modification of Jovan Puzovic's program which allowed the user to calculate fewer digits than 1188 and a minor modification of the fast mode version of the Science et Vie program. He also included a TI-66 program which could calculate 494 digits of pi in about 7.5 days
In mid 1987 Hewlett Ladd reported that he had translated the Science et Vie TI-59 program for use with the TI-95. His translation would calculate up to 1573 digits. He did not report run times at that time. His program was resurrected for this historical account. It will deliver 1000 digits of pi in 40.95 hours. .
An HP-32SII program by Katie Wasserman which will calculate 99 digits of pi in 11 minutes appears at hpmuseum.org as Articles Forum No. 281 submitted in June 2002. That program uses a different formula for pi
pi = 20*arctan(1/7) + 8*arctan(3/79)
One might think that a savings in execution time would result because the first term would converge more rapidly; however, the second term will converge more slowly such that the total execution time will be expected to be very similar to that with the equation used by Knapp, Fruit and Puzovic.
In early 2004 Palmer Hanson noted that the five-fold increase in speed of Hewlett Ladd's translation of the TI-59 Science et Vie program for the TI-95 suggested that a conversion of Bob Fruit's TI-59 program for use on the TI-95 might yield results which were faster than the Knapp programs on the HP-41. That turned out to be true. The resulting program will deliver 30 places in 30 seconds, 90 places in 3 minutes 5 seconds, 99 places in 3 minutes 43 seconds, 200 places in 13 minutes 35 seconds, 460 places in 1 hour 8 minutes, 1000 places in 5.81 hours, 1160 places in 7.72 hours and 2070 places in 24.61 hours.
Other discussions of methods for finding or remembering pi were reported in later issues of TI PPC Notes:
V8N5P10 reported that George Thomson had recognized the editor's fascination with pi by addressing letters to "Palmer Pi Hanson" and passing on a mnemonic for remembering the first thirty digits of pi which had appeared on page 309 of the April 1969 issue of Datamation, where one counts the letters in each word to obtain each successive digit of pi.
Now I, even I, would celebrate in rhymes inept,
The great immortal Syracusan, rivaled nevermore,
Who in his wondrous lore passed on before,
Left men his guidance how to circles mensurate.
V10N1P14/15 discussed a method for finding pi through the use of random numbers which appeared in A. K. Dewdney's column "Computer Recreations" in the April 1985 issue of Scientific American. The analogy is to a cannon firing into a square field which includes an inscribed circular pond. If the cannon is fired many times and the hits are distributed uniformly over the area of the square then the ratio of the number of hits in the pond to the total number of hits in the square should approach the ratio of the area of the circle to the area of the square which is pi/4. The simulation on a calculator or a computer is performed by using a random number generator to determine the position of each hit. Clearly, such a method for finding pi depends upon the quality of the random number generator. John Von Neumann's admonition that "Anyone who considers mathematical methods of producing random numbers is, of course, in a state of sin" (Donald Knuth's The Art of Computer Programming, Vol. 2, page 1) may be applicable here.
V10N3P4 noted that approximating pi with the fractions 22/7 or 355/113 was a well known technique. Ron Wagner had obtained another technique known as the Hick's (or maybe Hicks) method at a computer trade show. Divide 2143 by 22 and take the square root two times. On the TI-59 the fraction 22/7 yields three correct digits, the fraction 355/113 yields seven correct digits and the Hick's method yields nine correct digits where the tenth digit is within one of the tenth digit displayed for pi. On the HP-41 the Hick's method yields 3.141592653 which is within one in the tenth digit of the value of pi used in that device.
V10N4P26 reported that Larry Leeds had used a decimal to fraction converter on his Model 100 to search for fractions and fractions followed by square roots which would return the first thirteen digits of pi. He found three fractions: 4272943/1360120, 5419351/1725033 and 61905677/19705189,. He also found three fractions followed by a square root: 3044467/308469, 17007401/1723210 and 26140802/2648617. He did not find any fractions which when combined with two square roots would yield thirteen correct digits of pi. The first thirteen digits of pi 3.14159 26535 89 (obtained by truncation) are NOT the same as the rounded value 3.14159 26535 90 which is obtained in response to the pi key on the TI-59, TI-66 and TI-95. It is more than a little curious that the TI-59 and TI-66, which use truncated thirteen digit arithmetic, store an internal value for pi which is a thirteen digit rounded value. It seems likely that memorizing thirteen digits of pi would be easier than memorizing any of those methods.
The discussion in V10N4P26 also proposed a simple-minded search which would compare the decimal equivalent of fractions against the value of pi (or any other number to be converted) loaded to the accuracy of the machine. Start with the fraction 1/1. If the value of the fraction is greater than the decimal to be converted then add a 1 to the denominator and try again. If the value of the fraction is less than the number to be converted then add a 1 to the numerator and try again. Sample programs for a CC-40 were included. Use of the simple minded search on a TI-95 yields two fractions of interest. 5419351/1725033 = 3.14159 26535 8985 ... which becomes 1E-12 less than the defined value on machines that truncate to thirteen digits such as the TI-59 and TI-66, and which becomes the defined value on machines that round to thirteen digits such as the TI-95 and 6565759/2089946 = 3.14159 26565 9009 ... which becomes the defined thirteen digit value whether truncated or rounded. The same technique on an HP-41 yields fractions such as 104348/33215 and 209051/66543 which will yield the ten digit value used for pi on that device.