C64 prime number generation

Test program prime.c:

#include <stdio.h>

#define N 65535u
#define N2 32767u
#define N8 8192u

#define TEST_BIT(a, i) (a[i >> 3] & (1 << (i & 7)))
#define CLEAR_BIT(a, i) a[i >> 3] &= ~(1 << (i & 7))

unsigned char a[N8];

int main()
{
	unsigned int i, j;
	unsigned long sum = 0;
	unsigned int count = 0;

	for (i = 0; i < N8; i++) a[i] = 255;
	for (i = 2; i < N2; i++) {
		if (TEST_BIT(a, i)) {
			for (j = i + i; j > i; j += i) CLEAR_BIT(a, j);
		}
	}
	for (i = 2; i < N; i++) {
		if (TEST_BIT(a, i)) {
			sum += i;
			count++;
		}
	}
	printf("%u primes below %u\nsum: %ld\n", count, N, sum);
	return 0;
}

Compiled with cc65: prime.prg (compiled with "cl65 -O -t c64 prime.c -o prime.prg"). To avoid using "unsigned long" for the inner loop variable "j", I've used a hack: instead of comparing "j < N", I use "j > i", which detects a 16 bit wrap around.

Runtime in VICE: 2:58 minutes. Size: 3,282 bytes. Output:

Handwritten assembler version, not optimized: prime.asm. Compiled with CBM prg Studio: prime-assembler.prg

Runtime: 28 seconds. Size: 638 bytes. Output:

Another implementation from mar77i from #c64 at Freenode: https://github.com/mar77i/c64_experiments/blob/master/primes/primenums Needs 15 seconds. prg file, compiled with the nice macro assember dasm: prime2.prg

Conclusion: I wrote the C program in about 15 minutes, for the assembler program I needed some hours (I forgot many details of the 6502 instructions). The assembler program is about 6 times faster than the C program. The C version is about 5 times larger, maybe because of big printf overhead. So if you don't do it for fun, and if you don't need the maximum speed, it is better to use cc65 instead of assembler for writing programs for the 6502. And even for many performance critical programs you can use inline assembler for the performance hot-spots, and C for the rest.