<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">2016-11-29 0:21 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"><span class="gmail-">On 11/27/2016 07:02 PM, Adam wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
Maybe this is particularly relevant in places where the numerator and<br>
denominator within fractionals, are very big, e.g. (/ a b) where a and b<br>
are both the result of (/ (random-integer (expt 10 30)) (random-integer<br>
(expt 10 25)) or higher exponents than that.<br>
</blockquote>
<br></span>
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:<br>
<br>
> (integer-length (random-integer (expt 10 30)))<br>
100<br>
<br>
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.<br>
<br>
For really large multiplications/divisions/squa<wbr>re 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.<br></blockquote><div><br></div><div>Wait.. around what complexity of fractionals did you say parallellization of mul/div/sqrts starts becoming worth it?</div><div><br></div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">This part would be easy to code.<br></blockquote><div><br></div><div>Ok cool. :)</div><div><br></div><div><br></div><div><div>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?</div></div><div><br></div></div></div></div>