[Agda] Data.Rational

Sergei Meshveliani mechvel at botik.ru
Wed Mar 12 14:04:57 CET 2014


On Wed, 2014-03-12 at 16:37 +0400, Sergei Meshveliani wrote:
> On Tue, 2014-03-11 at 20:58 +0100, Andreas Abel wrote:
> 
> > I have no personal experience, but I listened to a talk by Anders 
> > M"ortberg who presented his joint work with Cyril Cohen. He said that
> > if you want to be efficient you should *not* try to cancel the common 
> > primfactors in fractions each time.  The cost of making things 
> > coprime repeatedly seems to be higher than computing with larger 
> > integers. 
>  
> My experience is very different.
> 
> [..]


If one computes   m/n + m'/n'   for large random integers  m,n,m',n',
than it is better to delay cancelling by  gcd.
Because the average gcd for two large random integers occurs small.

Due to this consideration, I had once (in about 1990) an illusion of
that the (Delay) approach is good.   

But in most practical computation methods, the current  m  and  n  are
not random, they are somehow accumulated from some root in a long loop.

This is why (C) occurs more practicable than (Delay).
I cannot prove this, I only provide practical examples and
considerations in my previous letter. 

Just follow  D.Knuth:  in   m/n + m'/n'

the first step is to find  gcd n n' ...

Regards,

------
Sergei


> 1. GHC Rational
> ---------------
> As I recall, I tried this in earlier GHC versions (in 1990-ies)
> 
>    sumF n =  1 + 1/2 + 1/3 + ... + 1/n,   with taking large  n
> 
> [..]




More information about the Agda mailing list