[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