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

[Geoff Canyon]

Okay, now it's chunking by 7, and checking/avoiding overflows. This little
baby will multiply two 7,000 digit random numbers in right around a second
on my machine. Woot! If anyone sees further optimizations let me know.

For fun I wrote a factorial using bigTimesN7 -- bigFact(1100) comes out at
2577 digits in under a second.

Also just for laughs, I wrote a quick test to see if the size of X vs. Y
affects the speed, and it looks neutral.

function bigTimesN7 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 (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
   repeat with N = XL + YL down to 15 step -7
      repeat with M = max(7,N - YL) to min(XL,N - 7) step 7
         add (char M - 6 to M of X) * (char N - M - 6 to N - M of Y) to S
         if S > 900000019999997 then
            add char -20 to -8 of S to Scarry
            delete char -20 to -8 of S
         end if
      end repeat
      put char -7 to -1 of S before R
      add char -20 to -8 of S to Scarry
      put char -7 to -1 of Scarry into S
      delete char -7 to -1 of Scarry
   end repeat
   put Scarry before S
   if S is 0 then put empty into S
   return leadChar & S & R
end bigTimesN7




On Fri, Sep 6, 2013 at 8:35 AM, Geoff Canyon <gcanyon at gmail.com> wrote:

> 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.