Prime Failure 1 Year in the Making

Warning: This post is several years old and the author has marked it as poor quality (compared to more recent posts). It has been left intact for historical reasons, but but its content (and code) may be inaccurate or poorly written.

My expression is completely flat right now. I simply cannot believe I’m about to say what I’m preparing to say. I spent nearly a year cracking large prime numbers. In short, I took-on a project I called The Flowering N’th Prime Project, where I used my SheevaPlug to generate a list of every [every millionth] prime number. The current “golden standard” is this page where one can look-up the N’th prime up to 1 trillion. My goal was to reach over 1 trillion, which I did just this morning! I was planning on being the only source on the web to allow lookups of prime numbers greater than 1 trillion.

However, when I went to look at the logs, I realized that the software had a small, fatal bug in it. Apparently every time the program restarted (which happened a few times over the months), although it resumed at its most recent prime number, it erased the previous entries. As a result, I have no logs below N=95 billion. In other words, although I reached my target this morning, it’s completely irrelevant since I don’t have all the previous data to prove it. I’m completely beside myself, and have no idea what I’m going to do. I can start from the beginning again, but that would take another YEAR. [sigh]

So here’s the screw-up. Apparently I coded everything correctly on paper, but due to my lack of experience I overlooked the potential for multiple appends to occur simultaneously. I can only assume that’s what screwed it up, but I cannot be confident. Honestly, I still don’t know specifically what the problem is. All in all, it looks good to me. Here is the relevant Python code.

```def add2log(c,v):
f=open(logfile,'a')
f.write("%d,%dn"%(c,v))
f.close()

def resumeFromLog():
f=open('log.txt')
f.close()
return eval("["+raw+"]")```

For what it’s worth, this is what remains of the log file:

```953238,28546251136703
953239,28546282140203
953240,28546313129849
...
1000772,30020181524029
1000773,30020212566353
1000774,30020243594723```

Microcontroller-Powered Prime Number Generator

Warning: This post is several years old and the author has marked it as poor quality (compared to more recent posts). It has been left intact for historical reasons, but but its content (and code) may be inaccurate or poorly written.

My microcontroller-powered prime number calculator is complete! Although I’m planning on improving the software (better menus, the addition of sound, and implementation of a more efficient algorithm) and hardware (a better enclosure would be nice, battery/DC wall power, and a few LEDs on the bottom row are incorrectly wired), this device is currently functional therefore I met my goal!

This device generates large prime numbers (v) while keeping track of how many prime numbers have been identified (N). For example, the 5th prime number is 11. Therefore, at one time this device displayed N=5 and V=11. N and V are displayed on the LCD. In the photo the numbers mean the 16,521,486th prime is 305,257,039 (see for yourself!). The LCD had some history. In December, 2003 (6 years ago) I worked with this SAME display, and I even located the blog entry on November 25’th, 2003 where I mentioned I was thinking of buying the LCD (it was \$19 at the time). Funny stuff. Okay, fast forward to today. Primes (Ns and Vs) are displayed on the LCD.

In addition to the LCD, numbers are displayed in binary: Each row of LEDs represents a number. Each row of 30 LEDs allows me to represent numbers up to 2^31-1 (2,147,483,647, about 2.15 billion) in the binary numeral system. Since there’s no algorithm to simply generate prime numbers (especially the Nth prime), the only way to generate large Nth primes is to start small (2) and work up (to 2 billion) testing every number along the way for primeness. The number being tested is displayed on the middle row (Ntest). The last two digits of Ntest are shown on the top left. To test a number (Ntest) for primeness, it is divided by every number from 2 to the square root of Ntest. If any divisor divides evenly (with a remainder of zero) it’s assumed not to be prime, and Ntest is incremented. If it can’t be evenly divided by any number, it’s assumed to be prime and loaded into the top row. In the photo (with the last prime found over 305 million) the device is generating new primes every ~10 seconds.

