我正在处理BigInteger类,其中的数字在2的顺序中被提升到10,000,000的幂。
BigInteger 对数函数现在是我的算法中最昂贵的函数,我正在急切地寻找一个替代方案。
由于我只需要对数的积分部分,我发现了 本回答 这在速度方面似乎很出色,但由于某些原因,我没有得到准确的数值。我不关心小数部分,但我需要得到一个准确的积分部分,不管是浮动的还是上升的,只要我知道是哪个。
这是我实现的函数。
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.comen-usdevlabshh145003.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()函数。
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;
}
}