Monday, January 5, 2009

Particularities of PI

The occurrence of the sequence 0123456789 within tex2html_wrap_inline145 .

In his primer on Intuitionism, Heyting [5] frequently relies on the occurrence or non-occurrence of the sequence 0123456789 in the decimal expansion of tex2html_wrap_inline145 to highlight issues of classical versus intuitionistic (or constructivist) mathematics.gif

At the time that Brouwer developed his theory (1908) and even at the time that [5] was written, it seemed well-nigh impossible that the first occurrence of any 10 digit sequence in tex2html_wrap_inline145 could ever be determined.

The confluence of faster computers and better algorithms, both for tex2html_wrap_inline145 and more importantly for arithmetic (fast Fourier transform based, combined with Karatsuba, multiplication (see [3])) have rendered their intuition false. Thus, in June and July 1997, Yasumasa Kanada and Daisuke Takahashi at the University of Tokyo completed two computations of tex2html_wrap_inline145 on a massively parallel Hitachi machine with tex2html_wrap_inline175 processors.gif The key algorithms used are as in the recent survey in this Journal [1], with the addition of significant numerical/arithmetical enhancements and subtle flow management.

During their computational tour-de-force, Kanada and Takahashi discovered the first occurrence of 0123456789 in tex2html_wrap_inline145 beginning at the 17,387,594,880th digit (the `0') after the decimal point. It is worth noting that years become hours on such a parallel machine and also that the effort of multiplying two seventeen billion digit integers together without FFT based methods is also to be measured in years. The underlying method reduces to roughly 300 such multiplications ([3],[2]). Add the likelihood of machines crashing during a many-year sequential computation. Hence without fast arithmetic and parallel computers, Brouwer and Heyting might indefinitely have remained safe in using this particular and somewhat natural example.

We may emphasize how out of reach the question appeared even 35 years ago with the following anecdote. Sometime after Shanks and Wrench computed 100,650 places of tex2html_wrap_inline145 (in 1961 in 9 hours on an IBM 7090), Philip Davis asked Dan Shanks to fill in the blank in the sentence ``mankind will never determine the tex2html_wrap_inline189 of tex2html_wrap_inline145 .'' Shanks, apparently almost immediately replied ``the billionth.''

next up previous
Next: The use of 0123456789 Up: No Title Previous: No Title


No comments:

Post a Comment