News for hackers. Stuff that matters.
Re:Optimizing uint64_t Digit Counting: A Method that Beats L... by eapriv on Wednesday January 08, 2025 @02:32AM (#42631950)
Isn’t “the ratio of logs” going to be slower?
Re:Optimizing uint64_t Digit Counting: A Method that Beats L... by o11c on Wednesday January 08, 2025 @01:56PM (#42637274)
I mean the constant logs of the bases; you get to hard-code this in the algorithm.

One interesting coincidence is that log₁₀(2) ~= log₂(10) - 3, thus the 83 ~= 78 below.

If you use an 8-bit shift, depending on which direction you're going, you multiply the input length by 851 (which is 3*256 + 83) or 78, then shift by 8. This starts being wasteful at 23 bits, but is pretty cheap on 8-bit CPUs.

For a more accurate approximation (slackening at 289 bits), 217706 (3<<16 + 21098) or 19729, then >> 16