Epic Failure 1 Year in the Making

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. flowering_primes

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):

def resumeFromLog():
	return eval("["+raw+"]")

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



Mental Viscosity

A few weeks into dental school I feel I’m fairing decently. I have reached a point where I know everything will be okay, but am still disappointed at the [immense] amount of time it requires. There are so many things I wish I could do, but all of my projects need to be placed on a 4-year hiatus. I can bask in the satisfaction of the few projects I completed this summer, and I only hope that it’s enough to last me for four years. Dentistry, while important, is nothing more than emulation/repetition of what everybody else does. I simply have to satisfy my creative and ingenuitive desires in my hobbies, whatever they may be. For now, this website will cease to grow. Perhaps when I become more in control of my studies I will contribute to it, but in all likelihood I won’t be able to do anything worth writing about until 4 years from now [sigh]. With that being said, adieu, and goodnight.

I realized I never posted video of my finished prime number generator, so here it is. Full details are described on the project page. In brief, the 2-digit display on the left is the last two digits (in base-10, decimal) of a number currently being tested for primeness. This number is also displayed on the bottom red bar above the yellow lights (in base-2, binary). Once proven to be prime (by attempting to divide it by every number between 2 and its square root, every 1000th attempted number shown in yellow lights in binary), it’s loaded onto the top row of red lights (binary) and on the character LCD. N represents the Nth prime, with V representing its value. Half way through the video, the display says that the 16,595,044’th prime (N) equals 306,692,621 (V). Don’t believe it? Check my work.


Microcontroller-Powered Prime Calculator is [Mostly] Complete!

My microcontroller-powered prime number generator/calculator is virtually 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 theoretically complete (I met my goal). This entry will serve as the primary reference page for the project, so I will provide a brief description of what it is and what it does. First, here’s a picture of the device in its current state (click to enlarge):

BRIEF DESCRIPTION: This device generates large prime numbers (v) while keeping track of how many prime numbers have been identified (N). The 5’th prime number is 11. Therefore, at one time this device displayed N=5 and V=11. N/V values are displayed on the 20×2 LCD. In the photo, 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, but what’s with all those other LED lights? I’ll tell you:

In short, each row of LEDs displays 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 known algorithm to 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. Not bad! Let’s discuss technical details.

I’d like to emphasize that this device is not so much technologically innovative as it is creative. I made it because no one’s ever made one. 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.

By the way, here’s a simplified schematic:


Summer's End is Nearing

My most glorious 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/thesis requirements, this summer hosted a 9am-5pm job with time to do whatever I want to after. I’ve 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. I think it’s time for some photos.

Here I can be seen working on my prime number calculator. The primary display is nearing completion, and now it’s time to start wiring the buttons, switches, speaker, etc. Note the vintage scope in the background. In the photo it’s showing 60Hz (I couldn’t think of anything more profound to display?) which I’ll say is a representation of the fact that your body is continuously bombarded by electromagnetic radiation whenever you set foot in a house.

This is the current state of the back panel of the prime number calculator. It’s becoming quite complicated.

As you can see, most of the LEDs are working but I’m still missing a few 74hc595 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.

Update: I found a funny photo from field day. After the tents, antennas, and radios were mostly set up, everyone was exhausted. I was ready to make some contacts! I fired-up my ‘ol netbook and tried communicating over 40m using psk (a digital mode), a mode I’ve never used, with software I’ve never used, on a band I’ve never used. It wasn’t working either. I spent the first several hours in frustration because what I was trying to do wasn’t working, and I couldn’t figure out why. This photo was taken at the height of my frustration =o)


Prime Schematics

Here’s a rough approximation of the current 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:


Jedi Soldering Skills – Part 2

I’ll update my progress on this project as I go. I added a lot more light bars to the shift registers on my prime number generator project. I’m up to 5 daisy-chained shift registers completed (powering 40 LEDs) with 7 more to go! I’m using 22 gauge solid-core (fancy and expensive, from digikey, 100′ 14$!) wire for the back of this project. Being that I plan to keep it for many years, I want it to look crazy awesome. Remember, I’m only about 1/3 done so far…

