What is an efficent way to compute floor(log(m / n)), where m and n are integers?

user_5602689 0
Viewed 103

Basically, as title says. I would like to know of a way to compute floor(log2(x / y)), where x and y are nonzero unsigned machine integers, in as few cycles as possible (avoiding as much as possible the use of things like branches, memory bandwidth, division, etc that are expensive in tiny sections of code like this). The exact (integer) answer is required here. I was thinking about how to optimize the outer loop of Adaptive Shivers Sort by computing this efficiently, as it requires computing floor(log2(r / c)), where r is a run length and c a metaparameter to the algorithm; solutions that assume x <= y would work for the offline version of this sort, where c is chosen to be equal to the length of the input, but general solutions could be useful in other settings.

You can assume the use of PopCount and CountLeadingZeros/CountTrailingZeros, common SSE-style instructions, or even floating point computation--but it needs to be something which processors can do in just a few cycles.

micro-optimization assembly optimization c
2 Answers

How about something like this, inspired partly by a comment by NXTangl? Apply clz to both x and y and shift them both so their leading bit is in the top bit position (31 or 63). Let k be the difference between these two shift amounts. Now either k or k-1 is the result you're looking for, and you can distinguish the cases by which of the shifted value is greater.

user_3798970

Well, not a proper answer, but here are some interesting special cases.

Remember that log_k(x/y) = log_k(x) - log_k(y) for any k. Now,

  1. If y is a power of 2, floor(log_2(x/y)) = floor(log_2(x) - log_2(y)) = floor(log_2(x)) - log_2(y)
  2. If x is a power of 2, floor(log_2(x/y)) = floor(log_2(x) - log_2(y)) = log_2(x) + floor( -log_2(y)) = log_2(x) - ceil(log_2(y)) =
  3. If n is a non-negative natural number, then ceil(log_2(n)) = floor(log_2(2n-1))

Thus:

  • if x,y are powers of 2, we have:
    log_2(x/y) = (size_in_bits - ctz(y)) - (size_in_bits - ctz(x)) = ctz(x) - ctz(y)
  • If only y is a power of 2, we can also use ctz(x) - ctz(y) by argument (1).
  • If only x is a power of 2, we can use ctz(x) - ctz(2*y-1) by arguments (2), (3).

So, if you happen to be able to make one of these assumptions - or even, not make them in certainty but with high enough probability, you get quite an efficient calculation.

user_15930770
Related