Random musings on circuits and projects.
I lost my touch! I got a second batch of boards, and I got solder bridges on three sides of the IC from too much solder. I’ll get the hang of it again. Once again they sent four extra boards.
The finish on the green solder mask is much nicer on this batch, even though it’s the same style of order from the same PCB maker. This once is hard and glossy whereas the last one seemed kind of thin and had a rougher finish.
This is the PCB that I sent off for the second batch of #pispigot modules. On the first batch I forgot the pull-up resistors on the I/O lines (R5 and R6) so I just soldered them in between the connector pins manually. Diptrace file can be found here.
ln 2, e, π, and φ (the golden ratio)
I programmed the units to take their parameters from the unit at the far left, and each unit is programmed with different parameters. It’s a little dark, but you can see each value written in marker on each circuit board below the digits.
The boards cooperate to do a parallel computation of a hypergeometric series. The series used are
ln 2 = 2F1(1, 1; 2; ½) / 2
e = 0F0(; ; 1)
π/2 = 2F1(1, 1; 3/2; ½)
Got three of them up and running. Yes, the soldering is for crap, but it was a great learning process. I’m now not at all daunted by surface-mounted components in projects, and can do 0603-sized parts and ICs with 0.8mm pin spacing. (There’s actually a pull-up resistor soldered in-between the +5V and Sig lines of the three-pin jack on the left side of each board.)
The flux looks way worse than it really is. I actually cleaned most of it off already but the flash makes what’s left really shine. The curvature is because I took the photo through a big magnifying glass.
And it actually works! Now to order a bigger batch of boards. Of the six I ordered, these three and one more are still viable. Six went in the trash (they shipped ten, one was bad, and five got fubar’d by me as soldering lessons).
To review what’s going on here…
On the front of each of these boards is a two-digit LED display. When you connect these together and apply power they cooperate with each other to compute the value of a hypergeometric series and display the result. With the software on them now, the resulting value is π. (The first board shows “3.1”, the second shows “41”, the third shows “59”, etc.) The more modules you connect together, the more digits of π you get. It can also calculate e (the base of the natural logarithm) and its rational powers, π², square roots of various numbers, the natural log of 2 and some other numbers, the reciprocal of π, and many values related to the “error function” erf, and some funky useless combinations thereof such as \( \frac 1 2 \sqrt[4]{e} \sqrt\pi \text{ erf}(\frac 1 2) + 1 \).
A mystery! But first…I’m getting the hang of how to solder these puppies by hand. First put solder paste on the pads for the 0603 components, place the components, then bake in the oven to reflow them into place. Next, flux up the pads for the Atmega, position the chip, tack down one corner with solder, align and tack down the opposite corner, then just swipe along each side with a tiny bit of solder to nail down eight pins at a go. (I can’t get the hang of putting solder paste on the 0.8mm-spaced pads by hand without getting bridges, but this is easier anyway.)
The mystery is why the heck LED segment C isn’t lighting on the left digit on either module. Uploading a test program shows that the digit display routine is correct (it counts from 00 to 99).
Good news is it seems to know how to calculate pi!
LED brightness test and ISP programming test for the assembled Pi Spigot circuit. Successfully blinking at 125 Hz. Huzzah!
Brightness looks fine in the photo but in real life it’s a little on the dim side, but there are way to adjust.
I also did a connectivity and control test to make sure I can light up each LED individually and it’s working. I went to the trouble of making an animated GIF of it, but Tumblr just keeps giving me an upload error so you poor souls won’t get to see it.
(This post uses MathJax to show equations, which won’t show up on Tumblr’s dashboard. Open in blog view to see equations correctly.)
This post gives some background on the math behind the Pi Spigot circuit (see previous posts).
π is about 3.14159… That sequence of digits, 3, 1, 4, 1, 5, 9, are specific to the base 10 representation of π. That’s called the decimal representation. π in base 8 (octal representation) is 3.1103755… The meaning of this representation, in base 10, is
\[ \pi = 3 + \frac 1 {10} (1 + \frac 1 {10} (4 + \frac 1 {10} (1 + \frac 1 {10} (5 + \frac 1 {10} (9 + … \]
This is numerically equivalent to the base 8 representation
\[ \pi = 3 + \frac 1 8 (1 + \frac 1 8 (1 + \frac 1 8 (0 + \frac 1 8 (3 + \frac 1 8 (7 + … \]
The digits in these representations have no known pattern to them. They seem to have all the same characteristics as a stream of random digits, and yet they’re completely computable.
However, if you use a “mixed” base instead of the same base for each digit position you can devise a positional representation where π has a regular pattern of digits. In fact, every digit is the same!
In base 10, each successive decimal position represents a place value that is 1/10th the size of the previous position (the one closer to the decimal point). In base n, it’s \( \frac 1 n \) instead of \( \frac 1 {10} \). Instead of using \( \frac 1 n \) for each digit position, if you use a different fractional base for each position you can represent π as 2.2222222…., or
\[ \pi = 2 + \frac {a_1} {b_1} (2 + \frac {a_2} {b_2} (2 + \frac {a_3} {b_3} (2 + \frac {a_4} {b_4} (2 + \frac {a_5} {b_5} (2 + … \]
If the a and b values are also unpredictable this doesn’t buy us anything. But they actually form a very simple pattern:
\[ \pi = 2 + \frac 1 3 (2 + \frac 2 5 (2 + \frac 3 7 (2 + \frac 4 9 (2 + \frac 5 {11} (2 + … \]
It doesn’t converge particularly quickly, but it’s quick enough and it can be computed using very simple integer arithmetic in each module of the Pi Spigot circuit.
By changing the pattern of the fractions at each position, and changing the pattern of the digits (e.g. using 1.111111… instead of 2.222222…) we can use the same circuitry to calculate other constants. Instead of me just listing out a bunch of magic numbers to calculate different constants, let’s go over the general technique for determining this “mixed fractional base” representation from general series formulas and derive some patterns.
The one we’re using for π comes from
\[ \frac \pi 2 = \sum_{k=0}^\infty \frac {k!} {(2k+1)!!} \]
The first few terms of this look like
\[ \frac \pi 2 = 1 + \frac 1 3 + \frac {1 \cdot 2 } {3 \cdot 5} + \frac {1 \cdot 2 \cdot 3} {3 \cdot 5 \cdot 7} + … \]
\[ = 1 + \frac 1 3 (1 + \frac 2 5 (1 + \frac 3 7 (1 + … \]
This is just our mixed-base representation, but we need to use 2′s instead of 1′s because this is an equation for π/2 instead of π.
Another interesting constant with an even simpler representation is
\[ e = \sum_{k=0}^\infty \frac 1 {k!} \]
\[ = 1 + \frac 1 1 + \frac 1 {1 \cdot 2} + \frac 1 {1 \cdot 2 \cdot 3} + … \]
\[ = 1 + \frac 1 1 (1 + \frac 1 2 (1 + \frac 1 3 (1 + … \]
\[ = 2.71828… \]
This can be written as
\[ e = 1 + \sum_{n=0}^\infty \left( \prod_{k=0}^n \frac 1 {k+1} \right) \]
Our expression for π/2 can also be written in this form.
\[ \frac \pi 2 = 1 + \sum_{n=0}^\infty \left( \prod_{k=0}^n \frac {k+1} {2k+3} \right) \]
which you can tell because the ratio of successive terms k+1 and k is
\[ \frac {(k+1)!} {(2k+3)!!} \cdot \frac {(2k+1)!!} {k!} \]
\[ = \frac {(k+1)!} {k!} \cdot \frac {(2k+1)!!} {(2k+3)!!} \]
\[ = \frac {k+1} {2k+3} \]
Functions of this form, when the numerator and denominator are polynomials in k, are called hypergeometric series. Many interesting values can be represented as hypergeometric series and computed with the Pi Spigot circuitry and software just by changing the polynomial used for the numerator and denominator. For example, to compute the square root of 2 we can use the equation
\[ \sqrt 2 = \sum_{k=0}^\infty \frac {(2k-1)!!} {4^k k!} \]
To get the hypergeometric series representation we need to look at the ratio of successive terms, which is
\[ \frac {(2k+1)!!} {4^{k+1} (k+1)!} \cdot \frac {4^k k!} {(2k-1)!!} \]
\[ = \frac {2k+1} {4k+4} \]
(As you can see, factorials, double factorials, and Pochhammer symbols simplify very nicely when you take the ratio of successive values just because of how they’re defined.) This gives us
\[ \sqrt 2 = 1 + \sum_{n=0}^\infty \left( \prod_{k=0}^n \frac {2k+2} {4k+4} \right) \]
which is just a minor tweak from the equations for π or e.
Just by playing around with different polynomials in the hypergeometric series you can discover other interesting expressions. For example
\[ \frac {\sqrt 5} 2 = 1 + \sum_{n=0}^\infty \left( \prod_{k=0}^n \frac {2k+1} {10k+10} \right) \]
which immediately leads to an expression for the Golden Ratio
\[ \phi = \frac 3 2 + \sum_{n=0}^\infty \left( \prod_{k=0}^n \frac {2k+1} {10k+10} \right) \]
which is equivalent to the infinite series
\[ \phi = \frac 1 2 + \sum_{n=0}^\infty \frac {(2n-1)!!} {10^n n!} \]
That’s all fine and good, but how do we see the result?
To compute the value of the mixed-base expression for e we usually mean compute the series of digits for a specific base representation, usually base 10. That’s what we need to do for the Pi Spigot circuit. How do we do that?
We know the first digit of e is 2, in any interesting base. Let’s compute the base-10 representation of the fractional portion of e which is
\[ \frac 1 2 (1 + \frac 1 3 (1 + \frac 1 4 (1 + \frac 1 5 (1 + … \]
We know this is between 0 and 1, and anything between less than 0.1 will have a leading digit “0″. Anything at least 0.1 but less than 0.2 will have a leading digit of “1″. We can easily determine the leading digit by multiplying by 10 and taking the integer portion of the result. The fractional portion of the result represents the remaining digits. So let’s multiply this by 10:
\[ \frac 1 2 (10 + \frac 1 3 (10 + \frac 1 4 (10 + … \]
That was easy. Also not very helpful. We just changed the digits of our mixed-base number from 1,1,1,1,1,… to 10,10,10,10,10,… But 10 isn’t a valid digit. We need to “reduce” this. Starting at the right end, we see \( \frac 1 4 \cdot 10 \). This is equal to \( 2 + \frac 1 4 \cdot 2 \). This reduces the invalid “10″ digit to a valid “2″ digit and produces a carry of 2 which we can add to the next digit to the left. So now we have
\[ \frac 1 2 (10 + \frac 1 3 (10 + 2 + \frac 1 4 (2 + … = \frac 1 2 (10 + \frac 1 3 (12 + \frac 1 4 (2 + … \]
The digit “2″ is valid at the \( \frac 1 4 \) position because it’s less than 4. Now instead of 10, 10, 10 we have the equivalent digits 10, 12, 2. Next we reduce the “12″. We see that \( \frac 1 3 \cdot 12 \) is equal to \( 4 + \frac 1 3 \cdot 0 \), so we reduce the 12 to 0 and carry the 4.
\[ \frac 1 2 (14 + \frac 1 3 (0 + \frac 1 4 (2 + … \]
Finally we reduce the 14 to a 0 and carry a 7, which is \( \frac 1 2 \cdot 14 \).
\[ 7 + \frac 1 2 (0 + \frac 1 3 (0 + \frac 1 4 (2 + … \]
So “7″ is our next decimal digit of e, and the remaining fractional portion is \( \frac 1 2 (0 + \frac 1 3 (0 + \frac 1 4 (2 + … \). We can continue extracting digits by multiplying by 10 again and repeating the reduction process. For this example we won’t get the expected digits 2, 7, 1, 8, 2, 8, etc., because we truncated the expression after a few terms. But we will get the digits that produce the base-10 representation of the truncated expression.
Doing the same for π adds a wrinkle because the numerators of the fractional bases aren’t all 1′s like they are for e. When we do a carry when the numerator isn’t 1, we also have to multiply by the numerator. But even after doing the normalization we also occasionally run into a “digit overflow” situation. We’ll see this right off the bat, actually. Let’s convert our mixed-base 2.222222… to base 10 to see how this all works. We start with the mixed-base expression
\[ \pi = 2 + \frac 1 3 (2 + \frac 2 5 (2 + \frac 3 7 (2 + \frac 4 9 (2 + \frac 5 {11} (2 + … \]
Right away it’s not immediately clear what the whole-number portion of this is. It looks like it might be 2, but we know it’s actually 3. But let’s pretend it’s 2 and see what happens. The reduction process has to start from the right, so we pick a place to truncate based on the accuracy that we want. We’ll truncate after the \( \frac 5 {11} \) position as shown. So we remove the 2 and the fractional portion (not really) multiplied by 10 is
\[ \frac 1 3 (20 + \frac 2 5 (20 + \frac 3 7 (20 + \frac 4 9 (20 + \frac 5 {11} (20))))) \]
The last term \( \frac 5 {11} \cdot 20 \) is reduced to \( 5 + \frac 5 {11} \cdot 9 \). (We calculate \( \frac {20} {11} \) to get 1 with a remainder of 9, so we carry \( 1 \cdot 5 \) and keep the remainder. Now we have
\[ \frac 1 3 (20 + \frac 2 5 (20 + \frac 3 7 (20 + \frac 4 9 (25 + \frac 5 {11} (9))))) \]
Next we reduce \( \frac 4 9 \cdot 25 \). Since \( \frac {25} 9 \) is 2 with a remainder of 7 we get \( 2 \cdot 4 + \frac 4 9 \cdot 7 \) so we carry 8 and keep the 7.
\[ \frac 1 3 (20 + \frac 2 5 (20 + \frac 3 7 (28 + \frac 4 9 (7 + \frac 5 {11} (9))))) \]
We continue this until all of the digits are reduced to the allowed range for each digit position (one less than the denominator for that position). We end up with
\[ 10 + \frac 1 3 (2 + \frac 2 5 (2 + \frac 3 7 (0 + \frac 4 9 (7 + \frac 5 {11} (9))))) \]
So we pretend that 10 is the “whole” portion and take it as our next digit, so our digits are now 2, 10 and the “fractional” portion, multiplied by 10 to get the next digit, is
\[ \frac 1 3 (20 + \frac 2 5 (20 + \frac 3 7 (0 + \frac 4 9 (70 + \frac 5 {11} (90))))) \]
After reduction this becomes
\[ 11 + \frac 1 3 (1 + \frac 2 5 (3 + \frac 3 7 (6 + \frac 4 9 (2 + \frac 5 {11} (2))))) \]
So now our “digits” are 2, 10, 11 and the fractional portion multiplied by 10 is
\[ \frac 1 3 (10 + \frac 2 5 (30 + \frac 3 7 (60 + \frac 4 9 (20 + \frac 5 {11} (20))))) \]
which reduces to
\[ 10 + \frac 1 3 (2 + \frac 2 5 (2 + \frac 3 7 (5 + \frac 4 9 (7 + \frac 5 {11} (9))))) \]
Repeating this process over and over again produces “digits” 2, 10, 11, 10, 14, 9, 10, 6, and then we end up with the same fractional portion we saw after producing the first “10″ digit, so everything repeats starting from the 11.
We know that 10, 11, and 14 aren’t valid digits. But we realize they represent a digit and a “1” carried to the left. So instead of 2, 10 we have 3, 0, and instead of 3, 0, 11 we have 3, 1, 0, and instead of 3, 1, 0, 10 we have 3, 1, 2, 0, and instead of 3, 1, 2, 0, 14 we actually have 3, 1, 2, 1, 4, etc. So our decimal value is \( 3.1 \overline {215007} \). That’s not π but it is the decimal representation of the expression we truncated after the 5/11′s position. To get closer to π we just have to add more terms.
The algorithm spits out one digit at a time with each circuit module dealing with just a few terms at a time and passing carries to the left. Occasionally a digit will overflow and we have to do a simple carry. So each module is dealing with the arithmetic of multiplying terms by 10, but also the display of the resulting decimal digits and the carries. The digits that each module displays aren’t directly related to the terms of the series that it’s calculating. The carries for the series are passed to the left and the digits of the results are passed back to the right for display. Digit overflows are carried back to the left again.
This method apparently produces more digit carries than the variation of the algorithm described by Rabinowitz and Wagon, but in fact it produces the same carries and handles them in a different way. This algorithm eliminates the final multiply-by-10 and mod-10 of the whole-number digit and leaves it up to the digit display step to deal with the carries. Since the microcontroller has to deal with that anyway, we might as well eliminate an unnecessary step.
Successfully soldered on second attempt. I got 3 out of 4 sides on first attempt but used too much solder on the 4th side and made a mess of trying to wick the extra off.
I used the “apply flux, put chip in place, and then put a blob of solder on the tip of the iron and drag across pins” method. Iron at 375 °C. Tiny blob of solder. It’s not the prettiest job in the world but the connections check out OK.
The Pi Spigot boards came back from the PCB house. This one has a break in the trace running just underneath D1, but they sent me 10 boards when I only ordered and paid for 6, so it’s all good.
The 3D view of the Pi Spigot board:
The two rows of holes are for the 2-digit 7-segment display which will go on the “back” of the board, which is actually the front but it’s easier to call it the back in DipTrace because it’s the only component back there. J1 is dual-purposes: it’s six pins for programming the Atmega, but after that it’s used to connect to J2 on the adjacent board. That’s why the connectors stick out the sides.
Here it is with a US quarter for scale:
I love how compact it is, but I hope I’ll be able to solder it!
A great thing about this board is that it’s pretty generic. It can be used as a general-purpose two-digit display. Instead of calculating digits of pi, you can use a chain of them as a serial-input general-purpose numeric display. You could use two of them with a small header board as a temperature display, etc.