What is the size limit for numbers in LC? -- and multiplying really large numbers

Geoff Canyon gcanyon at gmail.com
Fri Sep 6 09:35:32 EDT 2013


On Sep 5, 2013, at 6:11 PM, Mark Schonewille <m.schonewille at economy-x-talk.com> wrote:

> Perhaps you should add some comments to your script.

What, it's not obvious? ;-) 

My first versions of this were list-based, and scaled poorly because of the line painter's problem (each day the paint bucket is farther away). More than about 300 digit numbers and the execution time exploded.

Arrays instead of lists handled about 600 digits. The complexity of multiplication scales roughly as the product of the lengths of the numbers, so 600 digits vs. 300 means arrays were a 4x improvement. 

Several iterations followed, including pre-chunking the numbers, simplified storage of results, and most importantly, dealing with 4-digit chunks. At the time, I thought LC topped out at 32-bits: 2 billion. That's not a full 10 digits, so 4x4 made sense. Chunking the numbers to generate 4 digits at a time multiplies around 1000 digits in a second. 

The central loop for this had several statements in it: get the product of the two current chunks, break the product apart, put each part in the right place, etc. I found that simply appending the products to a list, and then summing each list at the end and breaking apart, parsing, and stitching together the sums was about 1.5x faster. This was where my concerns about the size of the numbers started. As long as I was immediately breaking each chunk product apart to add/store, I could never overflow LC's numbers. Doing the sum all at once means that when multiplying two 2000-digit numbers, if they're all 9s, the sum will be 500*9999*9999 = about 50 billion. Nothing broke, so I kept going. 

I experimented with pre-calculating 2-digit products and referencing an array instead of multiplying over and over, but it was slower. 

Then I realized: if I calculate the final result from least significant digit up, I can do everything in the loop and build the actual result there. The trick is to consider the places of the numbers, and process all the intermediate products in order from smallest place to largest. So to multiply 1234 * 5678:

The one's digit depends on 4*8.
The ten's digit depends on 3*8 and 4*7, with any carry from 4*8
The hundred's digit depends on 2*8, 3*7, and 4*6, with any carry.
Etc.

I did that, a digit at the time, and multiplied around 2500 digits in a second. 

Then I had to chunk it. 4 digits at a time, and few other bits, and here we are.

function bigTimes X,Y
 -- returns the product of any positive or negative numbers. Good to about 20,000 digits. I'll show how it multiplies X=-1234567 and Y=234567890

-- handle negative inputs
   if char 1 of X is "-" then 
      put "-" into leadChar
      delete char 1 of X
   end if
-- X is now 1234567, and leadChar is -
   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

-- pad the numbers to a multiple of 4 digits
   put (3 + length(X)) div 4 * 4 into XL
   put char 1 to XL - length(X) of "000" before X
   put (3 + length(Y)) div 4 * 4 into YL
   put char 1 to YL - length(y) of "000" before y

-- X is now 01234567
-- Y is now 000234567890

-- start from the sum of the lengths, and go down by 4s
-- this will be 20, 16, 12, 8 because negative steps overshoot
   repeat with N = XL + YL down to 9 step -4
 -- for each value in the outer loop, loop through all the 
 -- possible positions to use for the chunk of X
 -- this chunks the numbers into 4 digits
 -- when N = 12, we will add 0123*3456 + 4567*0002
 -- to whatever the carried-over value was
      repeat with M = max(4,N - YL) to min(XL,N - 4) step 4
 -- for each chunk from X, there is only one corresponding chunk of Y
 -- this is the one line that gets it all done
         add (char M - 3 to M of X) * (char N - M - 3 to N - M of Y) to S
      end repeat
 -- 0123*3456 + 4567*0002=> 434222 (pretending there was no carried value)
 -- so put 4222 before the result, and leave 43 in S as the carried value
      put char -4 to -1 of S before R
      delete char -4 to -1 of S
   end repeat
-- clean up any leading 0
   if S is 0 then put empty into S
-- return the sign of the result, remaining carried value, and the calculated result
   return leadChar & S & R
end bigTimes


This could be made faster by parsing into 5, 6, or 7 digit chunks, and either living with the size limitation of the operands, or adding back the safety code. Multiplying two 10,000 digit numbers in a second would be pretty tempting to try over the weekend.



More information about the use-livecode mailing list