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

Bradley Lucier lucier at math.purdue.edu
Fri Sep 20 19:25:41 EDT 2013


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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: pidigits2-gambit.scm
Type: text/x-scheme
Size: 1314 bytes
Desc: not available
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20130920/f49b5ed5/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: _num-scm.patch
Type: text/x-patch
Size: 15340 bytes
Desc: not available
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20130920/f49b5ed5/attachment-0001.bin>


More information about the Gambit-list mailing list