Page 1 of 1

Processor wars: Eratosthenes Sieve

PostPosted: Mon Jun 20, 2005 12:00 pm
by Trygve
you've talked the talk, but can you walk the walk and PROVE beyond doubt that your favorite processor is better than the rest, at a given clock speed, that is?

Quite simply, write a program in assembler which finds Prime numbers based on Eratosthenes Sieve:

The Sieve of Eratosthenes identifies all prime numbers up to a given number n as follows:

1. Write down the numbers 1, 2, 3, ..., n. We will eliminate composites by marking them. Initially all numbers are unmarked.
2. Mark the number 1 as special (it is neither prime nor composite).
3. Set k=1. Until k exceeds or equals the square root of n do this:
-Find the first number in the list greater than k that has
- not been identified as composite. (The very first number
- so found is 2.) Call it m. Mark the numbers

- 2m, 3m, 4m, ...

- as composite. (Thus in the first run we mark all even
numbers greater than 2. In the second run we mark
all multiples of 3 greater than 3.)
- m is a prime number. Put it on your list.
- Set k=m and repeat.

4. Put the remaining unmarked numbers in the sequence on your list of prime numbers.


Anyway, write the program in assembly, but... make no assumptions for any hardware beyond assuming the machine has a reasonable amount of RAM.
No need to design any IO. Just make certain that all Primes are stored in consecutive order on a known location.
To make it easy, we'll keep the challenge to 8bit (255)
You're also allowed to make modifications to the program to fit your processor better, as long at the starting conditions and the overall theory behind it is the same.

To make it difficult, though:
Post the complete source in a separate topic here in this forum, with explanations AND the number of cycles each instruction uses, so that the total running time can be calculated accurately.

When(or if) you have a result, PM me and I'll add the result to this thread.

If you can redesign the program for a processor, and make it faster, by all means do so, and I'll update the results.