I've written bignum routines for addition and multiplication several times
when solving project euler problems. Generally my multiplication functions
bog down at about 200 digits -- i.e. take more than a second to run.
I decided to optimize, and about a dozen iterations later, the below is the
result. It will multiply two 5,000-digit numbers in about a second on my
machine, and even 20,000 digit multiplication seems to work in about 15
seconds or so (woot!).
Here's the weird part. I would have said that LC numbers are 32 bit, and
lose their minds at about 2 billion. The temp variable S in this function
gets large, and I wrote many lines of code working around that. Then I ran
some tests, and seemingly when multiplying a string of 20,0000 nines --
99999999...999999 -- even though S gets up to 499,949,990,000, all is well,
and the result is correct. I wonder how large S can get before it
overflows? I did some quick experiments without hitting a conclusive
answer, and I don't see it in the docs or online.
In the meantime, multiply really big integers here:
function bigTimes X,Y
if char 1 of X is "-" then
put "-" into leadChar
delete char 1 of X
end if
if char 1 of Y is "-" then
if leadChar is "-" then put empty into leadChar else put "-" into
leadChar
delete char 1 of Y
end if
put (3 + length(X)) div 4 * 4 into XL
put char 1 to XL - length(X) of "000" before X
put (3 + length(Y)) div 4 * 4 into YL
put char 1 to YL - length(y) of "000" before y
repeat with N = XL + YL down to 9 step -4
repeat with M = max(4,N - YL) to min(XL,N - 4) step 4
add (char M - 3 to M of X) * (char N - M - 3 to N - M of Y) to S
end repeat
put char -4 to -1 of S before R
delete char -4 to -1 of S
end repeat
if S is 0 then put empty into S
return leadChar & S & R
end bigTimes
_______________________________________________
use-livecode mailing list
use-livecode@lists.runrev.com
Please visit this url to subscribe, unsubscribe and manage your subscription
preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
