[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