11

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.

Jeppe Stig Nielsen
  • 60,409
  • 11
  • 110
  • 181
  • 32 or 64 bit architecture? – DWright Jan 18 '13 at 16:14
  • Does this answer your question? http://stackoverflow.com/questions/12003719/log-of-a-very-large-number Or perhaps related? – Pete Jan 18 '13 at 16:21
  • @Pete Good find, but I think thats why he's initializing an extra byte. Unless the byte array needs to be terminated with a character in some way that the 1 is becoming the sign character. – B L Jan 18 '13 at 16:24
  • @Jeppe Stig Nielsen Could you tell us what the output of log2 actually is, or is it different everytime? – B L Jan 18 '13 at 16:42
  • 1
    @glace: It seems to be reliably `-1313491238.4757` when I test it. – mellamokb Jan 18 '13 at 17:09
  • You can't make a number that big in the first place. If you try `BigInteger.Pow(i1, 2)`, which would be the same number, you get `OutOfMemoryException`. – mellamokb Jan 18 '13 at 17:28
  • @DWright It's 64-bit hardware. I tried changing the build configuration between `x86` and `x64` "platform" but it didn't seem to change anything. – Jeppe Stig Nielsen Jan 18 '13 at 20:59
  • @glace (to your second comment) I get the same number as mellamokb mentions, consistently. – Jeppe Stig Nielsen Jan 18 '13 at 21:04
  • @mellamokb (to your second comment) I don't know if you're referring to a deleted comment, but whether you get out-of-memory or not depends on how much memory (probably memory without "holes" in it) can be allocated. I _can_ calculate the square `Pow(i1, 2)`, and it is equal to `i2` (when I test with `==` operator). – Jeppe Stig Nielsen Jan 18 '13 at 21:15
  • @JeppeStigNielsen: My second comment was a general comment directed to you :). Ya I was wondering the same thing - I do have 6GB ram free, so that seems a little odd. Have you tried the suggestion I posted on Daniel's answer with `Array.CreateInstance`? That might allow you to get it working on your machine. – mellamokb Jan 18 '13 at 21:27

1 Answers1

11

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.

Daniel Fischer
  • 181,706
  • 17
  • 308
  • 431
  • 2
    Actually I think that's by design. You have to use [`Array.CreateInstance`](http://msdn.microsoft.com/en-us/library/1z8w3at5.aspx) to [allocate an array taking up more space than `int.MaxValue`](http://stackoverflow.com/a/10946548/116614). However, if you do use `Array.CreateInstance` with the long-index overload, you get an `OutOfMemoryException` due to the [per-object max size limit](http://stackoverflow.com/a/5791912/116614). So the array being created by the OP is in fact not even `300,000,001` elements in the first place. – mellamokb Jan 18 '13 at 17:15
  • But it's just the number of **bits** that exceeds that limit. The array takes only ~300MB, that shouldn't be a problem at all. – Daniel Fischer Jan 18 '13 at 18:25
  • Hmm. I bet there's something intermediate going on internally that is generating an object that's too large. I've got 6GB free RAM on my machine, so it seems like it should have worked. – mellamokb Jan 18 '13 at 19:49
  • This answer explains what's going on, I guess. I'm considering filing that bug report. The value is the one you quote (except it's formatted to a string without the `e9` notation in my example, but you got the right number). – Jeppe Stig Nielsen Jan 18 '13 at 21:38
  • 1
    @mellamokb The array _is_ 300 million and 1 elements (each element is a byte). So it's over 2 gigabits, but not over 2 gigabytes (there's this factor 8, which is why I wrote ¼ gigabyte). But if the array used internally (by `BigInteger`) is limited to 2 gigabytes, then that sets an effective limit on how big a `BigInteger` can become, and I'm over one eighth of that level (if it exists). – Jeppe Stig Nielsen Jan 18 '13 at 21:45