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




Additional Resources

In my quest to build a hardware-based binary prime number generator I decided to build a demonstration model / rapid prototype to prove to myself (and the world) that I can reliably (and quickly) generate prime numbers. This code needs a lot of work, but it’s functional. Instead of messing with tons of little LEDs, it just dumps the output to a LCD. Of note, the library to run the LCD takes up about 90% of the memory of the chip leaving only a handful of free bytes to write the actual code in!
img_1984

Keep in mind this is a PROTOTYPE and that the full version will have over 80 LEDs to represent every number in binary form (up to 2^25, 33.5 million, with 25 LEDs/number). For now, this version (which dumps data to a HD44780 LCD screen) serves as a proof of concept. Powered by an ATTiny2313.

Here’s some video:

Here’s the code responsible:

#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=3;primeTest<sqrt(primeMax);primeTest=primeTest+2){
    for(primeTest=2;primeTest<sqrt(primeMax);primeTest++){
        maybePrime=1;
        //for (i=3;i<=(sqrt(primeTest)+1);i=i+2){
        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));
    //_delay_ms(1000);
    return;
}

void init(void){
    lcd_init(LCD_DISP_ON);
    //lcd_clrscr();
    lcd_puts("PRIME IDENTIFICATIONn");
    //lcd_puts("MAX PRIME: ");
    //lcd_puts(toString(primeMax));
    //lcd_puts("nsquare root: ");
    //lcd_puts(toString(sqrt(primeMax)+1));
    _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;
}

In other news, I’ve seen the new Star Trek movie and found it enjoyable. My wife liked it too (perhaps more than I did). Here’s a relevant news story I found informative:





Additional Resources

After a day of tinkering I finally figured out how to control a HD44780-style LCD display from an ATTiny2313 class ATMEL AVR microcontroller. There are a lot of websites out there claiming to show you how to do this on similar AVRs. I tried about 10 of them and, intriguingly, only one of them worked! I don’t know if it’s user error, or an incompatibility of the ATTiny2313 running code written for an ATMega8, but since it took me so long to get this right I decided to share it on the internet for anyone else having a similar struggle. First, the results:
attiny_2313_lcd_hd44780
You might recognize this LCD panel from some PC parallel port / LCD interface projects I worked on about 5 years ago. It’s a 20-column, 2-row, 8-bit parallel character LCD. This means that ranter than telling each little square to light up to form individual letters, you can just output text to the microcontroller embedded in the display and it can draw the letters, move the cursor, or clear the screen.
attiny_2313_lcd_hd44780_2
As you can see this thing is pretty easy to wire-up to the ATTiny2313. These are the connections I made:

  • LCD1 -> GND
  • LCD2 -> +5V
  • LCD3 (contrast) -> GND
  • LCD4 (RS) -> AVR D0 (pin2)
  • LCD5 (R/W) -> AVR D1 (pin3)
  • LCD6 (ES) -> AVR D2 (pin6)
  • LCD 11-14 (data) -> AVR B0-B3 (pins 12-15)

The code I used to FINALLY allow me to control this LCD from the ATTiny2313 was found on Martin Thomas’ page. [HIS CODE] I included the .h and .c files and successfully ran the following program (with great results) on my AVR. The internal RC clock works, and supposedly any external clock (<8MHz) should work too.

// THIS THE TEST PROGRAM "main.c"
// ATTiny2313 / HD44780 LCD INTERFACE
#include <stdlib.h>
#include <avr/io.h>
#include <util/delay.h>
#include "lcd.h"
#include "lcd.c"

int main(void)
{
    int i=0;
    lcd_init(LCD_DISP_ON);
    lcd_clrscr();
    lcd_puts("ATTiny 2313 LCD Demo");
    lcd_puts("  www.SWHarden.com  ");
    _delay_ms(1000);
    lcd_clrscr();
    for (;;) {
        lcd_putc(i);
        i++;
        _delay_ms(50);
    }
}
// THIS IS PART OF MY INCLUDED "lcd.h"
// THE WIRING CHART DESCRIBED IN THIS BLOG ENTRY
// IS MATCHED TO THE VALUES DISPLAYED BELOW
#define LCD_PORT         PORTB        /**< port for the LCD lines   */
#define LCD_DATA0_PORT   LCD_PORT     /**< port for 4bit data bit 0 */
#define LCD_DATA1_PORT   LCD_PORT     /**< port for 4bit data bit 1 */
#define LCD_DATA2_PORT   LCD_PORT     /**< port for 4bit data bit 2 */
#define LCD_DATA3_PORT   LCD_PORT     /**< port for 4bit data bit 3 */
#define LCD_DATA0_PIN    0            /**< pin for 4bit data bit 0  */
#define LCD_DATA1_PIN    1            /**< pin for 4bit data bit 1  */
#define LCD_DATA2_PIN    2            /**< pin for 4bit data bit 2  */
#define LCD_DATA3_PIN    3            /**< pin for 4bit data bit 3  */
#define LCD_RS_PORT      PORTD     /**< port for RS line         */
#define LCD_RS_PIN       0            /**< pin  for RS line         */
#define LCD_RW_PORT      PORTD     /**< port for RW line         */
#define LCD_RW_PIN       1            /**< pin  for RW line         */
#define LCD_E_PORT       PORTD     /**< port for Enable line     */
#define LCD_E_PIN        2            /**< pin  for Enable line     */

