10

I need a Very-Fast implementation of log2(float x) function in C++.

I found a very interesting implementation (and extremely fast!)

#include <intrin.h>

inline unsigned long log2(int x)
{
    unsigned long y;
    _BitScanReverse(&y, x);
    return y;
}

But this function is good only for integer values in input.

Question: Is there any way to convert this function to double type input variable?

UPD:

I found this implementation:

typedef unsigned long uint32;
typedef long int32;   
static inline int32 ilog2(float x)
{
    uint32 ix = (uint32&)x;
    uint32 exp = (ix >> 23) & 0xFF;
    int32 log2 = int32(exp) - 127;

    return log2;
}

which is much faster than the previous example, but the output is unsigned type.

Is it possible to make this function return a double type?

Thanks in advance!

Improve this question
7
  • 2
    This is a very strange requirement, because Logarithm with base 2 is rarely used for anything except calculating number of bits for something and you work with integers when you count bits. So what do you need it for? Commented Feb 23, 2012 at 11:18
  • 4
    @JanHudec: Off the top of my head, two common uses of a logarithm would be calculating the entropy of a signal, and doing arithmetic on very large numbers that would otherwise overflow. Commented Feb 23, 2012 at 11:32
  • 1
    @MikeSeymour: For signal, it is rare to be floating point rather than integer. For arithmetic on large numbers, you wouldn't need base 2 and probably use natural logarithm as the math is usually expressed with that. Commented Feb 23, 2012 at 12:12
  • @JanHudec: Well, I'd use floating point to represent properties of a signal if that were more convenient than integer; and I might choose 2 as an arbitrary base, since that might be faster to calculate than a natural logarithm; but that's just me. There's little point arguing about it, or about whether the OP should be interested in fast logarithms. Commented Feb 23, 2012 at 12:31
  • 1
    @Lightness Races in Orbit: I need to simulate a solution to differential evolution equation and it involves a lot of heavy and nested computations. The bottle neck of my calculation are time-consuming math functions like exp, log, atan. Thus, it is better for me to optimize them. Commented Feb 23, 2012 at 15:01

8 Answers 8

Reset to default
11

If you just need the integer part of the logarithm, then you can extract that directly from the floating point number.

Portably:

#include <cmath>

int log2_fast(double d) {
    int result;
    std::frexp(d, &result);
    return result-1;
}

Possibly faster, but relying on unspecified and undefined behaviour:

int log2_evil(double d) {
    return ((reinterpret_cast<unsigned long long&>(d) >> 52) & 0x7ff) - 1023;
}
Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

You mean it relies on an IEEE implementation of float or double? Of course the library implementors may have also thought of that one?
@CashCow: Indeed, and it also relies on reinterpret_cast working as hoped - that's undefined behaviour. frexp certainly would take advantage of the IEEE representation; but unless the library provides it inline, that would also incur the cost of a function call, and extracting the significand. The evil version doesn't do those things.
Thank you guys! I work in the field of High-Performance Scientific Computing and thus need all basic math function to be optimized. Frankly speaking, I have 4 nested loops and the the bottle neck is some complicated math expression involving log(), exp(), atan(), sqrt(), e.t.c. I need natural logarithm function log(), but since log2() is more "popular", I can convert log2() to log() just by multiplying by log(2) (which is constant). So, my question is: how to implement the fastest possible log()/log2() function which takes double type as argument and returns also double type.
You need compiler specific commands to turn off strict alias optimizations or evil casting code is nearly guaranteed to fail.
@Pomeron You need to 1. extract the base 2 exponent like this answer does, 2. compute log2(1.mantissa) by approximating it with some rational function (i.e. the approximation must be valid for the interval [1, 2)), and 3. add the two values together. If you need precision, most time will be spent on step 2, and AFAIK, that's what the standard implementations of log2() do anyway. However, if you are willing to trade some precision for speed, you can just use a faster approximation of log2() on the interval [1, 2).
|
8

MSVC + GCC compatible version that give XX.XXXXXXX +-0.0054545

float mFast_Log2(float val) {
    union { float val; int32_t x; } u = { val };
    register float log_2 = (float)(((u.x >> 23) & 255) - 128);              
    u.x   &= ~(255 << 23);
    u.x   += 127 << 23;
    log_2 += ((-0.3358287811f) * u.val + 2.0f) * u.val  -0.65871759316667f; 
    return (log_2);
}
Improve this answer

3 Comments

Slightly more accurate formula (maximum error ±0.00493976), optimized using Remez' algorithm: ((-0.34484843f) * u.val + 2.02466578f) * u.val - 0.67487759f
@netvope seriously thank you for this comment, made me open my eyes, and learn approximation theory!
This is undefined behavior , you must use either std::bit_cast or std::memcpy if before C++20 and cross your fingers that it compiles as zero cost. You cannot assign a value to a union, and read it out as a different value in C++
7

Edit: See link by Job in the comments below for a better version.

Fast log() function (5× faster approximately)

Maybe of interest for you. The code works here; It is not infinitely precise though. As the code is broken on the web page (the > have been removed) I'll post it here:

inline float fast_log2 (float val)
{
   int * const    exp_ptr = reinterpret_cast <int *> (&val);
   int            x = *exp_ptr;
   const int      log_2 = ((x >> 23) & 255) - 128;
   x &= ~(255 << 23);
   x += 127 << 23;
   *exp_ptr = x;

   val = ((-1.0f/3) * val + 2) * val - 2.0f/3;   // (1)

   return (val + log_2);
} 

inline float fast_log (const float &val)
{
   return (fast_log2 (val) * 0.69314718f);
}
Improve this answer

3 Comments

It seems that this doesn't work. Compiled with gcc-4.4.7, fast_log2(1024.f) returns -347469.
github.com/romeric/fastapprox has a much faster function at the same precision, or an almost-as-fast function with much higher precision
Specifically in this header: github.com/romeric/fastapprox/blob/master/fastapprox/src/…
5

C++11 added std::log2 into <cmath>.

Improve this answer

1 Comment

Since when is anything in the standard library fast...
3

You can take a look into this implementation, but :

  • it may not work on some platforms
  • might not beat std::log
Improve this answer

Comments

2

This is an improvement on the first answer which does not rely on IEEE implementation, although I imagine that it is only fast on IEEE machines where frexp() is basically a costless function.

Instead of discarding the fraction that frexp returns, one can use it to linearly interpolate. The fraction value is between 0.5 and 1.0 if it is positive, so we stretch between 0.0 and 1.0 and add it to the exponent.

In practice, it looks like this fast evaluation is good to about 5-10%, always returning a value that is a little low. I'm sure it could be made better by tweaking the 2* scaling factor.

#include <cmath>

double log2_fast(double d) {
    int exponent;
    double fraction = std::frexp(d, &exponent);
    return (result-1) + 2* (fraction - 0.5);
}

You can verify that this is reasonable fast approximation with this:

#include <cmath>

int main()
{
   for(double x=0.001;x<1000;x+=0.1)
   {
      std::cout << x << " " << std::log2(x) << " " << log2_fast(x) << "\n";
   }
}
Improve this answer

Comments

-1

No, but if you only need the integeral part of the result and don't insist on portability, there is even faster one. Because all you need is to extract the exponent part of the float!

Improve this answer

Comments

-2

This function is not C++, it's MSVC++ specific. Also, I highly doubt that any such intrinsics exist. And if they did, the Standard function would simply be configured to use it. So just call the Standard-provided library.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.