I powered the device up and it produced proper output. Yay! I was so discouraged yesterday when I wired-up an entire row (the top one), powered it on, and 1/2 the LEDs didn’t work. At first I thought it was software, but then I realized that I burned the LEDs out in the soldering process by getting them too hot. I had to de-solder EVERYTHING, rip out the destroyed LED bars, and start over. I’ll have to pick up some more light bars at Skycraft soon. This is what it looks like currently:

I’m making this project a priority because I only have a few weeks before I move to Gainesville, FL for dental school (the cutoff date for all electronics/radio/programming projects). I’ll be busy the next few days with other obligations (work, apartment hunting, field day, etc.) but I hope to resume this project soon.

UPDATE (June 26, 2009 @ 7:30pm): I finished wiring all the light bars I have. I need to purchase 3 more 10-led bars at Skycraft to replace the ones I melted with my soldering iron. D’oh! Anyway, here’s the beaut:


Jedi Soldering Skills

I’m currently challenging myself by creating a microcontroller-based project a few orders of magnitude more complex than anything I’ve ever done before. Although this is probably on par with projects you might see being created by senior electrical engineering seniors, keep in mind that I have no formal training in engineering, and that my MS is in molecular biology. I just started learning about circuitry / microcontrollers a few months ago, and challenge myself to learn more by continually attacking greater and greater challenges. Here’s what I began working on last night:

This if the first entry describing the creation of my non-prototype microcontroller-powered prime number generator. I made a proof of concept device a few weeks ago which calculates prime numbers (up to 2^25, about 33.5 million) and displays the results in binary form using 25 LEDs assembled in a 5×5 matrix. I added an extra column of 5 LEDs for a final matrix size of 6×5, illuminated by multiplexing through 11 IO pins of an ATMEL ATTiny2313. My new project will do the same thing, except it can calculate prime numbers up to 2^30 (over 1 billion!). Instead of only displaying 1 number, it will display 3 numbers (last prime, test number, and the divisor) using 90 LEDs. The picture above is of the main circuit board before I began soldering. The empty sockets will house a combination of 8-bit shift registers, binary-to-digital converters, and 7-segment display drivers all powered by an ATMEL ATMega8 microcontroller crystal-clocked at 10.042 MHz (arbitrary, but stable). Here’s what the underside looked like before I began soldering:

I anticipate that this project will develop into a soldering nightmare. The board is nearly too small as it is, and I don’t have good wire for soldering. (I’m actually using the small wires from an old phone cord right now.) I included a potentiometer, 2 buttons, and 3 switches to aid with various settings (brightness, menus, etc). 3 Rows of LEDs (60 pins each) requires 12 shift registers (16 pins each) plus the 28-pin microcontroller makes about 400 solder points (YIKES!), so I anticipate the underside of this project will quickly grow to become a daunting mess of wires. Last night I finished the connections necessary to program the microcontroller, and for the microcontroller to control a single 8-bit shift register, allowing the first 8 LEDs of the first number to be controlled. Here’s what the soldering looked like. Remember, the dense clump of connections only controls 8 LEDs, so multiply this by more than 10 and that’s what I’ll have to do JUST to power the display.

After programming with a straight-through DAPA style parallel-port programmer, I was able to shift data out to the single HC595 I had wired. I spent hours banging my head against the wall because nothing I did in the software would make the LEDs illuminate. I thought I was sending signals to the shift register wrong, or that I soldered something wrong. I finally concluded that somehow (probably when I was troubleshooting by applying 5v of power directly to the pins of the shift registers) I managed to burn out all 8 LEDs of the first light bar. I had to de-solder ALL of the connections you see in that picture, replace the bar with a new one (thank goodness I had an extra), and re-solder everything. I have a feeling that by the end of this project, I’ll be an expert at soldering. Here’s the program running controlling the first 8 bits only:

Supposedly the hard part is done for the display. The software was written in such a way that it will automatically begin lighting-up more LEDs as I wire them. The small node for the first shift register and 8 LEDs will be identical to the other 11, and as I solder them one by one I’ll get closer to my end goal. It will probably be many hours of soldering. In retrospect, I wish I purchased a bigger perfboard. Actually, in retrospect I wish I made a PCB!!

