[Haskell-cafe] about integer and float operations

[Yitzchak Gale]

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