I’d like to emphasize that this device is not so much technologically innovative as it is creative in its oddness and uniqueness. I made it because no one’s ever made one before. It’s not realistic, practical, or particularly useful. It’s just unique. The brain behind it is an ATMEL ATMega8 AVR microcontroller (What is a microcontroller?), the big 28-pin microchip near the center of the board. (Note: I usually work with ATTiny2313 chips, but for this project I went with the ATMega8 in case I wanted to do analog-to-digital conversions. The fact that the ATMega8 is the heart of the Arduino is coincidental, as I’m not a fan of Arduino for purposes I won’t go into here).

I’d like to thank my grandmother’s brother and his wife (my great uncle and aunt I guess) for getting me interested in microcontrollers almost 10 years ago when they gave me BASIC Stamp kit (similar to this one) for Christmas. I didn’t fully understand it or grasp its significance at the time, but every few years I broke it out and started working with it, until a few months ago when my working knowledge of circuitry let me plunge way into it. I quickly outgrew it and ventured into directly programming cheaper microcontrollers which were nearly disposable (at \$2 a pop, compared to \$70 for a BASIC stamp), but that stamp kit was instrumental in my transition from computer programming to microchip programming.

The microcontroller is currently running at 1 MHz, but can be clocked to run faster. The PC I’m writing this entry on is about 2,100 MHz (2.1 GHz) to put it in perspective. This microchip is on par with computers of the 70s that filled up entire rooms. I program it with the C language (a language designed in the 70s with those room-sized computers in mind, perfectly suited for these microchips) and load software onto it through the labeled wires two pictures up. The microcontroller uses my software to bit-bang data through a slew of daisy-chained shift registers (74hc595s, most of the 16-pin microchips), allowing me to control over 100 pin states (on/off) using only 3 pins of the microcontroller. There are also 2 4511-type CMOS chips which convert data from 4 pins (a binary number) into the appropriate signals to illuminate a 7-segment display. Add in a couple switches, buttons, and a speaker, and you’re ready to go!

I’ll post more pictures, videos, and the code behind this device when it’s a little more polished. For now it’s technically complete and functional, and I’m very pleased. I worked on it a little bit every day after work. From its conception on May 27th to completion July 5th (under a month and a half) I learned a heck of a lot, challenged my fine motor skills to complete an impressive and confusing soldering job, and had a lot of fun in the process.

Summer’s End is Nearing

My favorite summer yet is reaching its end. With about a month and a half before I begin dental school, I pause to reflect on what I’ve done, and what I still plan to do. Unlike previous summers where my time was devoted to academic requirements, this summer involved a 9-5 job with time to do whatever I wanted after. I made great progress in the realm of microcontroller programming, and am nearing the completion of my prime number calculator. I’m very happy with its progress.

Most of the LEDs are working but I’m still missing a few shift registers. It’s not that they’re missing, so much as I broke them. (D’oh!) I have to wait for a dozen more to come in the mail so I can continue this project. Shift registers are also responsible for powering the binary-to-7-segment chips on the upper left, whose sockets are currently empty.

Since this project is on pause, I began work hacking a VFD I heard about at Skycraft. It’s a 20×2 character display (forgot to photograph the front) and if I can make it light up, it will be gorgeous.

Here’s a high resolution photo of the back panel of the VFD. I believe it used to belong to an old cash register, and it has some digital interfacing circuitry between the driver chips (the big OKI ones) and the 9-pin input connector. I think my best bet for being able to control this guy as much as I want is to attack those driver chips, with help from the Oki C1162A datasheet. It looks fairly straightforward. As long as I don’t screw up my surface-mount soldering, and assuming that I come up with 65 volts to power the thing (!) I think it’s a doable project.

Prime Number Generator Schematics

Warning: This post is several years old and the author has marked it as poor quality (compared to more recent posts). It has been left intact for historical reasons, but but its content (and code) may be inaccurate or poorly written.

Here’s a schematic of the prime number calculator I’m working on. Last night I finished wiring all 12 shift registers for the primary display, so now it’s time to start working on software. Notice that we have a lot of pins free still. This will be advantageous if I decide to go crazy adding extraneous functionality, such as fancy displays (LCD?, 7-segment LEDs?, VFD?, all 3?!) or creative input systems (how about a numerical keypad?).

