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.

16 thoughts on “Embeded Sieve Of Eratosthenes: Hunting Primes On ARM

    1. In the addressing single bits feature. It’s ARM’s hack, and this is a useful application of it. It comes from the manufacturer, but still, tweaking the MMU to alias single bits to addresses is quite a hack IMO, never heard of it before. If this were a.f.c thought I’m sure there’d be 10 people pointing out some mainframe that did it in the 1950s. I wonder how afc is doing, hope they’re still mostly alive.

  1. You should mention the Tivaware licensing heartache from your project in this post, since I’ve struggled a lot with that recently. I want to like these parts, but I can’t get beyond the non-OSS compatible terms on portions of the libraries. Now that mbed is no longer online-only and is fully MIT licensed, I’ve transitioned to mbed-supported platforms (currently select LPC, STM32, Kinetis, and Nordic ARM) for new projects.

        1. That didn’t make any sense the first time I read it.

          BTW, the article on bit banding was pretty useless, too. Perhaps you might want to write a lucid description of what it is and how it works. And then include a full source listing.

    1. Yeah, I can’t figure out why TI (and other companies) go only half-way toward embracing the open source world. They have examples that build perfectly on GCC, but you can’t include a single one of those example files in your own repo because of the restrictive license.

      I’m not suggesting that they remove all licenses from TivaWare. I just want them to provide three files that can be used by anyone for any reason: a Makefile, a linker script, and a startup file. In my mind, the linker and startup are the biggest barrier to entry for ARM chips. Having these files would help usher in wider adoption.

      1. I used to work on the team that produced this software. The reason is because the company (rightly or wrongly) perceives that there is some IP value in the software and does not want to lose control of it. The only real restriction that they care about is that it can only be used with TI microcontrollers. We/they do not want someone to take the USB stack (for example) and port it to run on an ST (for example). But even putting a simple restriction like that causes an incompatibility with GPL-style licenses which is why you see the language about not combining it with viral licensed software.

        Having said all that, some of us developers realized that a lot of the code is low-value IP especially stuff that is tied to the hardware like low level drivers and header files with register addresses. There were 3 versions of StellarisWare/TivaWare that were released that had some components under a BSD-style license. The header files with all the registers and the driverlib were BSD-style licensed. The USB and graphics library etc remain under the proprietary license. There was also a single example project that had the makefile, linker script etc under BSD-style license (even though all the other example projects remained under proprietary license). See the “examples” directory.

        The 3 versions I know of are StellarisWare 9453 and 10636 and TivaWare 11577.

        I heard that after I left they reversed this policy but I dont know the reason.

        I found this: https://github.com/leonexis/stellarisware-bsd

        and this: https://github.com/travisg/lk/tree/master/platform/stellaris/ti

Leave a Reply

Please be kind and respectful to help make the comments section excellent. (Comment Policy)

This site uses Akismet to reduce spam. Learn how your comment data is processed.