0

I found a fast binary logarithm algorithm for fixed points in an answer to this question: Fast fixed point pow, log, exp and sqrt, based on an algorithm by Clay S. Turner. Is it possible to "reverse" this to calculate fractional powers of two? e.g: 

// log2(3) = 1.5849609375
log2fix(196608, 16) == 103872
pow2fix(103872, 16) == 196608

Here's the code from Dan Moulding:

#include <errno.h>
#include <stddef.h>

#include "log2fix.h"

int32_t log2fix (uint32_t x, size_t precision)
{
    int32_t b = 1U << (precision - 1);
    int32_t y = 0;

    if (precision < 1 || precision > 31) {
        errno = EINVAL;
        return INT32_MAX; // indicates an error
    }

    if (x == 0) {
        return INT32_MIN; // represents negative infinity
    }

    while (x < 1U << precision) {
        x <<= 1;
        y -= 1U << precision;
    }

    while (x >= 2U << precision) {
        x >>= 1;
        y += 1U << precision;
    }

    uint64_t z = x;

    for (size_t i = 0; i < precision; i++) {
        z = z * z >> precision;
        if (z >= 2U << (uint64_t)precision) {
            z >>= 1;
            y += b;
        }
        b >>= 1;
    }

    return y;
}
Sophia Gold
  • 756
  • 1
  • 8
  • 18
  • 2
    `z >= 2U << (uint64_t)precision` makes little sense. Suggest `z >= 2ULL << precision`. – chux - Reinstate Monica Apr 28 '20 at 03:39
  • Ok, I think the problem is that your exponent isn't an integer. I hadn't understood that. The algorithm I gave can raise any type of number to an integer power, but not a fractional power. In your case, you want `pow2fix(103872)`, which is `2^(103872 * 2^(-16))`, which is close to `3`. But the exponent is scaled by `2^(-16)` so it's not an integer. You could regroup it as `(2^(2^(-16)))^103872`, or as `(2^103872)^(2^(-16))`, but I don't think either will help. In both cases, you'd end up having to deal with an exponent of `2^(-16)`, which is fractional. – Tom Karzes Apr 28 '20 at 05:28
  • Yeah, sorry should have explained that better. A lot of people use Chebyshev polynomials or similar, but I happened upon the above algorithm for the log and was hoping for something more like that in reverse. But I'm not sure that makes sense; you can see it relies on squaring the argument and then setting bits in the mantissa based on the result. – Sophia Gold Apr 28 '20 at 05:41
  • The exponent could also be negative, so that's something else a solution would have to address. – Tom Karzes Apr 28 '20 at 06:01
  • I do have some ideas for how this might be done, but the problem with them is they'd depend on a fixed precision, i.e. 16. Although if the number of required precision values is low, it could probably be done with a couple lookup tables based on the precision. – Tom Karzes Apr 28 '20 at 06:04
  • There is an example here: https://stackoverflow.com/questions/36550388/power-of-2-approximation-in-fixed-point – Sophia Gold Apr 28 '20 at 06:49

0 Answers0