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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
