8th grade science fair project: estimating π with TT

[stoneformation]

Hi, all. This is our first post! We’re excited to be here, although we’ve been lurking in the Community for a while. It all started with a science fair idea…

How would you go about estimating the irrational number Pi, if you couldn’t use a modern calculator or even pencil and paper? What if you just had a mechanical calculator, either something that already exists (abacus, adding machine, slide rule, Curta, etc.) or something you could build yourself? What formula/algorithm would you use? How many digits could you calculate? What challenges would you encounter along the way?

We have actually been working on this for a while, and we are heading down the road of using the Turing Tumble for this project. The Rabinowitz/Wagon spigot algorithm for Pi is pretty well-suited for this, as it avoids the convergence issues associated with many infinite series-based approaches, and it doesn’t require the computation of square roots, trigonometric functions, or floating-point division. This approach can be used to calculate each successive base-10 digit with very little additional memory, and the arithmetic is all pretty basic. To compute 20 decimal digits, you never need to handle numbers larger than 2350, which will conveniently fit in 12 binary digits.

Before selecting the TT for the hardware, we acquired a vintage 30s-era Burroughs full-keyboard adding machine, an Addometer, a Produx, and a Pickett slide rule. All of these are base-10 tools, and might have been used in conjunction to implement various algorithms. One option that we considered was an adaptation of the Nilakantha alternating series formula for Pi, since we could defer all the division to the last step. Gauss-Legendre was also attractive, because it converges so quickly, but mechanically calculating square roots to high levels of precision was too daunting.

If you’re still reading this, you may be interested in how we’re planning to employ the TT in these calculations. We’ll keep you in suspense a bit longer, but our solution is really coming together. Again, this is for a middle school science fair, so scale your expectations accordingly! Also, we’re not really looking for suggestions at this point, but we’d be happy to discuss the decision-making process that was used, and our overall engineering design approach. From an education perspective, there are many topics that come into play with a project like this, from integral calculus to numerical analysis to systems integration to microprocessor architecture. Fun!

[Bob]

I’m interested. A “pi engine” has been on my wish-list of projects but I was not aware of the spigot algorithm. With help from The world of Pi - Spigot algorithm (pi314.net) I think I’ll have a good understanding in a few days.

You’re going to need more hardware than available in a standard TT. Are you planning to implement the machine in a simulation or hardware? Will you use state machines or build and code a processor?

I won Alaska’s science and engineering fair with a 10-bit machine using marble gates similar to TT in 1971 as a high school junior. It had an accumulator and a control register. Your machine will need more registers and a means of sequencing operations.

A less ambitious project might allow more time to work on the machine, report and display; especially if this is their first fair. Keep in mind that the student is expected to do the work.

-Bob S.

[stoneformation]

Thanks for the reply, @Bob. It’s cool that you did such a similar science fair project as a kid, without the benefit of all the educational resources and simulator options that exist today for Turing Tumble. My research projects were never this interesting when I was in school, to be honest. The idea to simultaneously delve into pi and mechanical computing was maybe a little over-ambitious, but it’s certainly led to a lot of discovery. Malcolm has been doing science fairs annually since first grade (even last year, remotely with COVID), so he has a lot of experience with the process and the expectations. In his case, it’s a bit different, since he’s in an accelerated academic program where they dedicate about four months each year to the science fair, with structured deliverables, etc.

Malcolm went into this project assuming that he would be able to automate the entire process, but he’s since realized that this was an unrealistic goal. He is now resigned to an approach that allows for a degree of human intervention, and this is now reflected in his problem statement. As with many historical calculation methods, the operator is an essential element of the solution. The ‘program’ is executed by following a predetermined (scripted) series of steps and copying register values from one ‘subroutine’ to another. Documenting the steps may prove challenging, but we’re looking at the assembly language for the Intel 8085 microprocessor as a template for this, due to its relative simplicity and low-level representation of basic computing operations. There’s even a simulator available…

After considering numerous potential approaches (mainly infinite sequence formulas, such as Nilakantha’s Series), we ultimately selected the Rabinowitz-Wagon spigot algorithm. As noted in the original post, there are other bounded and unbounded spigot alternatives that have been touted as ‘faster’ from a Big O perspective, but where the storage and/or calculation requirements are seemingly excessive for TT implementation.

Here’s a link to the original published article, describing the Rabinowitz-Wagon spigot algorithm in base-10:

The methods described in the paper are based on the Wallis product for π, which can be transformed into:

The algorithm essentially articulates the process for converting the mixed-radix terms above into base-10. This can be depicted via a table, with the fractional coefficients shown in the column headers:

Assuming that we’re interested in calculating the first n digits of π (including the integer portion: 3), we need roughly n × π columns in the table. For each of the n rows (i.e., for each major spigot iteration, which yields another decimal digit), this sets up a series of steps to be carried out from right to left, with i = (10n div 3) + 1 to 1, corresponding to the numerator a = i - 1 and denominator b = 2i - 1 (1/3, 2/5, 3/7, 4/9, etc.).

