Routines for very large numbers.

[golive]

GoLive.

The function "removeZeros" is part of MaxV's suite of handlers. It is not a native function. Look back at his post where he lists all his functions.

Craig

OIC. Thanks, I didn't think of that

[golive]

For example:

1 / 3 = 0.3 is not correct, it's an approximation 0.3=3/10
1 / 3 = 0.33 is not correct, it's an approximation 0.33=33/100
1 / 3 = 0.333 is not correct, it's an approximation 0.333=333/1000
1 / 3 = 0.333333333 is not correct, it's an approximation
1 / 3 = 0.3333333333333333333333333333 is not correct, it's an approximation
1 / 3 = 0.3333333333333333333333333333333333 is not correct, it's an approximation
1 / 3 = 0.3333333333333333333333333333333333333333333333333333333333 is not correct, it's an approximation
1 / 3 = 0 with remainder of 1. This is the only correct solution contemplating all digits

Ah yes, you are right. But one will normally need the result as a decimal to display an answer or to do further calculations.

Code: Select all

put bigDivide2(123,111) into tA
Put sqrt(tA) into tB

[geoffcanyon]

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.

I'll work on multiplication and division later.

Here they are:

Code: Select all

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

[geoffcanyon]

Edited to make a correction for arguments = 0.

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.

Code: Select all

function bTimes X,Y
   if X = 0 or Y = 0 then return 0
   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

[istech]

Thanks for your time Geoff. I will have a play with these today. Any performance gains is great.

[istech]

I hope all are fine,

Just a small update on this thread. I have run into some small issues with this same problem with numbers larger than 17 digits. example

If you try to compare 2 digits over 17 digits and the numbers over that limit are different it will always be positive.

Code: Select all

if "12345678901234561234" = "12345678901234561235" then
answer "same number" with "okay" --will always be true
end if

To add I have been doing some benchmarks on the custom functions so nicely donated by the community. I would love to see some improvement on them to come within range of lc internal functions. see below

Livecode version 8.1.2 - intel i7

10000, 20 digit computations

BigDivide2 153ms
BigTimesN7 817ms
BigAdd 1483ms
BigSubtract 2123ms

bTimes 807ms
bAdd 267ms
bSubtract 171ms

lc's internal at 17 digit limit
add 2ms
sub 2ms
times 2ms
div 2ms

[dunbarx]

Now I smugly thought that putting those strings in quotes would be certain to yield "false":

Code: Select all

answer "12345678901234561234" = "12345678901234561235" --last digit different

It does not. Changing the length of one of those strings gives a "false", and changing any digit in the first 16 does as well, but changing any after that makes no difference. I assume the engine is resolving these strings into numbers. But then why would a simple length change in one string, with the difference between them well beyond the magic 17 digits, that difference being therefore, out of range, give "false"?

Is there no way to force those strings to stay strings, without having to type them? Would this not be an issue in LCB?

Craig

[istech]

Yes I was typing fast. However tried both with and without quotes. Same result. It's like after the limit is sees the numbers as "0" after. Very annoying when you are scratching your head for half an hour. I'm actually surprised its not come up sooner.

[[-hh]]

Just to complete this interesting discussion with another option.

You could use python's bignum package via shell (or more advanced: use sockets).
Here is a stack that show hows to do this, use example 1 for start.
What one should know: In Python is "power" not "^" but "**", for example 2^5 is in python 2**5.

Python helper (= Raspi stacks collection #22) http://forums.livecode.com/viewtopic.ph ... 55#p101655

[istech]

Just to complete this interesting discussion with another option.

You could use python's bignum package via shell (or more advanced: use sockets).
Here is a stack that show hows to do this, use example 1 for start.
What one should know: In Python is "power" not "^" but "**", for example 2^5 is in python 2**5.

Python helper (= Raspi stacks collection #22) http://forums.livecode.com/viewtopic.ph ... 55#p101655

Thanks for the great post. Going to give this a try and compare the performance. However using long numbers would still be a problem unless I use python? or a custom LC function to check. See below:

Code: Select all

   put "12345678912345678919" into t
   switch
      case t = "12345678912345678912"
         answer "same number - 1" with "okay"  --still true
         break
      case t = "12345678912345678913"
         answer "same number - 2" with "okay" --still true
         break
   end switch

[[-hh]]

Yes, of course. You can't currently have numbers outside the 64-bit IEEE precision.

I you have a display outside this precision range then the additional digits are random.
You can for example set the numberformat to "0000000000000000000.00000000000000000000", but that's just for fun.

Whenever a bignum is possible to occur you then have do to every arithmetic operation with python's bignum (does all checks for you). Else you may lose precision or are possibly accumulating rounding errors.

Even if you use "selfmade" bignum operations (maxV did here already a great job) you could use python's bignum for testing your handlers.

I use it for few computations, because it's not worth to launch Mathematica for a few things.
By the way, you can of course also use Mathematica (for example the free version on a Raspberry Pi running Raspbian) to do exact computations via LC's shell, see for example the demo stack here: http://forums.livecode.com/viewtopic.ph ... 22#p133422