Wrong logarithm of BigInteger when size of BigInteger exceeds ¼ gigabyte
.net, base-class-library, biginteger, c#, logarithm
Solution
Let me guess: The value is
-1.3134912384757032e9
(modulo small variations in computing the logarithm)?
The index of the highest set bit is stored and passed in an `int`, and
8*300000000 = 2400000000 > 2147483647
so the index wraps around to a negative number, namely `-1894967296`, and
-1894967296 * log 2 = -1.3134912384757032e9
Oops. Somebody should file a bug report.
Problem
When I have a `BigInteger` whose size exceeds 2 gigabits (that's ¼ gigabyte; I found this threshold by trial and error), the logarithm method gives a wrong answer. This simple code illustrates: ``` byte[] bb; bb = new byte[150000001]; bb[150000000] = 1; // sets most significant byte to one var i1 = new BigInteger(bb); double log1 = BigInteger.Log(i1); Console.WriteLine(log1); // OK, writes 831776616.671934 bb = new byte[300000001]; bb[300000000] = 1; // sets most significant byte to one var i2 = new BigInteger(bb); double log2 = BigInteger.Log(i2); Console.WriteLine(log2); // Broken, gives negative number, should be twice 831776616.671934 ``` Of course we must have a positive log for a number exceeding `1`, a zero log for the number `1`, and a negative log for a number between `0` and `1` (no integers there). My numbers `i1` and `i2` above are greater than `1` since, by convention, when the most significant byte is between `0` and `127`, that means positive `BigInteger`. Now, if you read the documentation for `BigInteger.Log`, they claim it might throw if the logarithm "is out of range of the Double data type". Now, clearly that would require a computer with a memory storage of more than `1E+300` bytes, and the observable universe is much too small to contain such a computer, so I guess that will never happen. So why doesn't this work? PS! Size over `2 ^^ 31` bits means that the actual value of the `BigInteger` is over `2 ^^ (2 ^^ 31)`, or approximately `circa 8.8E+646456992`. UPDATE: I sent in a bug report to Microsoft Connect. After having read the discussions I have also become aware that because of the design of `BigInteger` and the upper limit of 2 gigabyte for the size of one single object, a `BigInteger` can never be over 2 gigabyte (no matter how much memory you have). This bug happens, therefore, when the `BigInteher` is between ¼ and 2 gigabytes.