Back to the implementation in TT… Here are the specialized boards that we are developing in @jcross’s Turing Tumble Simulator*, to handle the required calculations and data storage requirements for the spigot algorithm:

• PI Digits (storage of 4-bit BCD digits, e.g., for n = 21)
• RW Storage (storage of the following, for each step i):
  • M1: numerator a = i - 1 (7-bit)
  • M2: denominator b = 2i - 1 (8-bit)
  • M3: initialized base (2) | r[n - 1] (6-bit)
  • M4: carry from [i] to [i - 1] (10 bit)
  • M5: main array A (12-bit)
  • M6: quotient q = A[i] div b (6-bit)
  • M7: remainder r = A[i] mod b (6-bit)
• RW Process (persists i, M4, and M7 for all steps i)
  • with pointer to i represented by a ring counter
• Binary Arithmetic (capable of the following operations):
  • integer addition (a + b, 12-bit with overflow)
  • integer subtraction (a - b, 12-bit with underflow)
  • integer multiplication (a × b, 12-bit with overflow)
  • integer division (a div b | a mod b, 12-bit with underflow)
  • integer comparison (a == b, leverages subtraction a - b)
  • 2’s complement (s2c a, used for subtraction and division)
• Stack (accommodates up to 8 12-bit registers, with stack pointer)
• BCD to Decimal Converter (4-bit BCD, 0-9 with overflow)
• Decimal to Binary Converter (12-bit output with overflow)

We will provide simulator links for each of these in a future reply to this post, along with screenshots, design commentary, and basic instructions for use. It’s good to know that there’s some interest in this topic here in the Community, but it’s a valuable exercise regardless. This is basically the same information that he will need to provide as part of his science fair report. Being able to clearly articulate his methodology in writing is key, in order to communicate the mathematical underpinnings, as well as the TT-specific aspects of the solution.

–Brian

* Kudos to @jcross [Jesse Crossen] for his ridiculously useful and engaging simulation tool. We especially appreciate the schematic mode, which is indispensable when dealing with TT boards that are upwards of 10x the standard game-board dimensions, with ~100 balls potentially in play. We also rely heavily on the PNG export/import functionality. We found a few bugs in the software, but these are easy to work around, and we certainly couldn’t have done this project without the large-board support and non-standard ball release capabilities. I can’t believe I was originally planning to take this on myself via rigid-body simulation in Blender…

[Bob]

Bryan,

BCD to Decimal: Will that be a mechanical Nixie or 7-segment? I can provide links to such devices, but they might be projects by themselves. Interestingly, the results are binary values but the range is always 0-9. They could be considered BCD but there was no BCD computation.

Decimal to Binary: The only input variable appears to be “n.” If so, consider entering a binary value to avoid needing a converter. Because the user intervenes in register transfers, nobody will want n > 16. A decimal-to-binary table could be displayed near the input.

Opinion: Audience and judges might be more impressed with fully automatic multiplication or division than with a more ambitious machine that requires user intervention.

-Bob S.

[stoneformation]

Bob:

We’ll share the details on the B2D and D2B Conversion boards. These are more for ‘extra credit’ than anything else, since they’re not strictly required for the overall solution. Malcolm didn’t want to have any paper & pencil math, though, and he also wanted to avoid lookup tables. With the current iteration of the Arithmetic board, multiplication and division are fully-automated, but it’s necessary to copy the inputs/results to and from the stack for further processing.

[stoneformation]

For the record, I’m a big fan of Nixie tubes:

Photo taken at the VintageTEK Museum, Beaverton, OR

Here's what the BCD to Decimal Converter looks like:

Simulator link

[stoneformation]

Here's the Decimal to Binary Converter:

Simulator link

[stoneformation]

I’m no longer able to edit the original post, so here’s some additional clarification on the algorithm…

Assuming that we’re interested in calculating the first n digits of π (including the integer portion: 3), we need roughly n × π columns in the table. For each of the n rows (i.e., for each major spigot iteration, which yields another decimal digit), this sets up a series of m = (10n div 3) + 1 steps, to be carried out from right to left. In other words, starting at i = m, we’ll count down to i = 1, with the rational coefficients a/b (1/3, 2/5, 3/7, 4/9, etc.) derived for each step.

In pseudocode:

init = true; // for j == 1...
n = 10; // e.g., number of pi digits and table rows
m = ((10 * n) div 3) + 1; // number of table columns
for (j = 1, j <= n j++) { // outer iteration on j, 1..n
  for (i = m, i >= 1, i--) { // inner iteration on i, m..1
    if (init) {A[i] = 2;} // initialize array to 2
    if (i == m) {c = 0;} // initialize carry to 0
    A[i] *= 10; // multiply array value times 10
    A[i] += c; // add carry to array value
    a = i - 1; // numerator
    if (i == 1) { b = 10; } // denominator for i == 1
    else {b = 2 * i - 1;} // denominator for i > 1
    q = A[i] div b; // find quotient
    r = A[i] mod b; // find remainder
    c = q * a; // find carry for next i
    A[i] = r; // set array value for next j
  }
  PI[j] = q; // jth digit of pi is A[1] div 10
  init = false; // for j > 1...
}