Computing stuff tied to the physical world

Number crunching on a DIP

Did you know that the LPC810 knows over half a million prime numbers?

Well, maybe that’s a bit of a stretch, but it really can calculate that many primes (a lot more actually, if you’re willing to investigate some additional coding tricks).

Here’s a somewhat shortened version of the code from the primes demo on GitHub:

uint32_t limit = 3, numFactors = 0;

for (int value = 2; value < limit; ++value) {
    int i;
    for (i = 0; i < numFactors; ++i)
        if (value % factors[i] == 0) // check divisibility
            break;
    if (i < numFactors)
        continue; // found a factor, so it's not prime

    printf(" %d", value);

    if (numFactors >= 400)
        continue; // no more room left in the factors table

    factors[numFactors++] = value;

    limit = value * value; // largest prime we can check for
}

This is essentially the Sieve of Eratosthenes, coded in C. The idea is to save the first N primes in RAM, to easily factor them out from the next candidates. It’s just plain math.

With 1 KB of RAM, there is room for 400 prime factors, probably even a bit more, hence this declaration at the top of the code:

    uint16_t factors [400];

The 400th prime is 2,741. That means we can check values up 2,741 x 2,741 = 7,513,081 for being a prime. After all, if a value X can be written as the product of N and M, then it must be at least the square of the smallest of those two factors.

There is not much use for this, probably – even less so on an embedded processor. But if you look at the entire example, you’ll see that there are some “#if __arm__” conditionals in there. This allows compiling and running exactly the same code on a “big” computer:

    gcc -o primes main.cpp && ./primes

Either way, the generated output will consist of 54,830 lines of text:

Prime numbers:
 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 [...]
 [...] 7512991 7513021 7513039 7513057 7513063 7513073
Found 509067 primes.

Evidently, it’ll be a lot faster on a multi-GHz CPU than on an LPC810 running at 12 Mhz.

But hey, it won’t beat this hand-soldered contraption for size:

DSC 4825

Here is the back side:

DSC 4828

This circuit, with three diodes if you look carefully, can be used to: 1) power an LPC810 from an FTDI interface and 2) upload code to it and 3) see the serial output it generates.

The point of this story is not that you can use a tiny chip to do the work of a big PC (though, yes… you can), but that it’s occasionally quite easy to write code in such a way that it’ll run on either one. By stubbing out the differences, you can develop parts of your project on a non-embedded machine, and port it to the ┬ÁC later – once it has been verified to work.

Due to the wonders of C/C++ and the inherently portable nature of such software…

Even actual hardware can at times be replaced by a simulated data feed, so that instead of actual input data, the code runs with data read from a file or generated on-the-fly. The three main benefits are: 1) dramatically faster edit/run/debug cycles, 2) a more controlled and repeatable environment, and 3) more development tools to build and test with.

[Back to article index]