3 ms·

Isn’t “the ratio of logs” going to be slower?

• o11c 2y ago
  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