[gambit-list] Computing pi with parallel gambit
Bradley Lucier
lucier at math.purdue.edu
Tue Dec 13 12:05:53 EST 2016
Marc:
About a parallel bignum library ...
I think it depends on what we want to accomplish with bignums in Gambit.
When we started, we wanted to use Jon L White's ideas to design a fully
portable, relatively efficient while still using naive algorithms,
bignum implementation for 32- and 64-bit big- and little-endian
machines, all written in Scheme except for a small number of word-level
primitives. So we did that.
Then we saw that Karatsuba's algorithm for multiplication is very easy
to implement, and we were off to the races.
In the end, we used a relatively novel algorithm for large
multiplication (but not too large, good up to about a billion bits).
Given this multiplication algorithm, we added a novel GCD, state-of-the
art sqrt (following Zimmermann), and a division based on the usual trick
of computing the inverse and multiplying (which helped with conversion
of large numbers to strings).
For a while for a few operations for a certain range of size of inputs
Gambit was faster than GMP, but this has not been true for a long time.
GMP is now faster than Gambit in everything. Much of the low-level
routines in GMP are written in assembly code, tuned for various Intel,
AMD, and Arm processors.
So now that we might have parallelism, what should we do?
If you want a test-bed for the parallel runtime, bignum arithmetic would
be a possibility. But I don't see Gambit beating GMP for any reasonable
range of argument sizes and choice of operations.
Other application areas might be just as good a testbed for parallelism.
What are our goals?
Brad
More information about the Gambit-list
mailing list