<html><head><meta http-equiv="Content-Type" content="text/html charset=windows-1252"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><br><div><div>On Oct 9, 2014, at 3:17 PM, Mikael <<a href="mailto:mikael.rcv@gmail.com">mikael.rcv@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"><div dir="ltr">Dear Brad,<div><br></div><div>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:</div><div><br></div><div><font face="courier new, monospace">*: 179x (0.23345 vs 0.0013 ms per operation)</font></div><div><font face="courier new, monospace">/: 2.7x (0.23269 vs 0.0889 ms per operation)</font></div><div><font face="courier new, monospace">+: 202x (0.12112 vs 0.0006 ms per operation)</font></div><div><font face="courier new, monospace">-: 200x (0.12008 vs 0.0006 ms per operation)</font></div><div><br></div><div>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)?</div><div><br></div><div><br></div><div>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?</div><div><br></div><div><br></div><div>At what location in Gambit's sources is this calculation performed?</div></div></blockquote><div><br></div>The code begins here.</div><div><br></div><div><a href="https://github.com/feeley/gambit/blob/master/lib/_num.scm#L10133">https://github.com/feeley/gambit/blob/master/lib/_num.scm#L10133</a></div><div><br></div><div>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).</div><div><br></div><div>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.</div><div><br></div><div>So basically, there will be one gcd between two bignums for ##ratnum.+ and ##ratnum.-</div><div><br></div><div>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 -.</div><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>The algorithms are out of Knuth, volume 3.</div><div><br></div><div>Brad</div><div><br><blockquote type="cite"><div dir="ltr"><div><br></div><div>Thanks,</div><div>Mikael</div><div><br></div><div><br></div><div>(define (r) (random-integer (expt 10 100)))</div><div><div><br></div><div>(define a (/  (r)  (r)))</div><div>(define b (/  (r)  (r)))</div></div><div><br></div><div><div>(define c (r))</div><div>(define d (r))</div></div><div><br></div></div>
</blockquote></div><br></body></html>