On Tue, 26 Oct 2021 18:31:21 -0700 Kalesh Singh kaleshsingh@google.com wrote:
And IIUC max_div is an arbitrary value we decide on that's <= 2^shift? Is there a rule of thumb for choosing this?
The way I came up with the max was to figure out at what point is it no longer guaranteed to be accurate. That is, what number can make the mult/shift no longer match the division.
If we have some number div that is not a power of two. At some point:
(X * mult) >> shift != X / div
Now I simply picked
max = 1 << shift / (mult * div - (1 << shift))
Because that will always be within the precision of the actual number.
But I believe we can make max bigger, but because that deals with truncation, it's not simple math.
That is, the above X / div is truncated and not the real number.
I'm sure there's an algorithm somewhere that can give as the real max.
-- Steve