Site Info

Authors
  • H.Koenig
  • Adam Goucher
  • Dave Greene

« Sprouts and parasites | Main | Turing machines »

2011 January 09

Engineered Objects
Phi and pi calculators

Overview of phi calculator
Blueprint for Adam P. Goucher's calculators -- the diagram for the
phi calculator is shown here, but the pi calculator is very similar.
Decimal output is displayed in the upper right corner.

In mid-February 2010, Adam P. Goucher announced the completion of a large Life pattern that could calculate the decimal digits of phi (the golden ratio): 1.61803398874989484820... This was followed a week later by a similar pattern that output the digits of pi. The pi calculator was the embodiment of a 40-year-old speculation by John Conway about the feasibility of a pi-printing pattern.

Macrocell file for phi calculator (copy and paste into Golly, or open the file from Golly's File menu)

Macrocell file for pi calculator

sample output from Adam P. Goucher's phi calculator
The first 16 digits displayed
by the pi calculator
sample output from Adam P. Goucher's phi calculator
The first 7 digits displayed
by Adam P. Goucher's phi calculator
A common feature of the two calculators is the printer attachment, which accepts input on eleven glider lanes (for digits 0 through 9 plus a decimal point) and produces readable output on a SW-NE diagonal, when the pattern is zoomed out sufficiently far (individual pixel-blocks in the digits are actually separated by 64 cells diagonally, so the output is easily readable at scales around 2^5:1, as shown.

The phi pattern is a standard square root calculator (for sqrt(5)/2, with the initial 1.6 hardcoded). The algorithm is encoded in an array of several thousand stable glider reflectors and splitters. A glider cycles through these reflectors to execute a program with 177 possible states, producing output gliders representing each new digit.

The pattern runs in O(n^2) time in practice -- it's actually O(n^3) in the long run, but only after a thousand digits have been generated. At that point the memory tapes in the northeast have grown long enough to take noticeably longer to access their bits.

The pi calculation uses an infinite product series, programmed into a very similar array of stable reflectors, but in this case there are 188 possible states, and the program runs in O(n^4) time at first and O(n^6) time eventually, due to the higher complexity of the calculation as well as the memory-tape speed limitation.

The printer design is very simple and easily adapted to other uses, such as a hexadecimal printer with alphanumeric characters A-F added, similar to the extended printer in the fine-structure-constant-generating pattern that appeared at the beginning of April.