Expand description
§Memory Efficiency
As we discussed previously, primes get sparser over time. So if we start with 10 thousand primes, we know after this whole process, we’ll be left with only 1229 as prime. That is, more than 80% of the memory we created went in vain.
However, there’s another lingering problem that we haven’t tackled. What do we do with our prime sieve after we crossed off all nonprimes? We need to store those primes somewhere.
§What’s the most efficient way to store raw prime numbers?
That’s a really vague question, which includes lots of factors. One of them will always arise from any question regarding “memory efficiency”, which is the most efficient way to store any information. That involves compression, which will be dealt with later on. Right now, we only care about listing prime numbers.
We can also optimize data storage by, instead of storing the data itself, we store a function that can generate the data. That will also be dealt with in the future. Right now, we only care about storing the data itself.
The most straightforward way is to list the primes, perhaps as a u32, and simply store that
in a file. It’s easy to encode and decode. Unfortunately, if we decided to store the first 200
million primes, the file size will be ~800MB.
The first optimization idea could be to notice that the first of these primes are small, and don’t need to be stored as a 4 byte number. Maybe 1 byte or 2 bytes suffice. The first 54 primes can be stored in 1 byte, then the next 6488 can be stored in 2 bytes. We can also encode the next 1,071,329 primes in 3 bytes, leaving the remaining 198,928,671 to be stored in 4 bytes. Unfortunately, that only compresses ~800MB into ~775MB.
§The Law of Excluded Middle
If you’ve ever studied logic, you may have come across that law. It states something really intuitive, but incredibly powerful for mathematical theorems:
Every statement is either true or false. Never both, never neither.
With this, we can determine that every integer is either prime or not. Because every time we say “N is prime”, that statement is either true or false. Within the context of programming, we can associate the state of being prime or not as a 1 or a 0.
This way, we can make a huge array (or, in a more dynamic context, a vector) of bits, where
the position i will store wether the number i is prime or not.
0 1 2 3 4 5 6 7 8 9 ...
0 0 1 1 0 1 0 1 0 0 ...In this context, it’s a little harder to ask “how much memory it takes to store the first N primes” because now we’re storing according to all numbers, not just primes. So we need to first ask when will we reach the Nth prime, then divide that by 8 to get the amount of bytes it’ll take.
The 200 millionth prime is around 4.2 billion. Which means, in order to reach there, we’ll need 4.2 billion bits, which is ~525MB. Already a big improvement.
§We’re not done!
Hopefully you already know that 2 is the only even prime. That means, after 2, every bit in an even position will be guaranteed to be a zero. That’s a lot of useless information! Specifically, close to half of our data is unnecessary! So we can heavily improve our system by only listing odd primes, and when we want to decode our data, we hardcode an extra 2 that will be missing!
1 3 5 7 9 11 13 ...
0 1 1 1 0 1 1 ...However, we can generalize this idea. Obviously, 3 is the only prime divisible by 3. So after 3, all positions divisible by 3 (9, 15, 29769…) will also be a guaranteed zero!
So we can ignore all positions that aren’t divisible by either 2 or 3! First, we multiply these two
to get 6. Now, we notice that for any number N, N % 6 == k, where k is in the range (0..6). If
k is 0, 2, or 4, N is definitely divisible by 2. If it’s 3, N is definitely divisible by 3. That means
the only possible primes, after 3, are the numbers where k results in 1 or 5.
1 5 7 11 13 17 19 ...
0 1 1 1 1 1 1 ...How much are we improving here? Well, in the beginning, we were storing every number as a bit. Which
means the bit to number ratio was 100%. When we excluded even numbers, it became 50%, because it
takes 1 bit to store info about two numbers (since the second one is even, we know it’s not prime).
Once we excluded numbers divisible by 2 and 3, we went from 6 possible values of k to just 2. Meaning
the bit to number ratio became ~33%.
And we can keep going. Adding 5 into the mix gives us a multiple of 30 (235). Out of the 30 possible
values of N % 30, 15 are even, 5 are odds multiple of 3, and other 2 are only multiples of 5. So we
have 8 possible prime candidates out of a 30 number range. ~26%.
However, as the range increases, we’re increasing the size of the chunks of bits we need to decode. For the previous example, we had to encode it in chunks of 2. One for k = 1, and the other for k = 5.
By adding 5 and increasing the range to 30, we have 8 possible primes, meaning the chunk size is now an entire byte. As we increase the amount of primes to discard, we also increase the chunk size.
| Primes | Range | bit/N | Chunk Size |
|---|---|---|---|
| None | 1 | 100% | - |
| 2 | 2 | 50% | 1 bit |
| 2,3 | 6 | 33% | 2 bit |
| 2,3,5 | 30 | 26% | 8 bits |
| 2,3,5,7 | 210 | 23% | 48 bits |
As you can see, when we add 7, the chunk size becomes 6 times larger, while we go from 26% to 23%. We want to avoid big changes for small improvements. Not only that, but using just 2, 3, and 5 lets us have exactly 1 byte of chunk size. Neat and tidy.
§Recap
How will our data look like? We know that every byte is a chunk of prime candidates, that are either
prime (1) or not prime (0). Each bit represents a number N, so that when you evaluate N % 30, it’ll
return some k that is not divisible by 2, 3 or 5. Specifically, these k values:
[ 01 07 11 13 17 19 23 29 ]
A byte by itself doesn’t give us the full picture though. We can’t extract N from k. So if we want to find out the numbers in a given chunk, we need some “offset” value, such as 29. Then, we can multiply the offset by 30, and we can sum each k value to that result, yielding N. Example:
{ offset: 29, byte: [01111000] }
First, we multiply the offset. result = offset * 30 = 870. Then, we notice the k values that are
ones (a.k.a, prime numbers) are 7, 11, 13, and 17. Summing those by 870 gives us the numbers:
877, 881, 883, 887
If our data isn’t wrong, we officially decoded all prime numbers between 870 and 900!