How to handle edge cases when allocating bits for the bits output tag?

[louie-github]

I apologize if the title was confusing, but I can't think right now of a better title.

Anyway, I have a question about the number of "bits the implementation uses to store the indication (flag) if a number in the sieve is a prime number, or not" guidelines for the bits output tag.

In PrimeC/solution_2/sieve_1of2.c, we have this snippet of code:

// We need to store only odd integers, so only half the number of integers
sieve_state->a=calloc(maxints/2/sizeof(TYPE)+1,sizeof(TYPE));

If I understand this correctly, this line allocates the necessary memory for the array of uints used to store the bit values.
For example, if the sieve size is 1 million and the uint type is uint64_t, then maxints/2/sizeof(TYPE)+1 = 1000000/2/64+1 = 7813 uints to store the odd numbers up to 1 million. This seems correct: 64 * 2 * 7813 = 1000000.

However, I also noticed that there is one edge case here where it might allocate one more uint that necessary: what if maxints is a multiple of 2 * TYPE?

For example, if TYPE is uint64_t and maxints is 128, then maxints/2/sizeof(TYPE)+1 would translate to 128/2/64+1, resulting in 2 uints being allocated to store the odd numbers until 128, even if 128 only needs one uint64 (64 * 2 * 1 = 128).

How would you consider this edge case in classifying the solution in terms of bits per prime candidate?
Thank you for your time!

[louie-github]

As another "edge case", in the solution I am currently writing, I use the same technique as described above to allocate the bit array.
However, for my solution, I consider the first index to map to the number "3", then the second index "5", and so on and so forth. Basically, I ignore 1, even if 1 is taken into account when allocating the memory.

This leads to more edge cases:

127 = 127/2/64+1 = 63/64+1 = 0 + 1 = 1 uint allocated
Allocated bits: 64 * 2 * 1 = 128 bits + 2 = all numbers up to 130 (good)

128 = 128/2/64+1 = 64/64+1 = 1 + 1 = 2 uints allocated
Allocated bits: 64 * 2 * 2 = 256 bits + 2 = all numbers up to 258 (same edge case as in main question; this could also fit in just one UInt64)

129 = 129/2/64+1 = 64/64+1 = 1 + 1 = 2 uints allocated
Allocated bits: 64 * 2 * 2 = 256 bits + 2 = all numbers up to 258 (another edge case; this could also fit in just one UInt64)

130 = 130/2/64+1 = 65/64+1 = 1 + 1 = 2 uints allocated
Allocated bits: 64 * 2 * 2 = 256 bits + 2 = all numbers up to 258 (another edge case; this could also fit in just one UInt64)

131 = 131/2/64+1 = 65/64+1 = 1 + 1 = 2 uints allocated
64 * 2 * 2 = 256 bits + 2 = all numbers up to 258 (good)

Note that I'm adding 2 to the number of bits to accommodate the fact that I ignore numbers 1 and 2 when setting bits. The first bit maps to the number 3.

I can easily make this approach more accurate to the first one by subtracting 2 before starting the divisions (or subtracting 1 after dividing by 2), but I was just wondering if I could avoid a few extra operations by allocating a little more memory than absolutely necessary.

[tjol]

sizeof(uint64_t) is 8, not 64. Looks like that solution over-allocates by a factor of 8? That should probably be fixed…

⌊(n+7) ÷ 8⌋ will give you the number of bytes needed to store n bits. If you want to allocate your array in larger increments, adapt the calculation accordingly.

As for the definitions of the number of bits: assume the sieve size is chosen in a way that fits perfectly with your alignment constraints (i.e. is a multiple of 8 or 64 or whatever), and if you have a few bits of padding at the end that's absolutely fine. What matters is how you address the flags.

[tjol]

(I've submitted PR #406)

[rbergen]

We had a rather extensive discussion with Dave about this, a while back. What it boils down to is that his main requirement for marking an implementation as a 1-bit implementation is that meaningful "bit twiddling" is used. Reserving individual bits for even numbers but never using them is fine, having a small over-allocation of the applicable "bit-hosting type" (integer or otherwise) is fine.

Over-allocating by a factor of 8 is a bit excessive, so identifying that one is a great catch indeed.