Hunting Primes on Embedded Systems

One way of finding prime numbers is to use the Sieve of Eratosthenes. This starts with a list of all numbers 2-n. You find the first number in the list, which is prime, then remove all of its multiples from the list. Then repeat.

This is advantageous on an embedded platform because it doesn't involve very much computing. The drawback is that you can't store a huge list of incremental numbers; you quickly run out of space.

The Index is the Huge Number

The solution I came up with is to use one huge number as the index for a boolean array. Basically I create an array of 32-bit integers, using as much SRAM as I have available. The sieve will read that array like so:

1. Find the first bit in the array that is a 1. The index of this bit is a prime number so print it out

2. Iterate all indices that are multiples of this prime index, setting their bit in the array to 0

3. Repeat until the array has been exhausted

Bit Banding to Save Cycles

The reason I started this afternoon adventure was to try out bit-banding. This is an address alias in the ARM core which maps to a single bit in SRAM (also works on some of the peripheral buses). This should save quite a bit of time since the alternative is a three-step process of reading the register, performing a bitwise operation to change the bit in question, then writing the register. Bit Banding can do this all in one operation.

Basic Code for Bit Banding

I'm using a Tiva C Launchpad but the bit banding feature is a part of the ARM core so this should be the same on other ARM chips. TI has been kind enough to include a macro that does all of the heaving lifting. This wasn't readily apparent to me at first so I was trying to do the offsetting mentioned in TI's datasheet which is much more convoluted. The macro method is dead simple:

//#######Bit Band Write Operation
HWREGBITW(&targeRegister,targetBit) = 0;

//#######Bit Band Read Operation
myVar = HWREGBITW(&targeRegister,targetBit);<br>

The first parameter is the register address, the second is the bit location within that 32-bit register.

The macro HWREGBITW is defined in the int/hw_types.h file and takes care of the alias region offset (0x02000000) and the word and bit shifting to arrive at the final address. What you get back is simply a memory address that is written to or read from. Very neat:

#define HWREGBITW(x, b) HWREG(((uint32_t)(x) & 0xF0000000) | 0x02000000 | (((uint32_t)(x) & 0x000FFFFF) << 5) | ((b) << 2))