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