GHC: Ticket #1656: Bignum exponentiation yields wrong results
http://ghc.haskell.org/trac/ghc/ticket/1656
<p>
I've used the following GHC program:
</p>
<p>
main = print $ 9<sup>9</sup>9
</p>
<p>
The result was right in the number of digits (approx. 350 millions) but the last to digits are 94. By quick modular exponentiation, one finds out that 9<sup>9</sup>9 mod 100 = 89. So the number is obviously wrong. Looking further, at least the last 100 digits are wrong.
</p>
<p>
I have redone the calculation with demo/calc/calc.c included in the distribution of the GNU gmp library. This yields a different number, that could be correct ( 89, but I don't know if it is otherwise correct)
</p>
<p>
In both cases, the same libgmp3 shared object was used. But the GHC version constantly used 8 GiB of memory and four hours just for outputting the value in base 10, while the calculation of the value had been finished in about 5 minutes. demo/calc/calc.c used about 30 minutes for the whole job.
</p>
en-usGHChttp://ghc.haskell.org/trac/ghc/chrome/site/ghc_logo.png
http://ghc.haskell.org/trac/ghc/ticket/1656
Trac 1.2.2.dev0rvb@…Sun, 02 Sep 2007 18:27:07 GMT
http://ghc.haskell.org/trac/ghc/ticket/1656#comment:1
http://ghc.haskell.org/trac/ghc/ticket/1656#comment:1
<p>
Ok, ... that was meant to read
</p>
<pre class="wiki">main = print $ 9^9^9
</pre><p>
Hope that's better now.
</p>
Ticketrvb@…Sun, 02 Sep 2007 18:35:25 GMT
http://ghc.haskell.org/trac/ghc/ticket/1656#comment:2
http://ghc.haskell.org/trac/ghc/ticket/1656#comment:2
<p>
Ok, both the GHC calculated number and the C calculated one have exactly 369693101 digits. So the GHC computed number is probably not just truncated.
</p>
TicketiglooSun, 02 Sep 2007 19:30:54 GMTmilestone set
http://ghc.haskell.org/trac/ghc/ticket/1656#comment:3
http://ghc.haskell.org/trac/ghc/ticket/1656#comment:3
<ul>
<li><strong>milestone</strong>
set to <em>6.8</em>
</li>
</ul>
<p>
Thanks for the report. This reminds me of <a class="closed ticket" href="http://ghc.haskell.org/trac/ghc/ticket/867" title="#867: bug: Integer arithmetic gives the wrong answer on amd64/Linux (closed: fixed)">#867</a>, but that is fixed in 6.6.
</p>
<p>
Unfortunately I don't have 8G of RAM, so reproducing this is non-trivial. I tried with some smaller examples, but couldn't reproduce it. If anyone has a smaller example then please let us know, but of course it's possible that it is only when >2G of RAM is being used that problems happen.
</p>
<p>
Thanks
</p>
<p>
Ian
</p>
Ticketrvb@…Sun, 02 Sep 2007 20:06:44 GMT
http://ghc.haskell.org/trac/ghc/ticket/1656#comment:4
http://ghc.haskell.org/trac/ghc/ticket/1656#comment:4
<p>
I neither have 8G of RAM. (that's why it took so long, constantiously swapping)
</p>
<pre class="wiki"> dd if=/dev/zero of=swap count=20000000 # 10G
mkswap swap
sapon swap
</pre><p>
Unfortunately, it takes some hours this way. I am just redoing the computation during the night to see if the error is reproducible. But maybe you can come up with an example which is only a few bigger than 2GiB.
</p>
Ticketrvb@…Mon, 03 Sep 2007 07:16:12 GMT
http://ghc.haskell.org/trac/ghc/ticket/1656#comment:5
http://ghc.haskell.org/trac/ghc/ticket/1656#comment:5
<p>
This time, I got the same result as with C+gmp, but used a different program:
</p>
<pre class="wiki">power acc _ 0 = acc
power acc x n | odd n = power (x * acc) (x * x) ((n - 1) `div` 2)
| even n = power acc (x * x) (n `div` 2)
main = let (^^^) = power 1 in do
writeFile "myresult" . show $ 9 ^^^ (9 ^^^ 9)
</pre><p>
Note: this time I used writeFile directly instead of print and redirecting the output, and I am using an exponentiation algorithm different from the one in the base library. Although I don't see why that would lead to different results. (I haven't looked at the base one very much)
</p>
<p>
I'll try once again with writeFile and the builtin <sup>, to see whether print and redirection messed with my number.
</sup></p>
Ticketrvb@…Tue, 04 Sep 2007 11:08:43 GMT
http://ghc.haskell.org/trac/ghc/ticket/1656#comment:6
http://ghc.haskell.org/trac/ghc/ticket/1656#comment:6
<p>
I again failed to reproduce it. This time using my power function and print with shell redirection. For the next night, I'll just retry the original example to see if the bug is reproducible at all.
</p>
Ticketrvb@…Wed, 05 Sep 2007 06:51:09 GMT
http://ghc.haskell.org/trac/ghc/ticket/1656#comment:7
http://ghc.haskell.org/trac/ghc/ticket/1656#comment:7
<p>
Ok, it is not reprodicble, not even using the original program. This of course means, that nobody knows that has even caused the wrong calculation... whether it was GHC, libgmp, a bug in the kernel or the hardware, that might have been triggered by the heavy load or what else.
</p>
<p>
Feel free to close the bug, then.
</p>
TicketiglooWed, 05 Sep 2007 14:47:14 GMTstatus changed; resolution set
http://ghc.haskell.org/trac/ghc/ticket/1656#comment:8
http://ghc.haskell.org/trac/ghc/ticket/1656#comment:8
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>worksforme</em>
</li>
</ul>
<p>
OK, thanks for looking into it.
</p>
TicketiglooMon, 05 Nov 2007 15:03:59 GMTmilestone changed
http://ghc.haskell.org/trac/ghc/ticket/1656#comment:9
http://ghc.haskell.org/trac/ghc/ticket/1656#comment:9
<ul>
<li><strong>milestone</strong>
changed from <em>6.8 branch</em> to <em>6.8.1</em>
</li>
</ul>
Ticket