# mini-gmp and mpq

Mon Feb 26 20:03:47 UTC 2018

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.