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