[Agda] Data.Rational

[Sergei Meshveliani]

On Wed, 2014-03-12 at 17:04 +0400, Sergei Meshveliani wrote:
> 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.


Here is a reasonable intuitive explanation for the effect.

If  r = m/n + m'/n'  is a _final result_ for randomly chosen integers,
then it may have sense to use the (Delay) approach for the gcd 
cancellation.

This consideration is the source of a certain illusion about the (Delay)
approach.

This illusion is broken. Because usually there are done a lot of further
computations based on  r.  
And if  r  has only a small extra size bit in its expression, this extra
size is grown by applying further operations. 
This is shown in my two examples in my previous letters.


Regards,

------
Sergei