I wanted to learn x86-64 assembly, so I made this program (I have not found any good name for it) which takes a positive integer as an argument, and ouputs to stdout all primes integers up to and including the argument.
$ make
as --64 -o primes.o primes.s
ld -o primes primes.o
$ ./primes 10
2
3
5
7
The program uses the sieve of Eratosthenes. Each numbers is represented by a bit in a bit array, which makes accessing a specific number a bit difficult, because it has to make some bitwise operations, but it means that the program uses 8 times less memory that if each number was represented by a byte.
I didn't use any external functions.
I used sys_mmap to allocate the bit array, and sys_write to write to
stdout and stderr.
I took some time to comment the code (what I don't usually do), so don't hesitate to take a look!
I'm sure compilers can make a better job optimizing code than me, but it's fast enough.
Example calculating primes up to one hundred million (100,000,000) on a AMD Ryzen 7 1700 at 4.00 GHz and 16 GB of DDR4-2933 RAM.
$ hyperfine './primes 100000000 > /dev/null'
Time (mean ± σ): 471.6 ms ± 3.1 ms [User: 467.7 ms, System: 3.1 ms]
Range (min … max): 467.0 ms … 476.1 ms 10 runs
The biggest limitation is the RAM usage, as it allocates number / 8 + 1
bytes.
For example, calculating primes up to one hundred billion (100,000,000,000)
will take 12.5 GB of RAM, and if you store the results, the file will take
near 50 GB!
- Async output
- Multithreading
- Use the segmented or incremental sieve