Update: After a few more hours (of soldering, troubleshooting, desoldering, and rewiring, and resoldering) I have my second 8-bit segment working. Note all the yellow (newly-added) wires. Multiply this by 10, and that’s what I have left to wire for the display alone!


Prime-ary Prototype: Complete!

For the last several weeks I’ve been hacking together a small prototype of a microcontroller (ATTiny2313)-powered prime number generator. I can finally say that it (the prototype) is complete, functional, and elegant [get the song I’m referencing while it’s up!]. The name says what it does, so I won’t waste time describing it. If you’re interested in how it does what it does, check out the other posts with the same category tag for a full (and I mean full as in “more than you ever wanted to know”) description. A schematic is soon to come. Code is below. For now, here’s a video of the completed project:

And the source code I used. I chose the ATTiny2313 because it was cheap (~$2) and has 18 IO pins to work with. I had to fight memory usage every step of the way. I’m limited to 2kb, and this program compiles within 1% of that! For future projects (more LEDs, more menus) I’ll use the 20-pin and/or 40-pin ATMega series. I’m thinking about having one be in charge of the display (multiplexing) leaving the other to think about generating prime numbers.

#define F_CPU 10240000
#include <avr/interrupt.h>
#include <util/delay.h>
#include <math.h>

// ~~~ PORT D ~~~
#define r1 0b00000100
#define r2 0b00000010
#define r3 0b00001000
#define r4 0b00100000
#define r5 0b00010000
#define f1 0b01000000
#define id 0b00000001
#define f0 0b10111111

// ~~~ PORT B ~~~
#define c1 0b00010000
#define c2 0b00000001
#define c3 0b00000010
#define c4 0b00000100
#define c5 0b00001000

char delay=1;
int redo=0;

char rows[] = {r1,r2,r3,r4,r5};
char cols[] = {c1,c2,c3,c4,c5};
char vals[] = {0,0,0,0,0};
char funcs=f1+id;
unsigned long showNum=5;//33554431;

void displayNum();
void incrimentNum();
void menu_pause();
void menuCheck();
char button();
char isPrime(unsigned long);
unsigned int twoTo(char);

