Question about rules

[hamarb123]

Hi, I've devised an algorithm that is quite fast for the language it is and the base algorithm.
I believe that it is the base algorithm and it follows the rules, but I'm not certain.
It uses 8-bits for each stored value, but instead of storing every value, it only stores for the odd numbers starting at 3. It doesn't have any predefined primes (except 2 like the standard c++ one), so it's not a wheel algorithm.
Is this allowed? Is it 8-bits or 4-bits or other?
I don't see why it wouldn't be, but I wanted to check before I got it ready for PR.

[rbergen]

@hamarb123 I'm converting this question to a Discussion.

[rbergen]

If I understand your question correctly, there is an algorithmic aspect to the answer, and a storage one.

• The fact that you only store odd numbers starting at 3 is a characteristic of the algorithm you use. This is an accepted optimization within the boundaries of a base algorithm implementation. In fact, it's used in Dave's original first implementations, to the point that his implementations actively warn if you manipulate even numbers. I also believe I have yet to see an implementation that doesn't use it.
• The fact that you use 8 bits per value you do store is a storage characteristic, and makes that it is an 8-bit implementation.

[hamarb123]

Hi, thanks. I'll add my implementation when I'm more done with it.
(btw, the implementation I was looking at was https://github.com/PlummersSoftwareLLC/Primes/blob/drag-race/PrimeCPP/solution_1/PrimeCPP.cpp, and it seems like it also stores even values to me unless I'm missing something)

[rbergen]

Well spotted! You're right in the sense that it effectively uses 2 bits per prime candidate. I'll send a message to Dave to let him know. :)

[rbergen]

I've discussed this with Dave, and you can find the outcome of that conversation in my answer below.

[hamarb123]

Hi, if I'm not mistaken, that means that mine's an allowed base algorithm.
It would still be 8-bits right (rather than 4)?
Thanks!

[rbergen]

That's correct. Base algorithm, but 8 bits.

[louie-github]

This might be a little off-topic, but I've done something similar with my Julia implementation that I plan to submit in a PR later on.

Instead of storing only odd numbers, I generate a bit array of booleans with alternating true-false values by copying the byte 0x55 and truncating to the needed length, rather than going through the bitwise operations needed to set bits in said array. I think this could be considered a "pre-calculation" of sorts, which is why I also want to clarify whether this falls within the bounds of the "base" algorithm as an optimization on even numbers.

The rest of the algorithm is exactly the same as the normal base algorithm in the original implementation, the only step changed was that the first step, removing even numbers, is "optimized" or "pre-calculated" out. So, only 2 is a "predetermined" prime.

Would this be within the boundaries of a "base algorithm implementation"?

[rbergen]

If my internal hexadecimal/binary conversion logic isn't failing me, you're describing an alternating bit pattern as an alternative means of "skipping" even numbers. In itself, I don't see an issue with that from a base algorithm perspective in principle.

However, I think it does lead to one of two possible scenarios:

• you either implement an algorithm that considers every number (even and uneven) in the loop that seeks the next prime candidate, which I expect to be very inefficient because you have to cycle that loop twice as often as all other implementations do and check twice as many bits, or
• your algorithm only considers odd numbers (like all current implementations do), in which case you end up using 2 bits per prime candidate.

[louie-github]

Huh. I completely forgot about the "bits per prime" part of the solution. I'll take those into consideration, thank you so much!

[rbergen]

Based on a very sharp observation made by @hamarb123, I've had a conversation with Dave on the subject. The outcome is that it is allowed to allocate one bit per number within the sieve limit (including even numbers), regardless of if the algorithm itself only operates on the odd ones. Throughout the implementation, it may consider 2 (and only 2) a "known" prime.

That means that the description you provided earlier is indeed within the boundaries of a base algorithm implementation. I apologize for the earlier confusion on this point.

[davepl]

BTW, I have no issue with the omission of multiples of 2, which of course I do myself. My argument is that 2 is a special case anyway, being the only even prime. I am concerned that algorithms shouldn't use 8X the memory and then be compared to one another directly. So if solution_X uses bits and solution_Y uses bytes, I treat them separately. If an algorithm is fast enough to be a contender, it should use bit storage (either 1/2 or 1 bit) rather than 8 bits per candidate integer. If it's just a cool implementation and not a contender for fastest, then it can use bytes as sort of an "exhibition" implementation.

I still think it's important to have a mix. For all I knew, using bytes could be slower because you blow the cache away much faster, so until we had one of each, it was all just theory. So both types are welcome, but to vie for the crown...

(Just a random aside, not an official rule or anything!)

[hamarb123]

Thanks, I think mine's an interesting implementation, but also pretty fast.
I wrote an alternative version of the algorithm using bits 2 times, but scrapped it both times because it ended up running about 2.5x slower. I'm pretty sure I did something wrong, but I'll work that out later in another PR if I fix it. Personally, I'm not concerned by the memory usage of my algorithm, I just want it to be fast, but I do know that bit storage is an important step to speed.