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…
img_2445

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

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:
dark_bars
wires1





Additional Resources

Bitwise programming techniques (manipulating binary numbers) is simple in theory, but it’s often hard to remember how to do specific tasks if you don’t do them often. Recently in my microcontroller programming endeavors (where you’re pressed to conserve every bit of memory) I’ve needed to perform a lot of bitwise operations. If I’m storing true/false (1-bit) information in variables, it’s a waste to assign a whole variable to the task (even a char, the smallest variable in C is a waste because it uses 8 bits of memory!). When cramming multiple values into individual variables, it’s nice to know how to manipulate each bit of a variable.

Questions like “how do I retrieve the value of a certain bit in a variable”, “how do I set the value of a certain bit in a variable”, and “how do I flip a certain bit in a variable” can eventually be answered by twiddling around with bitwise operators in C, but often the solutions you randomly discover this way are not elegant or efficient. This afternoon I ran across the following chart on an Arduino help site and although I’m not a fan of Arduino, I can certainly appreciate the chart. I hope you find it as useful as I did.

y = (x>>n)&1;    // stores nth bit of x in y.  y becomes 0 or 1.

x&=~(1<<n);      // forces nth bit of x to be 0.  all other bits left alone.

x&=(1<<(n+1))-1;   // leaves lowest n bits of x; all higher bits set to 0.

x|=(1<<n);       // forces nth bit of x to be 1.  all other bits left alone.

x^=(1<<n);       // toggles nth bit of x.  all other bits left alone.

x=~x;              // toggles ALL the bits in x.




Additional Resources

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;
  //convertNum();
  //showNum=5;
  while (1) {

    showNum+=1;

    if (isPrime(showNum)){
      convertNum();
    }


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

char isPrime(unsigned long test){
  if (test%2==0) return 0;
  unsigned long div = 3;
  while(div*div<test+1){
    if (test%div==0) return 0;
    div+=2;
    displayNum();
  }
  return 1;
}

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


char button(){
  PORTD=id;
  if (PINB & _BV(PB7)) return 0; // not pressed
  _delay_ms(1000);
  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++){
    rowcode=0;
    for (row=0;row<5;row++){
      if (showNum&msk) rowcode+=rows[row];
      msk = msk < < 1;
    }
    vals[col]=rowcode;
  }
  return;
}

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




Additional Resources

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…
curve_fit2

Coeffecients:

### 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: ###
Ys=[]
for x in range(len(values)):
     Ys.append(a*(x**.5)+b*(x)+c*(x**2)+d*(x**1.5)+e)

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!





Additional Resources

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:
findingspng
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):
	primesFound=0
	startTime = time.clock()
	for testPrime in xrange(startAt,stopAt):
		if isPrime(testPrime):
			primesFound+=1
	s="%d,%d,%d,%fn"%(primesFound,startAt,stopAt,time.clock()-startTime)
	print s
	f=open("log_py.txt",'a')
	f.write(s)
	f.close()
	return

for i in range(100):
	testSpeed(100000*i,100000*(i+1))
raw_input()

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();
    for(testPrime=startAt;testPrime<stopAt;testPrime++){
        if (isPrime(testPrime)) primesFound++;
        }
	len=sprintf(buf,"n%i,%u,%u,%f",primesFound,startAt,stopAt,
		(float)(clock()-startTime)/CLOCKS_PER_SEC);
	printf("%s",buf);
	FILE *fptr = fopen("log_c.txt","a");
	fputs(buf,fptr);
	fclose(fptr);
    return;
}

int main(){
	char i;
	for (i=0;i<100;i++){
		testSpeed(100000*i,100000*(i+1));
	}
    return 0;
}

Python code to graph the difference utilizing MatPlotLib:

import pylab

def graphIt(fname,col):
	f=open(fname,'r')
	data=f.readlines()
	f.close()
	val,time=[],[]
	for line in data:
		if line.count(',')<3: continue
		line=line.strip('n').split(',')
		val.append(int(line[1]))
		time.append(float(line[3]))
	pylab.plot(val,time,color=col)
	return [val,time]

pylab.figure()
pylab.subplot(311)
v,tc=graphIt('log_c.txt','k');
v,tp=graphIt('log_py.txt','b');
pylab.title("C vs Python: test 10,000 numbers for primeness")
pylab.ylabel("time (seconds)")
pylab.xlabel("starting value")
pylab.grid(alpha=.3)
pylab.subplot(312)
pylab.grid(alpha=.3)
graphIt('log_c.txt','k');
graphIt('log_py.txt','b');
pylab.ylabel("time (seconds)")
pylab.xlabel("starting value")
pylab.semilogy()
pylab.subplot(313)
ratios=[]
for x in range(len(v)):
	ratios.append(float(tp[x])/tc[x])
pylab.plot(v,ratios,'k')
pylab.ylabel("speed ratio")
pylab.xlabel("starting value")
pylab.axis([None,None,None,5])
pylab.grid(alpha=.3)
pylab.show()