1

Consider the function:

int log2di(double x) {
  return (int)log2(x);
}

Since the log2 result is immediately truncated to int, this can be much more efficiently implemented using1 std::ilogb or std::frexp.

How about this slight variation, where the log2 result is multiplied by an arbitrary double y before being truncated:

int log2di_mul(double x, double y) {
  return (int)(log2(x) * y);
}

Can it be efficiently implemented without an expensive general purpose log2 call?

1 Really this only applies to FLT_RADIX == 2 systems, but that's everything you are realistically going to care about these days.

BeeOnRope
  • 60,350
  • 16
  • 207
  • 386
  • 1
    That is not even a correct implementation; necessary rounding errors in the return value of `log2` is smaller than the actual logarithm, so that multiplying by `y` produces a lower result and results in a lower integer when truncated. – Eric Postpischil Jul 31 '20 at 02:27
  • 2
    `log2(x) * y` is essentially a logarithm with an arbitrary base (the base is 2^(1/y)). So no, there is no cheap implementation of it; its implementation is a general logarithm. – Eric Postpischil Jul 31 '20 at 02:35
  • @EricPostpischil - not even correct implementation of what? It is a faithful implementation of the function I have. About "is a general logarithm", well yes, log2 * x, is a general logarithm but I don't need that, I need (int)(log2 * x) which has, among other things, many fewer possible answers. Your argument would seem to apply equally to the `(int)(log2(x))` case, yet that one becomes much cheaper when you truncate it to `int`. – BeeOnRope Jul 31 '20 at 03:25
  • 1
    For any given FP exponent, the mantissa only leaves a small number of possible integer results. (Or non-small if `y` is large). For a small constant `y`, you might be able to get somewhere from replacing `x`'s exponent field with that of `1.0` (to get numbers in the [1.0, 2.0) range), then doing something with that on top of the log2() part from the exponent? Or some kind of table lookup based on the mantissa? – Peter Cordes Jul 31 '20 at 03:52
  • 1
    (This idea came from an (int)base10_num_digits(unsigned) idea that uses __builtin_clz to index a table length, with a fixup of adding another +1 if the value was >= a value from another table indexed the same way. Found that idea again at [performance of log10 function returning an int](https://stackoverflow.com/a/25934909), but I think I first saw it in a different SO answer.) – Peter Cordes Jul 31 '20 at 03:59
  • Yes, this idea crossed my mind: it seems like you can apply it in general to any FP function with a small number of outputs where the "shape" is roughly amenable to table lookup (log2, of course, is very amenable since expontent + some mantissa bits work well). – BeeOnRope Jul 31 '20 at 04:02
  • I'm not sure it's actually viable; if you need a different set of constants for every different exponent (because `y` isn't a power of 2), you'd need a 16384 entry lookup table (of small arrays to search). In the integer case, even if you could divide by `1<. – Peter Cordes Jul 31 '20 at 04:28
  • Re “not even correct implementation of what?”: `(int)(log2(x) * y)` is not a correct implementation of mathematical function floor(log2(x)•y). Here is a proof using IEEE-754 binary32 (simply to make it easier to demonstrate; failures also exist for binary64). Let x be 110,592 and y be 0.17905223369598388671875. The latter is the binary32 nearest 1/log2(48), and it is slightly above that. Then a correctly rounded `log2` for binary32 produces 16.754886627197265625 for `log2(x)`, and `log2(x)*y` evaluates to 2.9999997615814208984375, so casting to `int` yields 2. But floor(log2(x)•y) is 3. – Eric Postpischil Jul 31 '20 at 11:25
  • 1
    (There seem to be a few words missing in my original comment, I am guessing to do entry problems on a small device. It should say that necessary rounding errors in the return value of `log2` will sometimes yield a return value smaller than the actual logarithm. Such rounding errors are of course necessary because the floating-point format cannot exactly represent most logarithm values. The converse might happen too, where a result is too large.) – Eric Postpischil Jul 31 '20 at 11:30
  • Re “Your argument would seem to apply equally to the (int)(log2(x))”: No, `log2(x)` is not a general logarithm; it is a specific logarithm, so an argument about requiring a general logarithm does not apply. You are correct that floor(log2(x)•y) differs from log2(x)•y, but, as my example above shows, it is necessary to get the transition points correct (those where the discontinuous function floor jumps, i.e., the integers). We can do that for y=1 because there is no rounding error in multiplying by 1 and we have a `log2` that produces exact results where the logarithm is an integer… – Eric Postpischil Jul 31 '20 at 11:35
  • … But, when y is not 1, we do not have these advantages, and, again referring to my example, we essentially need to know the logarithm with high accuracy at certain points. So the problem might not be “implement a general logarithm,” but it is “implement a general logarithm for at least a set of certain critical points.” And I do not think that is much different in difficulty. – Eric Postpischil Jul 31 '20 at 11:37

0 Answers0