[Haskell-cafe] about integer and float operations

[Manlio Perillo]

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