CODEWITHSUNDEEP
c#.netmathbigintegerlogarithm
Raheel Khan
Raheel Khan

Reputation: 14787

BigInteger Log Issue on large numbers

The code below takes a BigInteger n and finds a number less than n that is also a power of 2. It works fine with small numbers but the first branch of the if statement does not work for int.MaxValue and above. Apparently subtracting 1 (BigInteger.Log(n - 1)) is not enough for larger numbers.

How can I calculate a number to subtract that is large enough to make a difference and yet work on smaller numbers too?

public BigInteger FindNearestPowerOfTwo (BigInteger n)
{
    double number = 0;
    BigInteger big = 0;

    if (n.IsPowerOfTwo)
    {
        number = BigInteger.Log(n - 1) / BigInteger.Log(2);
    }
    else
    {
        number = BigInteger.Log(n) / BigInteger.Log(2);
    }

    number = Math.Floor(number);

    big = BigInteger.Pow(2, (int) number);

    return (big);
}

Upvotes: 3

Views: 657

Answers (3)

Juan Lopes
Juan Lopes

Reputation: 10575

Or the lazy man's version:

public static BigInteger FindNearestPowerOfTwo(BigInteger number) {
    bool isPower = number.IsPowerOfTwo;
    int count = 0;
    while(!number.IsZero) {
        Console.WriteLine(number);
        number = number >> 1;
        count ++ ;
    }
    return BigInteger.Pow(2, count - (isPower ? 2: 1));
}

Upvotes: 1

Keith Randall
Keith Randall

Reputation: 23265

You can use ToByteArray to get an explicit representation, then clear all bits but the highest one.

public BigInteger FindNearestPowerOfTwo (BigInteger n) {
    Byte[] a = n.ToByteArray();
    int len = a.Length;
    if (a[len - 1] == 0) len--; // leading zero to maintain sign
    for (int i = 0; i < len - 1; i++) a[i] = 0;
    int x = a[len - 1] & 255;
    int y = 1;
    while (x > 1) {
      x >>= 1;
      y <<= 1;
    }
    a[len - 1] = y;
    return new BigInteger(a);
}

Upvotes: 2

Daniel Fischer
Daniel Fischer

Reputation: 183968

In the if branch, you can subtract something from the quotient,

number = BigInteger.Log(n)/BigInteger.Log(2) - 0.9;

for example (I'd be careful with subtracting 1.0 there since BigInteger.Log(x) isn't exact, the quotient could be a little too small, then subtracting 1.0 would give you the wrong power of 2). That works also for pretty large numbers (but a double has only 53 bits of precision, so for numbers larger than 2^(2^54) that is guaranteed to fail - however, that's a lot more memory than currently available).

But easier would of course be

if (n.IsPowerOfTwo) {
    return n/2;
}

However, the else branch is problematic. If n is very close to a power of 2,

BigInteger.Log(n) / BigInteger.Log(2)

can be a little too large or too small, moving the quotient across the closest integer to the exact result. You should check that big is indeed smaller than n and if not, divide by 2.

It may be that BigInteger.Log(n, 2.0) produces more exact results than dividing two natural logarithms. (I don't know the implementation.)

Upvotes: 1

Related Questions