[gambit-list] Computing pi with parallel gambit
Bradley Lucier
lucier at math.purdue.edu
Mon Nov 28 11:21:58 EST 2016
On 11/27/2016 07:02 PM, Adam wrote:
>
> Maybe this is particularly relevant in places where the numerator and
> denominator within fractionals, are very big, e.g. (/ a b) where a and b
> are both the result of (/ (random-integer (expt 10 30)) (random-integer
> (expt 10 25)) or higher exponents than that.
Numbers of this size aren't really "big" for bignum purposes. For
example, we can find the bit length of a random integer < 10^30:
> (integer-length (random-integer (expt 10 30)))
100
So that random integer would fit into two 64-bit words (plus a header
word) in a bignum. It would hurt to try to parallelize things at this
level.
For really large multiplications/divisions/square roots (with results
with K > 10^9 bits), when we use Karatsuba multiplication there are
three multiplications of size K/2 bits, and this is recursive, so if K/2
is again too big for our FFT routine, we'd get 9 multiplications of size
K/4, or 27 multiplications of size K/8, etc., and we know that each of
these multiplications would take quite a few operations themselves.
This part would be easy to code.
Brad
More information about the Gambit-list
mailing list