Large integer multiplication -- dramatically improved
Geoff Canyon
gcanyon at gmail.com
Thu Dec 17 14:50:58 EST 2015
I've written large integer multiplication routines before. This is over
twice as fast as those were, and many times faster than other routines I've
seen. On my mac it will multiply two 9,000-digit numbers in under a second.
I've tested it up to multiplying two 100,000-digit numbers, which takes
about 45 seconds. This handles positive and negative arguments, and the
order (large, small, or small, large) does not matter.
I have tested the results with this over thousands of example numbers
against other large number libraries to ensure accuracy, but more testing
for edge cases is always appropriate. And of course if anyone has any
suggestions or questions I'm all ears.
div/mod is next, but not a rush, since I'm just doing this for fun.
function bTimes 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 X & Y into R
put "0000000000000000" into char 1 to 10 of R
put (6 + length(X)) div 7 * 7 into XL
put char 1 to XL - length(X) of "000000" before X
put (6 + length(Y)) div 7 * 7 into YL
put char 1 to YL - length(Y) of "000000" before Y
put length(R) - 6 into rStart
repeat with N = XL + YL down to 15 step -7
put min(XL,N - 7) into finalM
put 0 into C
repeat with startM = max(7,N - YL) to finalM - 7 step 630
repeat with M = startM to min(startM + 623,finalM) step 7
add (char M - 6 to M of X) * (char N - M - 6 to N - M of Y) to S
end repeat
add char 1 to -8 of S to C
delete char 1 to -8 of S
end repeat
put char -7 to -1 of ("000000" & S) into char rStart to rStart + 6 of
R
subtract 7 from rStart
put C into S
end repeat
if S > 0 then put S into char max(1,rStart) to rStart + 6 of R
put 0 into zR
repeat until zR > 0
put 0 + char 1 to 15 of R into zR
put zR into char 1 to 15 of R
end repeat
return leadChar & R
end bTimes
More information about the Use-livecode
mailing list