NEW: Learning electronics? Ask your questions on the new Electronics Questions & Answers site hosted by CircuitLab.
Project Help and Ideas » Pi spigot
September 02, 2011 by bretm |
Project idea: Create a tiny circuit board with a single 7-segment LED digit on it and an ATTiny and some resistors. By itself, when powered on, it will display "3.". It will have a connector on each side. If a second identical unit is connected on the right side, the next digit will display the next digit of pi, which is "1". Keep attaching units, supplying enough power, and each added digit will display the next digit of pi. How would it work? See A Spigot Algorithm for the Digits of Pi by Rabinowitz and Wagon. Each unit would handle 4 columns of the calculation. On average only 3 1/3 columns are needed, but always using 4 doesn't hurt anything. Things will be fast enough. They would communicate with their left and right neighbors using the following protocol:
Or something like that anyway. Digit dimensions and connector layout should be standardized so that units produced by different people can be connected together. |
---|---|
September 03, 2011 by Ralphxyz |
Now this would be a great electronics club/class project. Every new member to the club would make a module. Eventually you could have hundreds. Would there be a limit to the number of digits processed? Would you use a protocol for communications or just serial/pin high? Ralph |
September 03, 2011 by bretm |
It would be limited only by the power supply and the current rating of the pcb traces and connectors, but you can get around that by adding additional supplies with common ground further down the line. The more modules you have the longer it would take for the first digit to show up. The delay would be in linear relation to the module count, and just microseconds per digit anyway, so it would take many thousands before it would look "slow". Once you reach about 200 digits you already have the computing power of a 3GHz PC core, at least as far as this algorithm is concerned. |
September 03, 2011 by bretm |
Oh...protocol. SPI would be good. The communication is fundamentally an exchange between neighbors of carries coming from the right and finished digits coming from the left. |
September 03, 2011 by bretm |
The cheapest I can find digits is $0.44 per digit, from the Sparkfun 4-digit modules. They're a lot pricier on Digikey--$0.715 per digit there. The math for 4 digits per unit isn't any harder than 1 digit, but the LED driving gets harder because you have to multiplex and add a transistor per digit, or add a driver chip per unit. But the per-digit cost of the MCUs goes down. I think it's probably the right way to go. Could also go LCD at $0.28 per digit, but even harder to drive and not stackable with equal digit spacing. The datasheet doesn't show electric characteristics but I bet it draws a lot less current. |
September 03, 2011 by bretm |
So, not SPI. I change my mind. More like TWI hardware but not the TWI complexity since we don't need multiple slaves. Saves wires. Data is tri-state or pulled low by only one unit, not both. Digit to the right owns the clock line. The last digit is in charge. Each digit is the boss of the digit to the left. When your boss clocks you, you have to stop and listen and answer. When you power on, ask your left digit what your position is. If they know, they've already been running and you're the new guy. If they answer "I'll tell you later" it's because they just powered on, too, and are waiting to find out. Ask again later. If no answer, you're the first digit and your position is 0. If you're the tail digit, initialize your calculations and crank out your first carry. Tell your slave "here's your carry, give me your digit if you have one" (except for the very first calculation, where you ignore incoming digit). If you're given a carry value by your master, and you just woke up, initialize yourself and do your first calculation. Tell them you don't have a digit yet. Give your carry result to your own slave and tell them that this is a new calculation starting. Carries pass to the left, digits pass to the right. If a carry is the first in a new calculation, digits coming from the left are discarded as they pass and each digit initializes itself. Digits coming from the left are displayed on the first unit that hasn't received one. Fresh digits are in "pending" state until another digit passes by that isn't a 9, which releases the pending digit for display. If it's a 10, the pending digit is incremented before displaying. If it's a 9 it's just passed along. If you're the head digit, your carry is actually a new pi pre-digit and you hold onto it to give back to your master when you're given the next carry value (or you display it if you haven't yet). I've gone back to the single-digit-per-unit idea. Easier to standardize and implement, if slightly more expensive per digit. BIT-LEVEL DETAILS: When your boss raises the clock line, they'll either be asking "where am I" or "here's a carry value". This is just one bit, obtained from the data line. You wait for clock low, then put your first answer bit on the data line within a specific time period after which the boss will read it. If they asked "where am I" you either send "0" which is "I don't know, I just woke up", or "1" which is "I'll tell you". If you do know, your boss will ask for 32 more bits, in which you tell them their position (your position plus one). If your boss said "here's a carry value" you then read the next bit. If it's a "1", this is the first calculation from a newly-awoken unit, otherwise it's a continuation. Then the next 32 bits received are the carry value. Your boss will wait for you to answer "1". You may not be able to do it immediately if you're still in the middle of a previous calculation. After you receive a carry and you send your "1", you send a "0" if you're not holding on to a digit, or a "1" if you are, then you send 4 more bits representing the digit you're holding. If you're starting a new calculation, then you just threw away whatever digit you were holding and you don't return a digit. That's most of it. |
August 04, 2012 by bretm |
I finally got around to building this. I went with two digits per microcontroller because it was easy to fit on the breadboard and only added one more resistor. Transistor LED drivers are eliminated by only running one segment per digit at a time at 16mA. One output pin at a time can source two segments total, for 32mA. This is running from a 9V battery limited by a 7805 voltage regulator. I programmed the chips using an in-circuit programmer, not the Nerdkits bootloader. That's also why you don't see crystals. The chips are running on the 8MHz internal clock divided down to 1MHz. The point of this circuit isn't to display "3.14159". You wouldn't need microcontrollers for that. The point is that all three circuits are identical and they are cooperating to implement the Pi Spigot algorithm of Stanley Rabinowitz and Stan Wagon. Each chip is running seven columns of the algorithm and passing the carry value onto the next chip. The algorithm is O(n^2), but since the microcontrollers are running in parallel it finishes the calculation in O(n) time. If you connect enough of these together it will calculate pi faster than a desktop PC using the same algorithm (but much better algorithms exist). The chips are connected together with a single data wire (yellow wires at the left of the image). Ground is also shared. +Vcc is also shared but doesn't have to be. The data lines have external pull-resistors because of the protocol used to transfer data. It's similar to the "1-Wire" protocol for obvious reasons. Either chip can pull the data line down, so I leave PORTx at 0 and use DDRx to either disconnect from the line (at let it pull up) or drive the line and pull it down to zero. |
August 05, 2012 by bretm |
Source code follows. There is a wide variety of pin-outs on 7-segment displays so I made it as configurable as possible. The common anode code path hasn't been tested.
|
August 08, 2012 by Ralphxyz |
Wow bretm, that's cool. I've missed your input, been traveling? Ralph |
August 08, 2012 by pcbolt |
bretm - Very cool project and very interesting link to the Spigot algo. Should be a snap converting it to display 'e'. If my understanding of your code is correct, you'd only need to change the num/den sequence from
To
Wouldn't mind seeing a photo of that :-) |
August 09, 2012 by bretm |
Yes, I think e would be that easy. I'll try it and take a pic if it works. In addition to changing the fractions, I'd also have to change the initial digits from 2,2,2,... to 1,1,1,... I thought about incorporating this either by adding a switch, or by adding a controller to the front end to provide the rules, but I didn't want to complicate the design. Doing a one-off for a photo op is no problem, though. Interesting side-note: because the LED segments are multiplexed, my phone can't take a picture of this in action. The exposure time is too short and it doesn't show the complete digits. I had to use my wife's iPhone because it takes a longer exposure. Hi, Ralph! No, not travelling, unless you count travelling to allaboutcircuits.com. Been over at that forum instead lately. But I had to post this to Nerdkits because I credit them for getting me in to microcontrollers at all. Next step for this is miniaturization. A surface-mount Atmega, current-limiting resistors, bypass capacitor, and reset pullup resistor will all fit in between the pins of the LED displays. Just need a little circuit board sticking out because I want to put pins for the in-circuit programmer, and I need plugs/recepticals to join digits together. |
August 09, 2012 by bretm |
Here's the "e" picture. I built out a couple of more units. I ran out of 7-segments so I bought two more from Fry's. Same manufacturer and part number, but dimmer display. NTE is now provably both overpriced and declining in quality over time. The extra wires are to join all the SPI ports together to make it easier to reprogram them all. |
August 09, 2012 by pcbolt |
Wow! That was fast. Guess it was that easy. So if you were to throw in a bypass switch which would jump over a "node" all the digits down the line would change. Thanks for the picture...awesome project. |
August 10, 2012 by bretm |
Eventually that's how it will work but not yet. Once the digits are displayed the modules stop listening to each other. I still need to add code to watch if the connections are changed and invoke a recalculation and I haven't figured out a good method that handles all the edge cases. It would be easy with a two-wire protocol but I'm trying to keep it one-wire for various reasons. |
August 23, 2015 by bretm |
OMG this forum is still running. :-) Just dropped by to mention I never forgot about this project and finally built the thing. See it on my blog. Here's a picture of three of the two-digit modules. Yes, that's an Atmega168A and supporting components in between the pins of the 7-segment display, on the back side of the board. |
August 24, 2015 by Rick_S |
Looks good! - I'm going to have to make up some smd boards and try the reflow thing one of these days... |
August 24, 2015 by JKITSON |
bretm Wow The boards are really nice. I am having to redo my display boards as I did my layout wrong the first time. Your method of inter-connecting is perfect. It will make my next batch much simpler. Am impressed with your math and totally lost also. Good work. Jim |
August 24, 2015 by Ralphxyz |
bretm, was so helpful in helping me along the way!! Thanks bretm. |
August 24, 2015 by bretm |
I would have done the connections differently. 1) The holes are too big so it's easy to solder them in crooked. 2) The 1x3 should be a 2x3 with the extra pins unused. The 1x3 is too flexible. 3) The natural height of the 2x3 doesn't leave enough room for the ISP connector so I have to have the ISP connector attached to get the height right when I solder it in, and then connect the 1x3 to a neighboring 2x3 to get its height right. 4) There needs to be some other connection near the top end of the board to prevent twisting. |
August 24, 2015 by Rick_S |
Jim, Good to see you back. How did the tests go? hope all is well |
August 26, 2015 by BobaMosfet |
bretm- Long time no see, welcome back! Yes board is limping along-- Mike and Humberto abandoned it several years ago, but we are all still here. Nice work on your PCBs. BM |
Please log in to post a reply.
Did you know that essentially all power supplies' voltages drop when current is drawn from them? Learn more...
|