Manlio Perillo manlio_perillo at libero.it
Wed Feb 4 19:10:13 EST 2009

```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.
>
> -- 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
```