[gambit-list] Universal library improvements
Bradley Lucier
lucier at purdue.edu
Tue Mar 24 01:58:55 EDT 2020
I figured that users of the Javascript backend would prefer to have
smaller file sizes than speed improvements on "bigger" bignums (bigger
than about 2000 bits), so I just turned off the "fast" bignum algorithms
for Javascript in this commit:
https://github.com/gambit/gambit/commit/eda058a10772fa93beef9398c297e41f6f5b8638
I wanted to see what difference it might make in computation speed, so I
took the file chud1.scm from
https://mailman.iro.umontreal.ca/pipermail/gambit-list/2013-June/006789.html
which computes pi to varying number of digits, and built it as Marc
suggested. I then went back and turned fast algorithms back on
With "fast" algorithms:
firefly:~/programs/gambit/pi-programs> ./pi-js
Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits
10, CPU time: .01399993896484375.
Last 5 digits 26535.
Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits
100, CPU time: .003999948501586914.
Last 5 digits 70679.
Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits
1000, CPU time: .03099989891052246.
Last 5 digits 1989.
Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits
10000, CPU time: .7229998111724854.
Last 5 digits 75678.
Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits
100000, CPU time: 9.877000093460083.
Last 5 digits 24646.
Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits
1000000, CPU time: 154.63499999046326.
Last 5 digits 58151.
With no fast bignum algorithms:
firefly:~/programs/gambit/pi-programs> ./pi-js-old
Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits
10, CPU time: .01399993896484375.
Last 5 digits 26535.
Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits
100, CPU time: .004000186920166016.
Last 5 digits 70679.
Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits
1000, CPU time: .023000001907348633.
Last 5 digits 1989.
Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits
10000, CPU time: .8480000495910645.
Last 5 digits 75678.
Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits
100000, CPU time: 96.76300001144409.
Last 5 digits 24646.
Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits
1000000, CPU time: 11859.043999910355.
Last 5 digits 58151.
You don't really see much difference until you start computing 100,000
digits of pi (about 332,195 bits), were the "fast" algorithms are about
10 times as fast as the regular algorithms.
So I think that's the right trade-off to have slightly slower bignum
operations for "small" bignums for about 5% smaller library.
Brad
More information about the Gambit-list
mailing list