[Agda] Data.Rational

[Sergei Meshveliani]

On Wed, 2014-03-12 at 09:48 -0400, Jacques Carette wrote:
> On 2014-03-12 9:04 AM, 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.
> > 
> > This is why (C) occurs more practicable than (Delay).
> > I cannot prove this, I only provide practical examples and
> > considerations in my previous letter. 
> 
> Things have changed since.  The numbers one could deal with in 1990
> computers were still kind of not-too-big (10,000 to 100,000 digits,
> but more than that, things just did not work anymore). 

It is for the arbitrary-length integers. Any computer can operate in a
space of arbitrary size. 

>  If you go even bigger, things change.

(Delay) is worse than (C) on 10,000 digits, and it will be even more
relatively worse on 100,000,000 digits.


> The other thing to remember is that "industrial grade" gcd algorithms
> are really multi-algorithms: the case where the gcd is small is highly
> optimized, and is thus very cheap to compute.  Similarly, if the gcd
> is quite large, that is fast too.  It is only when the gcd is
> 'mid-sized' that the computation is expensive!
> 
> In particular, for things like Gaussian Elimination for exact matrices
> (integers, rationals, polynomials, etc), it can start to really pay to
> Delay, IF you have a fast zero-testing strategy.  See for example
> Wenqin Zhou, J. Carette, D.J. Jeffrey and M.B. Monagan Hierarchical
> representations with signatures for large expression management,
> Proceedings of Artificial Intelligence and Symbolic Computation
> (2006).
> []

1) So far, we compare only the two tactics:
 
(C)     cancel to coprimes immediately in all cases,
(Delay) delay cancellation to the end in all cases.


2) What is your statement concerning the example of

   sumF n =  1 + 1/2 + 1/3 + ... + 1/n  
?


3) There are known powerful and popular CA libraries with highly
optimized algorithms (which of course operate with fractions too),

* Lenstra's library for algebraic numbers (I do not recall the name),
* Axiom  (see for example, FriCAS),
* Maple,
* Mathematica,
and such.

Which of them apply the (Delay) approach?

As I recall,  Axiom of FriCAS  (which I respect highly) uses "always C".

It is not difficult to know about these programs. Just write to the
e-mail list of the corresponding library.
But the answer needs to be not just by _some article_ author.
Because publishing a paper does not imply that somebody will read this
paper, nor that many mathematicians will apply this computation method
on practice.
The answer needs to be by the mathematician who's algorithm for
fractions work in reality in this library. 
This can be known as follows. 
Look into the documentation for Fraction arithmetic in this chosen
program library. There will be a reference to the method author, and
most probably, a reference to the paper, after which the algorithm is
built.

Personally, I am lazy to look into this by new.
I may mistake. 
But I keep on thinking all these years: surely "always Delay" is not
practicable at all.

Regards,

------
Sergei