1A Spigot Algorithm for the Digits of Pi

It is remarkable that the algorithm illustrated in Table 1, which uses no floating-point arithmetic, produces the digits of π. The algorithm starts with some 2s, in columns headed by the fractions shown. Each entry is multiplied by 10. Then, starting from the right, the entries are reduced modulo den, where the head of the column is num/den, producing a quotient q and remainder r. The remainder is left in place and q × num is carried one column left. This reduce-and-carry is continued all the way left. The tens digit of the leftmost result is the next digit of π. The process continues with the multiplication of the remainders by 10, the reductions modulo the denominators, and the augmented carrying. TABLE 1. The workings of an algorithm that produces digits of π. The dashed line indicates the key step: starting from the right, entries are reduced modulo the denominator of the column head (25, 23, 21,..., resp.), with the quotients, after multiplication by the numerator (12, 11, 10,...), carried left. For example, the 20 in the 919 ’s column yields a remainder of 1 and a left carry of 1 · 9 = 9. After the leftmost carries, the tens digits are 3, 1, 4, 1. To get more digits of π one must start with a longer string of 2s. Reprinted from The American Mathematical Monthly, 102(1995)195–20