Large integer addition and subtraction -- dramatically improved

Geoff Canyon gcanyon at gmail.com
Mon Dec 14 13:22:23 EST 2015


I've created new routines for adding and subtracting large numbers. They
work on positive and negative integers, and are 10x to 20x and up faster
than any other routines I've seen (they are faster than routines I've
posted in the past). Also, they are optimized for mismatched arguments --
adding a 10 digit and 1000 digit number is substantially faster than adding
two 1000 digit numbers. The order of the arguments to the add function does
not matter: 10 digit plus 1000 digit will be as fast as 1000 digit plus 10
digit.

I have tested the results from these 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.

I'll work on multiplication and division later.

Here they are:

function bAdd x,y
   if char 1 of x is "-" then
      delete char 1 of x
      if char 1 of y is "-" then
         delete char 1 of y
         put "-" into theSign
      else
         return bSubtract(y,x)
      end if
   else
      if char 1 of y is "-" then
         delete char 1 of y
         return bSubtract(x,y)
      else
         put empty into theSign
      end if
   end if
   put length(x) into lenX
   put length(y) into lenY
   if lenX > lenY then
      put x into r
      put lenX into lenR
   else
      put y into r
      put lenY into lenR
      put x into y
      put lenX into lenY
   end if
   put 0 into c
   repeat with i = 14 to lenR step 14
      add char -i to 13 - i of r + char -i to 13 - i of y to c
      put char -14 to -1 of ("00000000000000" & c) into char -i to 13 - i
of r
      delete char -14 to -1 of c
      if i > lenY and c is empty then exit repeat
   end repeat
   put c before r
   put 0 + char 1 to 14 of r into char 1 to 14 of r
   return theSign & r
end bAdd

function bSubtract x,y
   if char 1 of x is "-" then
      if char 1 of y is "-" then
         delete char 1 of x
         delete char 1 of y
         put "-" into theSign
      else
         return bAdd(x,"-" & y)
      end if
   else
      if char 1 of y is "-" then
         return bAdd(x,char 2 to -1 of y)
      else
         put empty into theSign
      end if
   end if
   put length(x) into lenX
   put length(y) into lenY
   if lenX > lenY then
      put x into r
      put lenX into lenR
   else if lenX < lenY then
      if theSign is "-" then put empty into theSign else put "-" into
theSign
      put y into r
      put lenY into lenR
      put x into y
      put lenX into lenY
   else
      get bCompare(x,y)
      if it is "greater" then
         put x into r
         put lenX into lenR
      else if it is "less" then
         if theSign is "-" then put empty into theSign else put "-" into
theSign
         put y into r
         put lenY into lenR
         put x into y
         put lenX into lenY
      else
         return 0
      end if
   end if
   put 0 into c
   repeat with i = 14 to lenR step 14
      put char -i to 13 - i of r into s
      add char -i to 13 - i of y to c
      if s >= c then
         put s - c into s
         put 0 into c
      else
         put ("1" & s) - c into s
         put 1 into c
      end if
      put char -14 to -1 of ("00000000000000" & s) into char -i to 13 - i
of r
      if i > lenY and c = 0 then exit repeat
   end repeat
   put 0 + char 1 to 15 of r into char 1 to 15 of r
   return theSign & r
end bSubtract

function bCompare x,y -- only works on unsigned values
   put length(x) into lenX
   put length(y) into lenY
   if lenX > lenY then return "greater"
   if lenX < lenY then return "less"
   repeat with i = 1 to lenX step 14
      put char i to i + 13 of x into x1
      put char i to i + 13 of y into y1
      if x1 > y1 then return "greater"
      if x1 < y1 then return "less"
   end repeat
   return "equal"
end bCompare



More information about the Use-livecode mailing list