Re: [PATCH v4 6/8] tracing/histogram: Optimize division by a power of 2

[Steven Rostedt]

On Tue, 26 Oct 2021 18:31:21 -0700
Kalesh Singh <kaleshsingh@xxxxxxxxxx> 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