[gambit-list] Computing pi with parallel gambit

Adam adam.mlmb at gmail.com
Thu Dec 1 21:43:06 EST 2016


2016-11-29 0:21 GMT+08:00 Bradley Lucier <lucier at math.purdue.edu>:

> 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.
>

Wait.. around what complexity of fractionals did you say parallellization
of mul/div/sqrts starts becoming worth it?


This part would be easy to code.
>

Ok cool. :)


Talking about bignum performance, what about addition and subtraction. How
much of the energy is spent doing the actual add/sub and how much is spent
doing the least-common-denominator calculation that's done on each
calculation?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20161202/dba3a41f/attachment.htm>


More information about the Gambit-list mailing list