Re:Optimizing uint64_t Digit Counting: A Method that Beats L...
by o11c on Tuesday January 07, 2025 @08:14PM
(#42629796)
Honestly? Most of the time you can use an approximation. At worst you allocate a single extra byte unless your integers are hundreds of bits long (I worked this out once but I forget where I left the details). Just multiply by the ratio of logs or something like that.
[ Parent
| on HN ]
Re:Optimizing uint64_t Digit Counting: A Method that Beats L...
by Nevermark on Tuesday January 07, 2025 @11:18PM
(#42630856)
Nice. The best kind of optimization: Go lazy, to go fast.
I often go slow, to go fast. But lazy is the supremum.
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
Re:Optimizing uint64_t Digit Counting: A Method that Beats L...
by exyi on Wednesday January 08, 2025 @04:22AM
(#42632443)
I'd assume that the serializer is writing directly into the output buffer, so you'd have to shift everything left by one character if you overallocate. With the added checks for this, it might be faster to compute it precisely the first time.