mini-gmp and mpq

Bradley Lucier lucier at
Mon Feb 26 20:03:47 UTC 2018

On 02/26/2018 05:09 AM, Torbjörn Granlund wrote:
> Bradley Lucier <lucier at> 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 

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 (/ (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


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


(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 


More information about the gmp-devel mailing list