的数量非常大的日志 [英] Log of a very large number
问题描述
我处理BigInteger类与数字在2幂10,000,000顺序。
该BigInteger的日志功能，现在在我的算法中最昂贵的功能，我拼命寻找一种替代。
由于我只需要对数的组成部分，我跨来到这个答案它在速度方面似乎辉煌但由于某些原因，我没有得到准确的数值。我不关心的小数部分，但我确实需要得到准确的组成部分，该值是地板还是只要是我知道的ceiled其中。
下面是我实现的功能：
公共静态双LogBase2（System.Numerics.BigInteger号）
{
返回（LogBase2（number.ToByteArray（）））;
}
公共静态双LogBase2（byte []的字节）
{
//基于[ronalchn]的答案更正。
返回（System.Math.Log（字节[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！=负无穷大
LogBase2（2162420578）= 31.009999999993600！=负无穷大
LogBase2（4235837212）= 31.979999999984800！=负无穷大
LogBase2（4265299789）= 31.989999999727700！=负无穷大
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！=负无穷大
LogBase2（557430119061）= 39.019999999998900！=负无穷大
LogBase2（561307352157）= 39.029999999998300！=负无穷大
LogBase2（565211553542）= 39.039999999997900！=负无穷大
LogBase2（569142910795）= 39.049999999997200！=负无穷大
LogBase2（1084374326282）= 39.979999999998100！=负无穷大
LogBase2（1091916746189）= 39.989999999998500！=负无穷大
LogBase2（1099511627775）= 39.999999999998700！=负无穷大
试试这个：
公共静态INT LogBase2（byte []的字节）
{
如果（字节[bytes.Length - 1]≥= 128）返回-1; // -ve BIGINT（无效 - 不能把日志-ve数）
INT数= 0;
而（（字节[bytes.Length - 1]≥＆GT;日志）大于0）日志++;
返回日志+ bytes.Length * 8-9;
}
的原因最显著字节为0是因为BigInteger的是一个带符号的整数。当高位字节的最显著位是1，一个额外的字节被附加了重新present 0的符号位为正整数。
另外，从使用System.Math.Log功能，因为如果你只想要圆的价值，它的速度要快得多使用位操作改变。
如果您有Microsoft求解基金会（下载网址为： http://msdn.microsoft .COM / EN-US / devlabs / hh145003.aspx ），那么你可以使用的比特计数（）函数：
公共静态双LogBase2（Microsoft.SolverFoundation.Common.BigInteger号）
{
返回number.BitCount;
}
或者你也可以使用Java库。添加引用vjslib库。（在.NET标签中 - 这是J＃实现的Java库）
您现在可以在你的code加上使用的java.math。
java.math.BigInteger中有位长度（）函数
I'm dealing with the BigInteger class with numbers in the order of 2 raised to the power 10,000,000.
The BigInteger Log function is now the most expensive function in my algorithm and I am desperately looking for an alternative.
Since I only need the integral part of the log, I came across this answer which seems brilliant in terms of speed but for some reason I am not getting accurate values. I do not care about the decimal part but I do need to get an accurate integral part whether the value is floored or ceiled as long as I know which.
Here is the function I implemented:
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));
}
The values are now incredibly accurate except for corner cases. The values 7 to 7.99999, 15 to 15.9999, 23 to 23.9999 31 to 31.9999, etc. return -Infinity. The numbers seem to revolve around byte boundaries. Any idea what's going on here?
Example:
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
Try this:
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;
}
The reason for the most significant byte being 0 is because the BigInteger is a signed integer. When the most significant bit of the high-order byte is 1, an extra byte is tacked on to represent the sign bit of 0 for positive integers.
Also changed from using the System.Math.Log function because if you only want the rounded value, it is much faster to use bit operations.
If you have Microsoft Solver Foundation (download at http://msdn.microsoft.com/en-us/devlabs/hh145003.aspx), then you can use the BitCount() function:
public static double LogBase2(Microsoft.SolverFoundation.Common.BigInteger number)
{
return number.BitCount;
}
Or you can use the java library. Add a reference to the vjslib library (found in the .NET tab - this is the J# implementation of the java library).
You can now add "using java.math" in your code.
java.math.BigInteger has a bitLength() function
这篇关于的数量非常大的日志的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