int main(void) {
  DDRD = r1+r2+r3+r4+r5+f1+id;
  DDRB = c1+c2+c3+c4+c5;
  DDRB &= ~_BV(DDB7);
  PORTB = 0;
  PORTD = 0;
  unsigned int i=0;
  int j;
  while (1) {


    if (isPrime(showNum)){

    for (j=0;j<redo;j++) {
    if (i%10==0){funcs^=r1;
      if (i%100==0){funcs^=r2;
        if (i%1000==0){funcs^=r3;i=0;
  return 0;

char isPrime(unsigned long test){
  if (test%2==0) return 0;
  unsigned long div = 3;
    if (test%div==0) return 0;
  return 1;

void menu(){
  char j,but;
  but = button();
  if (but==0) return;
  else if (but==1){
    while (1) {
      if (PINB & _BV(PB7)) {
        for (j=0;j<200;j++){
          if (j%25==0) funcs^=r1;
      else {
        if (redo==0) redo=200;
        else redo=0;

char button(){
  if (PINB & _BV(PB7)) return 0; // not pressed
  if (PINB & _BV(PB7)) return 1; // pressed
  return 2; // held down

void convertNum(){
  char col,row,rowcode;
  unsigned long msk=1;
  for (col=0;col<5;col++){
    for (row=0;row<5;row++){
      if (showNum&msk) rowcode+=rows[row];
      msk = msk < < 1;

void displayNum(){
  char i,j;
    PORTB = 0b0;
    PORTD = funcs;
    for (i=0;i<5;i++){
      PORTD = vals[i];
      PORTB = cols[i];


Time Prediction by Curve Fitting

I decided to crank up the power on my prime number identifier and attempt to document its efficiency in both C (GCC) and Python. I used the [very inefficient] code from the previous entry, modified it to test every integer up to 1×10^8, and let them both run on my laboratory computer overnight (an AMD Athlon 64-bit X2 Dual Core 2 GHz PC with 2GB of ram). The Python program took 3.24 processor hours, and the C program took 1.85 processor hours to complete. Each step along the way each program recorded how long it took to test the last 10,000 integers, creating a logfile with 1,000 data points, which can be easily graphed (see previous entry). On this nice, fast computer the data look very clean and curve-like. I curve-fitted the data using my new favorite website, ZunZun.com. Here’s what I came up with…


### C (GCC) ###
a =  1.4193535434065586E-03
b = -1.2708466972699874E-07
c = -4.9489218065978358E-16
d =  1.3032518272036044E-11
e =  1.3231610935638881E-06

### PYTHON ###
a =  2.6579973323520396E-03
b = -2.8299592901357803E-07
c = -1.2080374779761445E-15
d =  3.0281624700595501E-11
e =  2.4778595094623538E-06

### Generating Data Points: ###
for x in range(len(values)):

Note that this fitted curve is the representation of how long (in seconds, vertical axis) it takes to systematically test 10,000 integers for primeness (starting at an integer on the horizontal axis), This does NOT represent how long it takes to reach a certain X. To properly calculate this, one would need to integrate the equation. This would allow for the easy prediction of how long it would take to reach a certain integer (the solution would be the integral of the provided equation from 0 to the integer). I’ll let someone else attack that. It’s time for me to get back to work!


Determining the Prime-ary Language

While working on my current microcontroller project I’ve become a little obsessed with the prospect of rapidly generating lists of prime numbers. I’ve been testing various strategies for speeding up the process using logic modifications to a base concept. I’ve been doing my conceptual work in Python because it’s so fast and easy to rapidly develop applications with. Now that I have a good understanding of my strategy (code scheme) of choice, I’m starting to wonder how much better the same code would run in C. It’s no secret that Python’s strength is its versatility and ease of development of scritps, not its speed. C on the other hand can be very cumbersome and awkward to develop with, but its compiled code is very efficient so it’s better suited for mathematical applications which require billions of repetitive tasks.

To visualize the speed difference between C and Python, I wrote the same prime-number-testing code in both languages and timed their output. Basically I wrote identical code in each language (variable names and functions are the same, almost a line-by-line translation) and timed how long it took to find all prime numbers up to 10,000,000. (It reported the length of runtime at every 100,000 integers, totalling 100 time points).

The results:
The black line is code written in C and the blue line is Python. According to this output, Pythin is about 4 times slower than C at identifying primes utilizing the identical method. I’m not a coding expert, and there may be better ways to code/compile things in each language, so I’ll asy this is an indication of speed rather than a detailed, scientific study comparing the two languages. For fairness, I’ll provide my code.

Python code to generate prime numbers up to 10^7:

import time
def isPrime(testPrime):
	for div in xrange(2,int(testPrime**.5)+1):
		if testPrime%div==0: return False
	return True

def testSpeed(startAt, stopAt):
	startTime = time.clock()
	for testPrime in xrange(startAt,stopAt):
		if isPrime(testPrime):
	print s

for i in range(100):

C code to generate prime numbers up to 10^7:

#include <stdio.h>
#include <math.h>
#include <time.h>

char isPrime(int testPrime){
     int div;
     for (div=2;div<(int)sqrt(testPrime)+1;div++){
         if (testPrime%div==0) return 0;
     return 1;

void testSpeed(unsigned int startAt, unsigned int stopAt){
    int primesFound=0;
	char buf[256],len;
	unsigned int testPrime;
    clock_t startTime = clock();
        if (isPrime(testPrime)) primesFound++;
	FILE *fptr = fopen("log_c.txt","a");

int main(){
	char i;
	for (i=0;i<100;i++){
    return 0;

Python code to graph the difference utilizing MatPlotLib:

import pylab

def graphIt(fname,col):
	for line in data:
		if line.count(',')<3: continue
	return [val,time]

pylab.title("C vs Python: test 10,000 numbers for primeness")
pylab.ylabel("time (seconds)")
pylab.xlabel("starting value")
pylab.ylabel("time (seconds)")
pylab.xlabel("starting value")
for x in range(len(v)):
pylab.ylabel("speed ratio")
pylab.xlabel("starting value")