developer's mag
main page
article
part 1
part 2
part 3
part 4
part 5
part 6
part 7
part 8
part 9
2 - Assembly Sieve
Our program is a popular benchmark program, the Sieve of Eratosthenes. This prime selection method is very easy to learn and code: set up a list of numbers, start at 2, and cross off every multiple (4, 6, 8, etc). When you've reached the limit of the numbers you are checking, go back and continue with 3, and so on. If the next number is crossed off, simply skip it and move on. Eventually you are at the end, and the uncrossed numbers are all the primes. (An entertaining Java version of the Sieve in action is available online, and is worth a visit)Since the Sieve is so simple, we might be tempted to code it right away in C, resulting in something like the following:
void PerformSieve(int *array,int limit)
{
// pass in array already cleared
for (int i=2;i<limit;i++)
{
for (int k=i+i;k<limit;k+=i)
array[k]=1; // mark item as composite (non-prime)
}
}
Although this will work, it can benefit from
some optimizing:
- Since our test is binary (prime vs. composite), we can use a single bit instead of an int for each number.
- All even numbers after 2 are composite, so we don't need to test or store these values.
- Additionally, all even multiples of odd numbers are themselves even, so we can skip them as well.
- The upper limit test is wasteful - for each odd number, the first multiple we need to check is not 2*n (which is even) but 3*n, so our outer loop is finished when we fail the test i*3<limit (or i<limit/3, which allows us to make limit/3 into a constant).
- Unnecessary code in the loops is a cycle stealer - we should try to move as much as possible from the inner to the outer loop, or even outside of that if possible.
Previous Section
Next Section