非常大的日志

Question

我正在处理 BigInteger 类，其中数字从 2 增加到 10,000,000 的幂。

BigInteger Log 函数现在是我的算法中最昂贵的函数，我正在拼命寻找替代方案。

由于我只需要日志的组成部分，因此我遇到了这个答案，它在速度方面似乎很棒，但由于某种原因，我没有得到准确的值。我不在乎小数部分，但只要我知道哪个，我确实需要得到一个准确的整数部分，无论该值是地板还是塞进。

这是我实现的功能：

public static double LogBase2 (System.Numerics.BigInteger number)
{
    return (LogBase2(number.ToByteArray()));
}
public static double LogBase2 (byte [] bytes)
{
    // Corrected based on [ronalchn's] answer.
    return (System.Math.Log(bytes [bytes.Length - 1], 2) + ((bytes.Length - 1) * 8));
}

这些值现在非常准确，但极端情况除外。值 7 到 7.99999、15 到 15.9999、23 到 23.9999 31 到 31.9999 等返回 -无穷大。这些数字似乎围绕着字节边界。知道这里发生了什么吗？

例：

LogBase2(                    1081210289) = 30.009999999993600 != 30.000000000000000
LogBase2(                    1088730701) = 30.019999999613300 != 30.000000000000000
LogBase2(                    2132649894) = 30.989999999389400 != 30.988684686772200
LogBase2(                    2147483648) = 31.000000000000000 != -Infinity
LogBase2(                    2162420578) = 31.009999999993600 != -Infinity
LogBase2(                    4235837212) = 31.979999999984800 != -Infinity
LogBase2(                    4265299789) = 31.989999999727700 != -Infinity
LogBase2(                    4294967296) = 32.000000000000000 != 32.000000000000000
LogBase2(                    4324841156) = 32.009999999993600 != 32.000000000000000
LogBase2(                  545958373094) = 38.989999999997200 != 38.988684686772200
LogBase2(                  549755813887) = 38.999999999997400 != 38.988684686772200
LogBase2(                  553579667970) = 39.009999999998800 != -Infinity
LogBase2(                  557430119061) = 39.019999999998900 != -Infinity
LogBase2(                  561307352157) = 39.029999999998300 != -Infinity
LogBase2(                  565211553542) = 39.039999999997900 != -Infinity
LogBase2(                  569142910795) = 39.049999999997200 != -Infinity
LogBase2(                 1084374326282) = 39.979999999998100 != -Infinity
LogBase2(                 1091916746189) = 39.989999999998500 != -Infinity
LogBase2(                 1099511627775) = 39.999999999998700 != -Infinity

Answer 1

试试这个：

public static int LogBase2(byte[] bytes)
{
    if (bytes[bytes.Length - 1] >= 128) return -1; // -ve bigint (invalid - cannot take log of -ve number)
    int log = 0;
    while ((bytes[bytes.Length - 1]>>log)>0) log++;
    return log + bytes.Length*8-9;
}

最高有效字节为 0 的原因是 BigInteger 是有符号整数。当高位字节的最高有效位为 1 时，将附加一个额外的字节来表示正整数的符号位 0。

也从使用 System.Math.Log 函数更改，因为如果您只需要舍入值，则使用位运算要快得多。

---

如果您有Microsoft规划求解基础（http://msdn.microsoft.com/en-us/devlabs/hh145003.aspx 下载），则可以使用 BitCount（） 函数：

public static double LogBase2(Microsoft.SolverFoundation.Common.BigInteger number)
{
    return number.BitCount;
}

---

或者您可以使用 java 库。添加对 vjslib 库的引用（可在 .NET 选项卡中找到 - 这是 java 库的 J# 实现）。

您现在可以在代码中添加"using java.math"。

java.math.BigInteger 有一个 bitLength（） 函数

Answer 2

BigInteger bi = new BigInteger(128);   
int log =  bi.Log2();
public static class BigIntegerExtensions
{
    static int[] PreCalc = new int[] { 8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
    public static int Log2(this BigInteger bi)
    {
        byte[] buf = bi.ToByteArray();
        int len = buf.Length;
        return len * 8 - PreCalc[buf[len - 1]] - 1;
    }
}

Answer 3

晚了几年，但也许这会帮助其他人......

.Net Core 3 添加了基本上是 log2 的.GetBitLength()。（但只有一个增量太高了）由于它是内置在 .net 中的，我认为这和我们所能得到的一样快。

// Create some example number
BigInteger myNum= (BigInteger)32;
// Get the Log2
BigInteger myLog2 = myNum.GetBitLength() - 1;

https://dotnetfiddle.net/7ggy4D