Yitzchak Gale ha scritto:
Manlio Perillo wrote:
However there is still a *big* problem: it is inefficient.
Here is a Python version of the Chudnovsky algorithm [1] for computing Pi: http://paste.pocoo.org/show/102800/ On my system it takes 10 seconds. Here is an Haskell version: http://paste.pocoo.org/show/102801/ On my system it takes 30 seconds.
Ah, OK. Thanks. Now we have a well-defined problem. :)
Good :).
And that makes it clear that what you want is Python 3 division.
Well, first of all, there are a few bugs in the Haskell version of your program - don't forget that unlike in Python, ranges in Haskell *include* the last number.
Ah right, thanks!
Second, we should note that it is silly to compute 1000 terms in this sum. By the end, you are getting terms whose order of magnitude is 10 ^ (-15000).
Yes, of course. But I wrote the Python script as a response to a post on it.comp.lang.python, where an user was having overflow problems with a naive implementation of the algorithm. I have tested it with 1000 iterations just to check the raw performances. Then I tried to code it in Haskell, noting that there was no direct method for an exact division of two integer numbers.
The Haskell version is spending a bit more time on those (useless) later terms. The reason is that in Haskell we are first reducing the fraction, then converting to Double. If you really did care about that amount of accuracy, you would leave the result as a Rational.
This is not possible, since there is an irrational number: c ** (3. / 2.). Moreover the sum of rational numbers is rather expensive, in this case.
[...]
In our case, the Python division first does a quick estimate of the sizes of the two integers, and just returns zero if it sees that there will be underflow on conversion to double. So I made the following rough change to the Haskell:
-- An exact division (/.) :: Integer -> Integer -> Double x /. y | y `div` x > 5*10^323 = 0 | otherwise = fromRational $ toRational x / toRational y
Right, but I would like to see a proper implemented function for exact integer division in GHC.
Now the Haskell runs in about half the time as the Python on my machine. Obviously, the Haskell could easily be further optimized.
-Yitz
Thanks Manlio