我正在处理 BigInteger 类,它包含 2 的 10,000,000 次方的数字。
BigInteger Log 函数现在是我算法中最昂贵的函数,我正在拼命寻找替代函数。
由于我只需要日志的组成部分,所以遇到了this answer这在速度方面看起来很棒,但出于某种原因我没有得到准确的值。我不关心小数部分,但我确实需要获得准确的整数部分,无论该值是下限还是上限,只要我知道是哪个即可。
这是我实现的功能:
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
最佳答案
试试这个:
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# 实现)。
您现在可以在代码中添加“使用 java.math”。
java.math.BigInteger 有一个 bitLength() 函数
关于c# - 大量日志,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12003719/