On 10/22/2013 10:48 AM, Marc Feeley wrote:
On 2013-10-21, at 4:55 PM, Bradley Lucier lucier@math.purdue.edu wrote:
Marc:
This patch estimates the size of the quotient much more carefully (at the bit level); it also starts the computation with the first possible nonzero mdigit of the quotient. So it's faster in the very important case of small (but still bignum) dividend and divisor.
Have you measured how much faster?
With
(define (time-test n) (let* ((divisor (do ((i 1 (* i 2))) ((##bignum? i) (+ i 1)))) (dividend (+ (* divisor 3) (quotient divisor 4)))) (pretty-print (list ##bignum.adigit-width ##bignum.mdigit-width (##bignum.adigit-length dividend) (##bignum.adigit-length divisor))) (time (do ((i 0 (fx+ i 1))) ((fx= i n)) (naive-div-orig dividend divisor)))
(time (do ((i 0 (fx+ i 1))) ((fx= i n)) (naive-div-new dividend divisor)))))
(the quotient is 3) with a 32-bit gambit (64-bit adigits, 16-bit mdigits) configured with
v4.7.0 20131009203852 x86_64-unknown-linux-gnu "./configure 'CC=gcc -march=native -m32' '--enable-single-host'"
on a rather old
model name : Intel(R) Core(TM)2 Quad CPU Q8200 @ 2.33GHz
you get
(time-test 1000000)
(64 16 1 1) (time (do ((i 0 (fx+ i 1))) ((fx= i n)) (naive-div-orig dividend divisor))) 1364 ms real time 1364 ms cpu time (1364 user, 0 system) 129 collections accounting for 25 ms real time (28 user, 0 system) 136034976 bytes allocated no minor faults no major faults (time (do ((i 0 (fx+ i 1))) ((fx= i n)) (naive-div-new dividend divisor))) 585 ms real time 584 ms cpu time (584 user, 0 system) 113 collections accounting for 21 ms real time (4 user, 0 system) 120029024 bytes allocated no minor faults no major faults
with a 64-bit gambit (64-bit adigits, 32-bit mdigits) configured with
v4.7.0 20131009203852 x86_64-unknown-linux-gnu "./configure 'CC=gcc -march=native' '--enable-single-host'"
on the same machine you get
(time-test 1000000)
(64 32 1 1) (time (do ((i 0 (fx+ i 1))) ((fx= i n)) (naive-div-orig dividend divisor))) 901 ms real time 900 ms cpu time (896 user, 4 system) 148 collections accounting for 30 ms real time (24 user, 0 system) 176026208 bytes allocated no minor faults no major faults (time (do ((i 0 (fx+ i 1))) ((fx= i n)) (naive-div-new dividend divisor))) 536 ms real time 536 ms cpu time (536 user, 0 system) 135 collections accounting for 27 ms real time (24 user, 0 system) 160028064 bytes allocated no minor faults no major faults
That's with the additional slight tweak in the included patch.
So that was almost a "brown paper bag" patch: for small quotients (fits in an mdigit) and small dividends it's about twice as fast.
Brad