// AND A LITTLE LOWER, I CHANGED THIS LINE TO 4-BIT MODE
#define LCD_FUNCTION_8BIT     0      /*   DB4: set 8BIT mode (0->4BIT mode) */

And some video of the output… Notice how this display can show English (lowercase/uppercase/numbers) as well as the Japanese character set! Sweet!





Additional Resources

UPDATE: I found a method of PC/microcontroller communication which I feel is simpler, easier, and definitely cheaper than this! It’s not good for everything, but worth looking at. It’s a way to communicate with a PC using your sound card and zero components!

Another page HERE has more info on how to do this with an intermediate IC if yours doesn’t have RX/TX pins…

I recently had the desire to be able to see data from an ATMEL AVR microcontroller (the ATTiny2313) for development and debugging purposes. I wanted an easy way to have my microcontroller talk to my PC (and vise versa) with a minimum number of parts. The easiest way to do this was to utilize the UART capabilities of the ATTiny2313 to talk to my PC through the serial port. One problem is that the ATTiny2313(as with most microcontrollers) puts out 5V for “high” (on) and 0V for “low” (off). The RS-232 standard (which PC serial ports use) required -15V for high and +15v for low! Obviously the microcontroller needs some help to achieve this. The easiest way was to use the MAX232 serial level converter which costs about 3 bucks at DigiKey. Note that it requires a few 10uF capacitors to function properly.

Here’s a more general schematic:

I connected my ATTiny2313 to the MAX232 in a very standard way. (photo) MAX232 pins 13 and 14 go to the serial port, and the ATTiny2313 pins 2 and 3 go to the MAX232 pins 12 and 11 respectively. I will note that they used a oscillator value (3.6864MHz) different than mine (9.216MHz).

Determining the speed of serial communication is important. This is dependent on your oscillator frequency! I said I used a 9.216Mhz oscillator. First, a crystal or ceramic oscillator is required over the internal RC oscillator because the internal RC oscillator is not accurate enough for serial communication. The oscillator you select should be a perfect multiple of 1.8432MHz. Mine is 5x this value. Many people use 2x this value (3.6864Mhz) and that’s okay! You just have to make sure your microchip knows (1) to use the external oscillator (google around for how to burn the fuses on your chip to do this) and (2) what the frequency of your oscillator is and how fast it should be sending data. This is done by setting the UBRRL value. The formula to do this is here:

The datasheet of your microcontroller may list a lot of common crystal frequencies, bandwidths, and their appropriate UBRR values. However my datasheet lacked an entry for a 9.216MHz crystal, so I had to do the math myself. I Googled around and no “table” is available! Why not make one? (picture, below). Anyway, for my case I determined that if I set the UBRR value to 239, I could transmit data at 2800 baud (bits/second). This is slow enough to ensure accuracy, but fast enough to quickly dump a large amount of text to a PC terminal.

>>> IMPORTANT UPDATE!

This will make your life easier. The page wormfood.net/avrbaudcalc.php has a chart of common crystals and the baud rates they work best with! Try to pick a combination that provides the least error possible...

This is the bare-minimum code to test out my setup. Just load the code (written in C, compiled with avr-gcc) onto your chip and it’s ready to go. Be sure you set your fuses to use an external oscillator and that you set your UBRRL value correctly.

  

  #include <avr/io.h>  

  #include <avr/interrupt.h>  

  #include <util/delay.h>  

   

 int main (void)  

 {  

   unsigned char data=0;  

   UBRRL = 239;  

   UCSRB = (1 < < RXEN) | (1 << TXEN);  

   UCSRC = (1 < < UCSZ1) | (1 << UCSZ0);  

   for (;;)  

     {  

     if (data>'Z'||data< 'A')  

     {  

       UDR = 10; UDR = 13; data='A';_delay_ms(100);  

     }  

     UDR = data;  

     data += 1;  

     _delay_ms(100);  

     }  

 }  

 

Once you load it, it’s ready to roll! It continuously dumps letters to the serial port. To receive them, open HyperTerminal (on windows, under accessories) or minicom (on Linux, look it up!). Set your baud rate to 2800 (or whatever you selected) and you’re in business. This (picture below) is the output of the microcontroller to HyperTerminal on my PC. Forgive the image quality, I photographed the LCD screen instead of taking a screenshot.

This is the circuit which generates the output of the previous image. I have a few extra components. I have an LED which I used for debugging purposes, and also a switch (labeled “R”). The switch (when pressed) grounds pin 1 of the ATTiny2313 which resets it. If I want to program the chip, I hold “R” down and the PC can program it with the inline programmer “parallel port, straight-through, DAPA style. One cable going into the circuit is for the parallel port programmer, one cable is for the serial port (data transfer), and one is for power (5v which I stole from a USB port).

I hope you found this information useful. Feel free to contact me with any questions you may have, but realize that I’m no expert, and I’m merely documenting my successes chronologically on this website.