After feeling the stink of paying almost \$15 for 100′ of yellow, 24 gauge, solid-core wire from DigiKey I was relieved (and a little embarrassed) to find I could score 1,000′ of yellow, 24 gauge, threaded wire for \$10 at Skycraft! Anyway, here’s the current schematic:

Prime Prototype Construction

Warning: This post is several years old and the author has marked it as poor quality (compared to more recent posts). It has been left intact for historical reasons, but but its content (and code) may be inaccurate or poorly written.

Now that I’ve worked-out the software side of the microcontroller-powered prime number generator, it’s time to start working on the hardware. I want to make a prototype which is far smaller and simpler than the final version but lets me practice driving lots of LEDs (30). I expect the final version to have around 80. Also, the heart of this project is an ATTiny2313 microcontroller, and for the full version I’d like to use an ATMEega8. I picked up an unfinished wooden box with a magnetic latch from Michaels. It’s delicate and tends to chip when you drill it, but moving slowly I’m able to make nice evenly-spaced holes.

This is the circuit concept. The chip is an ATTiny2313, sourced with 5V, where the left pins control the columns (by providing current) and the right pins control the rows (by providing ground). The “holes” at the top of the circuit represent where I hook up my PC and external power for testing purposes.

Thoughts from Future Scott (10 years later, August, 2019)

A+ for enthusiasm and construction but your design is… just no!

Why are you using an external crystal?

The schematic for the crystal is wrong: those capacitors should be to ground not in series!

You made the circuit diagram in InkScape!

You shouldn’t drive current directly out of the microcontroller pins.

The majority of the microcontroller CPU cycles will go into managing multiplexing of the display (not calculating primes).

After a little more work I have a functional device and it looks better than I expected. There are a few more features I want to add, and I want to work on the code some more, but I hope to be done tomorrow. The coolest part is that I’ve included an internal button which drives a pause/resume and speed-controller menu based upon the length of button presses! There’s a lot of awesome stuff I want to write, but once again, I’ll save it for the completed project page.

