[gambit-list] Patch to speed bignum division in common case

Marc Feeley feeley at iro.umontreal.ca
Tue Sep 24 17:00:48 EDT 2013


On 2013-09-20, at 7:25 PM, Bradley Lucier <lucier at 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




More information about the Gambit-list mailing list