4

How can I compute a base 2 logarithm without using the built-in math functions in C#?

I use Math.Log and BigInteger.Log repeatedly in an application millions of times and it becomes painfully slow.

I am interested in alternatives that use binary manipulation to achieve the same. Please bear in mind that I can make do with Log approximations in case that helps speed up execution times.

Najia Khan
  • 51
  • 1
  • 4
  • Given an integer, you could zero all bits but the most-significant one and you've got yourself a power of two, which has a trivial 2-logarithm. That's a very rough approximation. – jforberg Aug 18 '12 at 23:29
  • Interesting, I wonder what the fastest way to find the most significant set bit. – Najia Khan Aug 18 '12 at 23:30
  • Levesque has a good solution. – jforberg Aug 18 '12 at 23:33
  • possible duplicate of [Log of a very large number](http://stackoverflow.com/questions/12003719/log-of-a-very-large-number) – L.B Aug 19 '12 at 06:39

6 Answers6

4

Assuming you're only interested in the integral part of the logarithm, you can do something like that:

static int LogBase2(uint value)
{
    int log = 31;
    while (log >= 0)
    {
        uint mask = (1 << log);
        if ((mask & value) != 0)
            return (uint)log;
        log--;
    }
    return -1;
}

(note that the return value for 0 is wrong; it should be negative infinity, but there is no such value for integral datatypes so I return -1 instead)

Thomas Levesque
  • 286,951
  • 70
  • 623
  • 758
2

http://graphics.stanford.edu/~seander/bithacks.html

Sebi
  • 4,262
  • 13
  • 60
  • 116
  • While this may theoretically answer the question, [it would be preferable](http://meta.stackexchange.com/q/8259) to include the essential parts of the answer here, and provide the link for reference. – Bill the Lizard Aug 19 '12 at 02:41
1

For the BigInteger you could use the toByteArray() method and then manually find the most significant 1 and count the number of zeroes afterward. This would give you the base-2 logarithm with integer precision.

mimicocotopus
  • 5,280
  • 4
  • 22
  • 24
  • Perfect. That reduces CPU cycles to practically 1 instead of byte[].Length. The BigInteger makes this easy. I wonder what the approach would be for native types like Int32, Int64, double, etc. – Najia Khan Aug 18 '12 at 23:31
  • Well, technically you could do the same sort thing with any integer type. As for a double, it's really easy, provided it's a IEEE binary double just use a bitwise and operation to select the exponent bits and shift these over -- there's the base two logarithm. Actually, for IEEE decimal it's easy too. Just do the same thing and then divide by log2(10) = ~3.2. – mimicocotopus Aug 18 '12 at 23:35
1

The bit hacks page is useful for things like this.

The code there is in C, but the basic idea will work in C# too.

Community
  • 1
  • 1
Mark Byers
  • 811,555
  • 193
  • 1,581
  • 1,452
0

If you can make due with approximations then use a trick that Intel chips use: precalculate the values into an array of suitable size and then reference that array. You can make the array start and end with any min/max values, and you can create as many in-between values as you need to achieve the desired accuracy.

Kent
  • 1,691
  • 4
  • 19
  • 27
0

You can try this C algorithm to get the binary logarithm (base 2) of a double N :

static double native_log_computation(const double n) {
    // Basic logarithm computation.
    static const double euler = 2.7182818284590452354 ;
    unsigned a = 0, d;
    double b, c, e, f;
    if (n > 0) {
        for (c = n < 1 ? 1 / n : n; (c /= euler) > 1; ++a);
        c = 1 / (c * euler - 1), c = c + c + 1, f = c * c, b = 0;
        for (d = 1, c /= 2; e = b, b += 1 / (d * c), b - e /* > 0.0000001 */ ;)
            d += 2, c *= f;
    } else b = (n == 0) / 0.;
    return n < 1 ? -(a + b) : a + b;
}

static inline double native_ln(const double n) {
    //  Returns the natural logarithm (base e) of N.
    return native_log_computation(n) ;
}

static inline double native_log_base(const double n, const double base) {
    // Returns the logarithm (base b) of N.
    // Right hand side can be precomputed to 2.
    return native_log_computation(n) / native_log_computation(base) ;
}

Source

Michel
  • 259
  • 2
  • 3