mini-gmp and mpq

[Bradley Lucier]

On 02/26/2018 05:09 AM, Torbjörn Granlund wrote:
> Bradley Lucier <lucier at math.purdue.edu> writes:
> 
>    Even in aors.c it seems that what complexity is there would be worth
>    the trouble even in a mini-gmp.
> 
> Let's not forget that the "mini" in mini-gmp refers to code complexity
> and size, not runtime.  :-)
> 

I understand, and others will decide how much complexity is worth it.

Just two remarks from my experience with the numerical runtime from 
Gambit Scheme:

1.  The amount of code needed for good rational arithmetic routines was 
much less than was needed even for the naive routines for integer 
arithmetic.

2.  I stumbled on this issue when approximating the golden ratio $\phi$, 
the root of $\phi^2-\phi-1=0$, using the naive iteration 
$\phi_{n+1}=1+1/\phi_n$ with $\phi_1=1$, or, in Scheme:

(define (fib-ratio n)
   (if (= n 1)
       1
       (+ 1 (/ (fib-ratio (- n 1))))))

At the time (2003), Mzscheme used mini-gmp for integer arithmetic, and 
its own rational number routines were written roughly along the lines of 
those proposed here, and Gambit used the algorithms from Knuth.  The 
timings were

Mzscheme:

 > (time (fib 1000))
cpu time: 379490 real time: 454623 gc time: 450

Gambit:

(time (fib 1000))
     8 ms real time
     10 ms cpu time (10 user, 0 system)

So these numbers weren't really that big (about 700 bits in numerator 
and denominator) and there was about a factor of 40,000 difference in 
performance.

Brad