Embeded Sieve of Eratosthenes

Hunting Primes with Microcontrollers

Similar projects worth following
As with most of my projects this came about because I made up a reason to do it. I wanted to explore Bit Banding on ARM microcontrollers. Hunting for prime numbers using the Sieve of Eratosthenes is a good way to do this.

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

  • 1 × TI Tiva C Launchpad
  • 1 × FTDI Breakout Board

  • Serial Problem with Tiva C Launchpad

    Mike Szczys03/23/2014 at 20:33 2 comments

    I'm getting really weird performance from the Tiva C Launchpad when using the UART. The board itself is an ICDI programmer but it also serves as a serial terminal at /dev/ttyACM0. The problem I'm having seems to be with synchronization. Some of the characters will be dropped, but other times I get complete gibberish. At any rate, I have the firmware looping at after a minute or two everything is rock-steady, but the unstable performance returns once again after power-cycling.

    I was developing this via SSH, with my production machine in the other room while I was on the sofa watching March Madness. I pulled out an FTDI breakout board; only needing to hook up one wire from TX on the Launchpad to RX on the FTDI (both are running from USB on the same machine which serves as the ground reference).

    Has anyone else experience this serial performance issues before?

  • Open Source Tiva C Template

    Mike Szczys03/23/2014 at 19:45 0 comments

    It took me a while to figure out how I wanted to do this, but I now have a functional template that works with TI's restrictive licensing on their example files.

    This open source template is a starting place for those interested in bare-metal programming Tiva chips using open source tools. It uses the libraries from the TivaWare package, as well as the example linker script and start code. Since neither of those files can be included in an open source repo, the Makefile creates symbolic links before compiling the package.

  • TI's Restrictive Example Files

    Mike Szczys03/23/2014 at 19:40 1 comment

    First off, TI I love your dev boards (and obviously your chips) but I hate your copyright statement on the top of all of the demo files in the TivaWare package. I can't put code up for this project yet because of this statement:

    You may not combine this software with "viral" open-source software in order to form a larger program.

    I'm working on my own Makefile to get around this nonsense.

View all 3 project logs

Enjoy this project?



Rhys wrote 03/24/2014 at 13:06 point
TI's licensing on large portions of TivaWare is rather frustrating. I've been working with USB related projects on the Launchpad for a while now. It really sucks when all you can post is your code and instructions on how to setup the build environment, as you can't just drop a complete project on GitHub without risking TI's lawyers knocking on your door if the project gets popular enough for them to notice.

It's the same reason there is no USB device/host support for the Tiva Launchpad in Energia, the licensing for the USB library precludes adding it to a "Viral" open source project. WTF is "Viral" supposed to mean, and why would TI put out an awesome, inexpensive, project board and then restrict the crowd that they want to use it from actually doing so in the manner in which they are accustomed to with every other development board out there.... Very frustrating.

  Are you sure? yes | no

Similar Projects

Does this project spark your interest?

Become a member to follow this project and never miss any updates