[Haskell-cafe] about integer and float operations
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.
> 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
More information about the Haskell-Cafe
mailing list