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