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. :) 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. 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). 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. Or as one of various other unlimited-precision floating point types that are available in Haskell libraries. This calculation in Haskell would take the same amount of time as it takes now. You would need to rewrite your Python program to do this, and I would guess it would run a lot slower. 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 Now the Haskell runs in about half the time as the Python on my machine. Obviously, the Haskell could easily be further optimized. -Yitz