Clarification request: interpretation of base / faithful=yes

[Kexisx]

Good Afternoon,

I wanted to ask for clarification on how strictly the base and faithful=yes classifications are intended to be interpreted.

This is not intended as criticism of any contributor or implementation. Some of the highly optimised entries are genuinely impressive, and I may simply be misunderstanding where the project draws the line.

My reading of CONTRIBUTING.md is that the base algorithm clears non-primes individually while increasing by 2 * factor each cycle, and that faithful=yes requires conforming to that base behaviour.

The reason I’m asking is that I had understood certain mask-pattern, precomputed, LUT-based, or chunk-reset style optimisations to fall outside base,faithful=yes. I may have been too conservative in that interpretation, so I’d like to understand the intended boundary before assuming anything either way.

The kinds of cases I’m unsure about are highly optimised reset paths that use generated dense/sparse resetters, precomputed or generated bit-mask patterns over words/chunks, dense/sparse LUT reset paths, or logic that may temporarily clear a prime factor bit and then restore it afterwards.

I am not suggesting those implementations are incorrect. I am only trying to understand whether those styles of generated/chunked/LUT resetter are considered acceptable for algorithm=base,faithful=yes, or whether they should be classified differently.

I’m asking in the interest of technical consistency rather than to challenge anyone’s work. The distinction matters because the leaderboard groups and compares entries partly by these tags, so it would be helpful to understand whether these optimisations are considered within the intended base,faithful=yes boundary.

Could someone clarify where the line is intended to be drawn between:

base,faithful=yes

and

base,faithful=no / algorithm=other

for highly optimised reset logic?

Thanks,
Chris

[rbergen]

It's an understandable question, and heavily debated in the early stages of this project, now almost 5 years ago.

The honest answer is that I can't give a 100% complete answer to your question in an up-front manner. I mean that in the sense that the rules try to be as unambiguous as possible, but will always leave room for some interpretation in certain cases, as various PRs have shown. Over the past 5 years, I have tried very hard for that interpretation to be applied as consistently as possible across the now close to 500 (benchmarked) implementations we have.

That said, my colloquial summary would be as follows:

• The algorithm is "base" when the fundamental rules you referred to for the base algorithm are followed. However, particularly in the second step (projecting the multiples of an identified prime onto the sieve space) we allow pretty far-reaching optimizations. What we do not allow is the use of any prior knowledge concerning any number being a prime, with the exception of 2. Implementatuions that do use such knowledge are either a wheel or other algorithm.
• Faithfulness is basically completely disconnected from whether the algorithm is the base algorithm or not. As the contributing guidelines stipulate, it concerns itself entirely with sieve encapsulation, per-run memory (re)allocation, enforcing that calculations need to be made at runtime, etc.
• The third aspect that decides if an implementation qualifies for the leaderboard is the number of bits of memory used per prime candidate. The required number (1) in practice actually translates to "~0.5 or 1", because many implementations only allocate and use memory for the odd numbers in the sieve space.

What may be visible is that the exact definitions of the relevant terms have matured in the beginning (I'd say first few months) of this project, which can lead to some early implementations that have been classified in a particular way not complying 100% with what the definitions then became. At the same time, the most aggressive optimizing programmers/language proponents have been very critical of the classification of competing solutions, and some classification "errors" have indeed been corrected.

On a personal note - and I've stated this a few times before - I think the use of the word "faithful" turned out to be an unfortunate choice, as it has a pretty comprehensive yet conceptual meaning in the real world.

I hope this helps.

[Kexisx]

Thanks, that was helpful and clears it up for me.