Dear Brad,
Benchmark seems to show that doing any the following operations below with a and b as argument compared to doing the same with c and d as argument is about the following X slower:
*: 179x (0.23345 vs 0.0013 ms per operation)
/: 2.7x (0.23269 vs 0.0889 ms per operation)
+: 202x (0.12112 vs 0.0006 ms per operation)
-: 200x (0.12008 vs 0.0006 ms per operation)
I guess this is because in the further case, the respective operation involves the calculation of a lowest common denominator for the divisor (i.e. what makes (+ 1/3 (+ 3/4 5/6)) and (+ (+ 1/3 3/4) 5/6) get the same result)?
If so, I guess we can be clear that primarily for * + - , in batch calculations there'd be value in having the ability to perform those operations without that calculation, and then making a separate operation for that function - or are the algorithms such that postponing wouldn't actually be for the win?
At what location in Gambit's sources is this calculation performed?
The code begins here.
If you look at the code for ##ratnum.+ and ##ratnum.-, you’ll see that with random integer numerators and denominators, most likely d1 will be a small integer (usually 1).
If d1 is 1, there’s a shortcut to the answer; if it’s a small integer then in the rest of the computation many operations involve at least one small integer.
So basically, there will be one gcd between two bignums for ##ratnum.+ and ##ratnum.-
If you look at the code for ##ratnum.* and ##ratnum./, you’ll see that two gcd’s will always be done on two bignums. That seems to be why * and / take about twice as long as + and -.
GCD, as implemented in Gambit, is $O(N^2)$ operations on numbers with $N$ digits (when $N$ is relatively small, (expt 10 100) is small), so it may be best to do the gcd’s with the smallest possible numbers, as we try to do here.
Division takes the longest times with two bignum arguments, but that’s because they’re converted to ratnums and then ##ratnum./ is called on them. There is only one nontrivial gcd call.
The algorithms are out of Knuth, volume 3.
Brad
Thanks,
Mikael
(define (r) (random-integer (expt 10 100)))
(define a (/ (r) (r)))
(define b (/ (r) (r)))
(define c (r))
(define d (r))