I rendered the cover sticker wrong and all the LEDs are mislabled. The first LED should be 2^0 (1), and the second should be 2^1 (2), etc. Also, 2^22 and 2^23 are mislabeled – oops! But the thing really does generate, differentiate, and display [only[ prime numbers. Once again, videos (including demonstration of the menus and the programming options) and source code will be posted soon.

Prime Number Generator Prototype

Warning: This post is several years old and the author has marked it as poor quality (compared to more recent posts). It has been left intact for historical reasons, but but its content (and code) may be inaccurate or poorly written.

In my quest to build a hardware-based prime number generator I built a rapid prototype to assess how quickly primes can be found with an 8-bit microcontroller. There is a lot of room for improvement, but the code works. Instead of messing with tons of little LEDs, this design displays numbers on an LCD. Interestingly the library to run the LCD takes up about 90% of the memory of the chip leaving only a handful of bytes to write the prime calculation code in!

```#define F_CPU 1E6
#include <stdlib.h>
#include <avr/io.h>
#include <math.h>
#include <util/delay.h>
#include "lcd.h"
#include "lcd.c"

const unsigned long int primeMax=pow(2,25);
unsigned long int primeLast=2;
unsigned long int primeTest=0;
unsigned int primeDivy=0;

void wait(void);
void init(void);
void updateDisplay(void);
char *toString(unsigned long int);

int main(void){
init();
short maybePrime;
unsigned int i;
for(primeTest=2;primeTest<sqrt(primeMax);primeTest++){
maybePrime=1;
for (i=2;i<=(sqrt(primeTest)+1);i++){
primeDivy=i;
updateDisplay();
if (primeTest%primeDivy==0){maybePrime=0;break;}
}
if (maybePrime==1){primeLast=primeTest;updateDisplay();}
}
return 0;
}

void updateDisplay(void){
lcd_gotoxy(12,0);lcd_puts(toString(primeLast));
lcd_gotoxy(5,1);lcd_puts(toString(primeTest));
lcd_gotoxy(16,1);lcd_puts(toString(primeDivy));
return;
}

void init(void){
lcd_init(LCD_DISP_ON);
lcd_puts("PRIME IDENTIFICATIONn");
_delay_ms(2000);
lcd_clrscr();
lcd_puts("LAST PRIME:n");
lcd_puts("TRY:");
lcd_gotoxy(14,1);lcd_puts("/");
return;
}

char *toString(unsigned long int x){
char s1[8];
ltoa(x,s1,10);
return s1;
}```

A Prime Idea

Warning: This post is several years old and the author has marked it as poor quality (compared to more recent posts). It has been left intact for historical reasons, but but its content (and code) may be inaccurate or poorly written.

I’m completely drained of energy. I visited my wife’s family in Tennessee last week. I left Thursday and came back Tuesday (yesterday). I drove a total of 2,180 miles. The drive to Humboldt, TN (the destination) and back is only 1,658 miles. That means that I drove over 520 miles over the 3 days while at my destination. That’s about 174 miles a day. At 50 MPH average speed that’s about 4 hours in the car. So, 13 hour drive (each way) to get there, then 4 hours in the car every day I was there. That’s a lot of car time!

While speaking with my brother-in-law (who just got a BS in computer science with a minor in mathematics) I learned that a faculty member at the university challenged him to write a computer program which could find the N’th prime number (up to 10^15) for a graduate school project. I was fascinated by the idea project and the various techniques, and workarounds related to it. After working on the theory behind the software (which I tested in Python) for a few hours, I had the idea to attempt to perform a similar task at the microcontroller level.

Here’s the project I want to begin: I want to build a microcontroller-powered prime number generator which displays results in binary. The binary-encoded output is similar to the binary clocks which are nothing new. My project will calculate prime numbers up to 2^25 (33,554,432) and display the results in binary using long strips of 20 LEDs. There will be 3 rows of LEDs. The middle row (red) will simply count from 0 to 2^25. Every time it gets to a new number, the bottom row (blue) counts from 0 to the square root of the middle row. For every number on the bottom row, the remainder (modulus) of the middle/bottom is calculated. If the remainder is 0, the middle (red) number is divisible by the bottom (blue) therefore it is not prime. If the bottom number gets all the way to the square root of the middle number, the middle number is assumed to be prime and it is copied to the top row (green). The top row displays the most recent number determined to be prime.

Technical details of the project further reveal its dual simplicity/complexity nature. I’ll add some buttons/switches for extra features. For example, I want to be able to start the program at a number of my choosing rather than forcing it to start at 0. Also, I want to be able to adjust the speed at which it runs (I don’t want the blue row to just flicker forever). The ATTiny2313 (my microcontroller of choice because I have a few extra of them) has 18 IO pins. If I get creative with my multiplexing techniques, I can probably run 81 LEDs from 18 pins (9 rows of 9 LEDs). I’ve specifically chosen against charlieplexing because I will be lighting many LEDs “simultaneously” and I think the degree of flicker would be far too great to satisfy my sensitive eyes, even though I could do it all with only 10 pins.

I’ve decided to transistorize the entire project to provide a greater and more constant current to the LEDs. I’ll use a set of 9 transistors to set the row that gets power (when the microcontroller powers the base, the row gets power) and another set of 9 transistors to set the LEDs in each row that light up (when the microcontroller powers the base, the LED gets grounded and lights up). To have consistently-bright, non-flickering LEDs which don’t dim as more LEDs illuminate, I will add a resistor to every LED. Maybe I can get creative and utilize 10-pin resistor networks (one for each row) immediately after the row-selecting transistor! That will save me so much time. (I just came up with that idea – just now!) Anyway, that’s my project idea.

I’d love to make this project look nice. All of my other projects were housed in junky plastic or cardboard boxes (if they were housed at all!) and this is something I want to keep. I start dental school soon, and I’ve love to have a fancy-looking piece of artsy/geeky/electrical memorabilia so I’ll never forget who I am, my roots, and my true interests. Plus, it will give me something groovy to stare at when I come home after a long day cleaning the teeth of manikins and wondering why I went to dental school [sigh].

Update (nextday): I’ve been toying over some various layouts for the LEDs. I most like the rectangle and hex-rectangle configurations, and am already working on assembly of the “mini” (prototype). Here are some random images of my thinking process.