ATtiny2313 prime number generator

posted Aug 24th 2010 6:00am by Mike Szczys
filed under: Microcontrollers

[Scott Harden's] prime number generator exhibits a great way to use an LED matrix to present readable information. The project resides in a hinged wooden box with a grid of holes on the lid for the LEDs. [Scott] has overlaid the matrix with a printout showing powers of two that represent different prime numbers. Inside you’ll find an ATtiny2313 microcontroller that handles the column scanning and prime number testing. We’ve embedded a video the break where [Scott] explains the project in great detail, but you should also check out his prototyping and construction pages.

Comments [9]

tagged: attiny2313, AVR, generator, led, matrix, prime number

9 Responses to ATtiny2313 prime number generator

ColinB says:

August 24, 2010 at 6:26 am

It’s weird that the photo has 2**13 twice but the video has 2**23 in the right spot.

Reply Report comment

ColinB says:

August 24, 2010 at 6:27 am

Huh, actually there are other problems with the photo as well! It starts at 2**1, for starters, instead of 2**0.

Reply Report comment

HackerK says:

August 24, 2010 at 7:49 am

Kinda useless but I *do* like this project. Very geeky!

Nicely done… ;)

Reply Report comment

HackerK says:

August 24, 2010 at 7:50 am

Oh next, is someone up for calculating the value of Pi using a PIC? :)

Reply Report comment

ehrichweiss says:

August 24, 2010 at 8:05 am

Fellas…regarding the double 12/13′s…he ran out of 2′s it seems…

Reply Report comment

Scott says:

August 24, 2010 at 8:56 am

Yeah, I screwed-up the first print (forgot 2^0 and have a misplaced 2^13) and re-printed it correctly before I shot the video. The code is the same obviously!

Reply Report comment

SparkyGSX says:

August 24, 2010 at 10:10 am

The code to find the next prime is horribly inefficient. Ofcourse, the AVR is rather memory-challenged, so a high efficient number sieve probably isn’t possible.

A few suggestions to speed it up:

- calculate the square root of the current number to be tested, instead of squaring the divisor every cycle

- keep track of some prime numbers in the available memory, so the intermediate numbers don’t have to be tested. Keeping the first X primes probably won’t help much, because the frequency of primes if much higher in the small number range, which means you effectively don’t skip many intermediate numbers. Keeping the last X discovered primes won’t do much good either, because most of the time, you won’t get that far before discovering a number isn’t a prime. Deciding which list to keep, if the space is very limited, is a bit of a challenge. Anyway, you could try to take advantage of the fact that any non-prime greater than 2 is dividable by a prime, so it would be best not to try non-primes as divisors, if possible.

Reply Report comment

Scott says:

August 24, 2010 at 2:01 pm

I’m a dental student, not an engineer or mathematician. Take my projects with a grain of salt and appreciate them for their educational value!

@SparkyGSX There’s no reason to make it run quickly. It’s a novelty, nothing more. I don’t think anyone expects this to rival supercomputers.

At the same time, the most effective algorithm I’ve come across to do this with limited memory is based upon “sieves using binary quadratic forms”, well-documented on http://cr.yp.to/papers/primesieves.pdf and it calculates MILLIONS of prime numbers every second on a standard PC. It’s what I used to calculate the first trillion prime numbers (2^15) on a SheevaPlug plug computer (it took a little less than a year to reach the trillion mark).

Right now it says that the 1,063,620,000,000′th prime number is 31,972,536,554,401. Ironically enough, there’s no way to check it online. The database http://primes.utm.edu/nthprime/index.php stops at 1 trillion, but it was accurate up to that point so I don’t doubt it.

Reply Report comment

amk says:

August 24, 2010 at 9:52 pm

Neat project Scott. I think we share a passion, finding weird things to do with prime numbers. I’ve spent the last 15 or so years coming up with weird ways to represent prime numbers, or more accurately the distribution of primes, in physical ways. There’s something therapeutic about it.

Reply Report comment