记录非常大的数字

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等返回-Infinity.数字似乎围绕字节边界.知道这里发生了什么吗？

例:

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 Solver Foundation(可从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()函数