Embeded Sieve of Eratosthenes: Hunting Primes on ARM

Embeded Sieve of Eratosthenes

I ended up with just enough time over the weekend to pull together a quick project. I implemented the Sieve-of-Eratosthenes on an ARM chip.

If you haven’t heard of the Sieve of Eratosthenes then you really need to work your way through Project Euler. That’s where I first learned about this method of finding prime numbers. You begin with a list of all numbers, find a prime, then remove all multiples of that prime from the list. The real trick with doing it on a microcontroller is to figure out how to store a large list of numbers in a limited space. The gist of my method was to use a boolean array (I call it a bit-packed array but that may be the wrong way of saying it). The details are found in my project linked at the top.

‘Why?’ is almost always the wrong question to ask around here. But in this case, I did this because I wanted to try out the Bit Banding functionality of the ARM core. These chips have alias addresses that map to a single bit in the SRAM and also some of the peripheral registers. This allows read or write access for a single bit using a single instruction. Turns out that one side effect of 32-bit architecture is having addresses to burn.

ATtiny2313 prime number generator

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

[Read more...]