<div dir="ltr">Brad,<div><br></div><div>I can clearly see times when it would be preferential to distribute the execution of multiplications, divisions (and square roots) to all Gambit processors.</div><div><br></div><div>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.</div><div><br></div><div>The point would be that a program sometimes not can anticipate when it will run into such heavy operations, however when it does, generally but not always, a user is waiting and it's preferable to parallellize it.</div><div><br></div><div>Could some kind of parallellize-math? setting be introduced, with what scope, thread-local or processor-local or global?</div><div><br></div><div>By the way, how many cores could the fractional above be spread across, and approx what speedup over serial execution could probably be attained?</div><div><br></div><div>And what about the same for the fractional but with the exponents doubled in size to 60 and 50?</div><div><br></div><div><div>This is not a super high priority but thanks for bringing it up.</div></div><div><br></div><div>Thanks,</div><div>Adam</div><div><br></div><div class="gmail_extra"><div class="gmail_quote">2016-11-28 4:08 GMT+08:00 Bradley Lucier <span dir="ltr"><<a href="mailto:lucier@math.purdue.edu" target="_blank">lucier@math.purdue.edu</a>></span>:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Marc:<br>
<br>
Because of accumulated roundoff error in IEEE floating-point arithmetic,<br>
Gambit's FFT-based bignum multiplication algorithm is limited to<br>
multiplying two numbers each of which has <= 2^{29} bits (on a 64-bit<br>
machine).<br>
<br>
Multiplying larger numbers falls back on Karatsuba multiplication, which<br>
cuts the size of the multiplicands roughly in half in each step, until<br>
you get back down to numbers of <= 2^{29} bits again, in which case FFT<br>
is used again.<br>
<br>
So, in fact, to compute a billion decimal digits of pi, we rely on<br>
Karatsuba to do the largest multiplications (and divisions and square<br>
roots, since they all reduce to multiplication).<br>
<br>
On a machine with enough memory, all the "sub-multiplications" in<br>
Karatsuba can be done in parallel.  I haven't figured out how much<br>
memory is needed; it takes a few GB of temporary RAM to multiply the<br>
largest numbers with the FFT algorithm.<br>
<br>
I believe it took about 16GB total to calculate a billion decimal digits<br>
of pi using the current serial algorithm.<br>
<br>
Once parallel gambit is usable, computing pi to a billion (or even 10<br>
billion, who knows) digits by parallelizing the larger Karatsuba<br>
multiplications might be a good test of the system.<br>
<br>
Brad<br>
______________________________<wbr>_________________<br>
Gambit-list mailing list<br>
<a href="mailto:Gambit-list@iro.umontreal.ca">Gambit-list@iro.umontreal.ca</a><br>
<a href="https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list" rel="noreferrer" target="_blank">https://webmail.iro.umontreal.<wbr>ca/mailman/listinfo/gambit-<wbr>list</a><br>
</blockquote></div><br></div></div>