On 2013-09-20, at 7:25 PM, Bradley Lucier lucier@math.purdue.edu wrote:
Marc:
Please find enclosed a patch that speeds bignum division in the common case where (quotient a b) is a relatively small integer.
Please apply this patch even though it's not a git fetch request. It's been going around in my head for a long time now, and I'd like to get rid of it before I learn about git.
In pidigit.scm, a spigot algorithm for calculating the digits of pi, all (or almost all, I haven't checked) of the quotients return a single decimal digit. So this new code improves this performance of this benchmark a bit: To calculate 10,000 decimal digits of pi:
Before the patch:
firefly:~/programs/gambit/4.6.8/gambit> time ./pidigits2-gambit > /dev/null 5.560u 0.052s 0:05.63 99.6% 0+0k 0+0io 0pf+0w firefly:~/programs/gambit/4.6.8/gambit> time ./pidigits2-gambit > /dev/null 5.564u 0.044s 0:05.62 99.6% 0+0k 0+0io 0pf+0w firefly:~/programs/gambit/4.6.8/gambit> time ./pidigits2-gambit > /dev/null 5.588u 0.048s 0:05.65 99.4% 0+0k 0+0io 0pf+0w
After the patch:
firefly:~/programs/gambit/4.6.8/gambit> time ./pidigits2-gambit > /dev/null 4.684u 0.024s 0:04.72 99.5% 0+0k 0+0io 0pf+0w firefly:~/programs/gambit/4.6.8/gambit> time ./pidigits2-gambit > /dev/null 4.676u 0.040s 0:04.73 99.5% 0+0k 0+0io 0pf+0w firefly:~/programs/gambit/4.6.8/gambit> time ./pidigits2-gambit > /dev/null 4.648u 0.032s 0:04.69 99.5% 0+0k 0+0io 0pf+0w
The code may also improve the performance of (very) bignum gcd, but I haven't checked that.
Thoroughly "white box" and "black box" tested.
The code includes better bignum shift code that I plan to use later in other places.
Brad <pidigits2-gambit.scm><_num-scm.patch>
Unfortunately there's something wrong with your patch. Here's the output of "make check" on my Mac.
Marc
------------ TEST 3 (interpreter and library functions) ../gsi/gsi -:s,~~bin=../bin,~~lib=../lib,~~include=../include -f -e '(begin (load "r4rstest.scm") (test-cont) (test-sc4) (test-delay) (exit))' > test3.out diff test3.ok test3.out && rm -f test3.out tmp* 582,584c582,601 < ==> #t < ==> #t < ==> #t ---
Number readback failure for (+ 1. (* -97 2.220446049250313e-16)) .9999999999999785 Number readback failure for (+ 10. (* -94 1.7763568394002505e-15)) 9.999999999999833 Number readback failure for (+ 100. (* -98 1.4210854715202004e-14)) 99.99999999999861 ==> #f BUT EXPECTED #t Number readback failure for (+ 3. (* -85 4.440892098500626e-16)) 2.9999999999999623 Number readback failure for (+ 30. (* -83 3.552713678800501e-15)) 29.999999999999705 Number readback failure for (+ 300. (* -80 5.684341886080802e-14)) 299.99999999999545 ==> #f BUT EXPECTED #t Number readback failure for (+ 7. (* -94 8.881784197001252e-16)) 6.9999999999999165 ==> #f BUT EXPECTED #t
621c638,643 < Passed all tests ---
errors were: (SECTION (got expected (call))) ((6 5 6) (#f #t (mult-float-print-test #f))) ((6 5 6) (#f #t (mult-float-print-test #f))) ((6 5 6) (#f #t (mult-float-print-test #f)))
631c653,658 < Passed all tests ---
errors were: (SECTION (got expected (call))) ((6 5 6) (#f #t (mult-float-print-test #f))) ((6 5 6) (#f #t (mult-float-print-test #f))) ((6 5 6) (#f #t (mult-float-print-test #f)))
647c674,679 < Passed all tests ---
errors were: (SECTION (got expected (call))) ((6 5 6) (#f #t (mult-float-print-test #f))) ((6 5 6) (#f #t (mult-float-print-test #f))) ((6 5 6) (#f #t (mult-float-print-test #f)))
658c690,695 < Passed all tests ---
errors were: (SECTION (got expected (call))) ((6 5 6) (#f #t (mult-float-print-test #f))) ((6 5 6) (#f #t (mult-float-print-test #f))) ((6 5 6) (#f #t (mult-float-print-test #f)))
make[1]: *** [test3] Error 1 make: *** [check] Error 2