On Sep 5, 2013, at 6:11 PM, Mark Schonewille <[email protected]>
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.
_______________________________________________
use-livecode mailing list
[email protected]
Please visit this url to subscribe, unsubscribe and manage your subscription
preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
