What is the size limit for numbers in LC? -- and multiplying really large numbers
Geoff Canyon
gcanyon at gmail.com
Fri Sep 6 21:05:22 CEST 2013
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.
More information about the use-livecode
mailing list