Here’s a program one of my friends challenged me to make. It basically takes two positive integers and multiplies them like a human would do it, digit by digit, carrying the one, etc. It’s not very useful, since it’s probably running in order n^2 or n! time, but it does have the advantage that it doesn’t end up using scientific notation, so it’s extremely accurate. I’m thinking of adding someting to do numbers with decimal points, but I might not, so I’m posting it now. Any suggestions on making it faster would be very much appreciated!
set {num1, num2} to {1234, 5678} --The two numbers to multiply
set {num1, num2} to {num1 as text, num2 as text}
set totallist to {}
repeat with i from 1 to length of num2
set bottomnum to (character (-1 * i) of num2 as number) --Take the first digit on the right of the first number
set total to 0 --This is the total for the first digit
repeat with j from 1 to length of num1 --Multiply it by each digit of the other number
set topnum to (character (-1 * j) of num1 as number)
set total to add((topnum * bottomnum) & zeroes(i + j - 2) as text, total)
end repeat
set end of totallist to (total as text) --This list has each digit's totals
end repeat
set resul to ""
repeat with k in totallist
set resul to add(contents of k, resul) --Add the list together
end repeat
repeat until character 1 of resul is not "0"
set resul to text 2 thru end of resul --Remove any stray leading zeroes
end repeat
return resul
to add(int1, int2) --Add two numbers "by hand"
set addplace to 0 --For carrying the one
set {int1, int2} to {"0" & int1 as text, "0" & int2 as text}
if length of int1 ≠length of int2 then --make both strings the same length by adding zeroes
if length of int1 < length of int2 then repeat until length of int1 = length of int2
set int1 to "0" & int1
end repeat
if length of int1 > length of int2 then repeat until length of int1 = length of int2
set int2 to "0" & int2
end repeat
end if
set res to ""
repeat with i from 1 to length of int1
set i to -i --So we go from right to left
set a to (character i of int1 as number) + (character i of int2 as number) + addplace as text
set res to (character -1 of a) & res
if length of a > 1 then
set addplace to 1
else
set addplace to 0
end if
end repeat
return res
end add
to zeroes(num) --To easily multiply things by ten by adding zeroes
set res to ""
repeat num times
set res to res & "0"
end repeat
return res
end zeroes
EDIT: In case anyone was wondering just how freakishly accurate this thing can get, 2^1024 - 1 (The largest number allowed before overflow on my version of AS) is 17976931348623159077293051907890247336179769789423065727343008115773267580550096313270847732240753602112011387987
1393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342
462881473913110540827237163350510684586298239947245938479716304835356329624224137215. This took quite a while to compute and is about 1.79E+308, if you’re wondering.
The method below doesn’t enter the text realm until the very end of the process, which is vastly more efficient. It also does the additions at the same time as the multiplications, which probably saves a bit of time too. I don’t think this constitutes cheating under the terms of the challenge! Not knowing the factors used to get 17976931348623159077293051907890247336179769789423065727343008115773267580550096313270847732240753602112011387987
1393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342
462881473913110540827237163350510684586298239947245938479716304835356329624224137215, I haven’t tested it with them.
on longMultiply(n1, n2)
set resultDigits to {} -- A collector for integers representing the digits of the final result.
set leftShift to 0 -- A left-shift indicator for the intermediate multiplication results.
-- For each digit from right to left in n2.
repeat until (n2 is 0)
-- Extract the digit value.
set n2digit to n2 mod 10
-- Get an intact copy of n1 .
set n1copy to n1
-- Start with no carry.
set carry to 0
-- Initialise an index to the last column in the result list so far that will coincide with this multiplication result.
-- Counting down this index will tell us when we need to add more columns at the front.
set c to (count resultDigits) - leftShift
-- For each digit from right to left in the duplicate of n1.
repeat until (n1copy is 0)
-- Multiply the n1 digit by the current digit from n2 and add any carry from the previous iteration.
set columnTotal to ((n1copy mod 10) * n2digit) div 1 + carry
if (c > 0) then
-- If the target column already exists in the result list, add its current value to this result.
set columnTotal to columnTotal + (item c of resultDigits)
-- . and update the column value to the lower digit of the total result.
set item c of resultDigits to columnTotal mod 10
else
-- Otherwise prepend a new column containing the lower digit of the multiplication + carry result.
set beginning of resultDigits to columnTotal mod 10
end if
-- Set the carry to any upper digit in the result of the above process.
set carry to columnTotal div 10
-- Prepare to extract the next digit from the duplicate n1.
set n1copy to n1copy div 10
-- Decrement the "existing column" index.
set c to c - 1
end repeat
-- If there's any carry after multiplying the whole of the duplicate n1 by the digit from n2, create a new column for it.
if (carry > 0) then set beginning of resultDigits to carry
-- Prepare to extract the next digit from n2.
set n2 to n2 div 10
-- Increase left shift by one more column.
set leftShift to leftShift + 1
end repeat
-- Coerce the list of digit values to text.
set astid to AppleScript's text item delimiters
set AppleScript's text item delimiters to ""
set resultString to resultDigits as string
set AppleScript's text item delimiters to astid
return resultString
end longMultiply
longMultiply(1234, 5678)
Smooth, Nigel. That works much faster than my version, but I think there’s an accuracy problem. I found 2^1024 by taking 2^32 and continually multiplying it by itself to get up to 1024. When I entered 2^512 * 2^512 into your program, our programs turn out different results. I think this test works:
Running a script that is only a number will return that number unless it it too large or you typed too many digits. So if I try to compile “1.797693134862315E+308” I will get the error “Syntax error. Some object.” If I change the 5 at the end to a 6, the number goes over the limit and I get “The result of a numeric operation was too large.” My program gives the 5 at the end for 2^1024, while yours produces a 9, making the number actually more than 2^1024. I think this has to do with the fact that you’re passing the function two numbers, which Applescript limits to a certian number of decimal places of accuracy.
Also, when entering numbers into the function, you cannot pass a number over 10 digits long without going into scientific notation. Luckily this program can avoid this by entering exponential expressions, but in those AS must chop off digits at the end.
If I try to multiply 2 ^ 32 by itself using your script, I get an error in the eighth line: ‘Can’t make “+” into type number.’ This is because the highest possible integer in AppleScript is 536870911 (2 ^ 29 - 1), the power operator returns a real anyway, and whole-number reals are rendered in scientific notation as from somewhere between 2 ^ 13 and 2 ^ 14. The only way to get your script to handle integers higher than 536870911 is to enter them as text “ which of course isn’t integers as specified in your first post. (I thought your upper limit was unfeasibly high!) If text representations of input numbers are allowed, though, that obviously goes beyond the range and precision of AppleScript numbers, which is why my script isn’t so accurate up that end of the scale. Happily, it’s easy to derive a text input version from it that’s still quite fast and can even go higher than yours, though I haven’t actually done the calculations by hand to see if the results are accurate.
on longMultiply(n1, n2)
-- The input numbers are assumed to be either integers or string representations thereof.
set n1 to n1 as string
set n2 to n2 as string
-- Determine if the result will be negative and arrange to skip any negative signs in the input numbers.
set n1start to 1
set n2start to 1
considering case
set neg to (n1 begins with "-")
if (neg) then set n1start to 2
if (n2 begins with "-") then
set neg to (not neg)
set n2start to 2
end if
end considering
script o
property n1digits : {} -- Will contain the individual digits of n1, as integers.
property resultDigits : {} -- Will contain integers representing the digits of the final result.
end script
-- Since we'll be accessing n1's digits many times each, pre-coerce its characters to a list of integers.
set n1count to (count n1)
if (n1start is 2) then set end of o's n1digits to "-" -- Not used. Just makes the list the same length as n1.
repeat with i from n1start to (n1count)
set end of o's n1digits to (character i of n1) as integer
end repeat
set leftShift to 0 -- The left-shift controller for the intermediate multiplication results.
-- For each digit from right to left in n2.
repeat with i from (count n2) to n2start by -1
-- Get the digit value.
set n2digit to (character i of n2) as integer
if (n2digit is 0) then
-- No need to multiply all n1's digits by 0.
set beginning of o's resultDigits to n2digit
else
set carry to 0
-- Get the index in the result list so far of the column (if it exists) to which the last digit of this multiplication
-- by n1 will be added. Counting down this index will tell us when we need to add more columns at the front.
set c to (count o's resultDigits) - leftShift
-- For each digit from right to left in the digits of n1.
repeat with j from n1count to n1start by -1
-- Multiply the n1 digit by the current digit from n2 and add any carry from the previous iteration.
set columnTotal to ((item j of o's n1digits) * n2digit) div 1 + carry
if (c > 0) then
-- If the target column already exists in the result list, add its current value to this result.
set columnTotal to columnTotal + (item c of o's resultDigits)
-- . and update the column value to the low-order digit of the total.
set item c of o's resultDigits to columnTotal mod 10
else
-- Otherwise prepend a new column containing the low-order digit of the (multiplication + carry) result.
set beginning of o's resultDigits to columnTotal mod 10
end if
-- Set the carry to the high-order digit of the total obtained above.
set carry to columnTotal div 10
-- Decrement the "existing column" index.
set c to c - 1
end repeat
-- If there's a carry after multiplying all of n1's digits by the digit from n2, create a new column for it.
if (carry > 0) then set beginning of o's resultDigits to carry
end if
-- Increase the left shift by another column.
set leftShift to leftShift + 1
end repeat
-- Zap any leading zeros in the final result list.
repeat with i from 1 to (count o's resultDigits)
if (item i of o's resultDigits is 0) then
set item i of o's resultDigits to ""
else
exit repeat
end if
end repeat
if (end of o's resultDigits is "") then
-- If all the digits were zapped (all zeros), return one "0".
set resultString to "0"
else
-- Otherwise, coerce the list of digits to text, along with a negative sign, if appropriate.
if (neg) then set beginning of o's resultDigits to "-"
set astid to AppleScript's text item delimiters
set AppleScript's text item delimiters to ""
set resultString to o's resultDigits as string
set AppleScript's text item delimiters to astid
end if
return resultString
end longMultiply
-- These numbers are too long for the Web page, but will be rendered correctly
-- in Script Editor when you click the "Open this Scriplet." link above.
longMultiply("179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216", "-179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216")
--> "-32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230656"
Edited: Now handles negatives, gives the correct result when either of the input numbers is “0”, and doesn’t bother to multiply by n1 when the current n2 digit is “0”.
Nigel,
You are a programming god. I’m amazed at how fast this goes (I think about 320 times as fast as mine, but that was just me counting, not the computer). I bow down to you.
Don’t do that, for goodness sake. There’s nothing supernatural about the code.
The trick in this case is to know that numerical operations are much faster than text operations. And since the exercise is principally a mathematical one with peripheral textual aspects, it makes sense to keep everything in the numerical realm for as long as possible and to minimise the use of text commands. That’s the main contributor to the speed of my script, although using a script object to reference the two lists also helps.
Here’s a version that handles “real” numbers too:
on longMultiply(n1, n2)
-- The input numbers are assumed to be either integers or reals or string representations thereof in decimal longhand.
set n1 to n1 as string
set n2 to n2 as string
-- Determine if the result will be negative and arrange to skip any negative signs in the input numbers.
set n1start to 1
set n2start to 1
set neg to (n1 begins with "-")
if (neg) then set n1start to 2
if (n2 begins with "-") then
set neg to (not neg)
set n2start to 2
end if
-- Get the decimal point character on this machine.
set decPoint to character 2 of (0.0 as string)
script o
property n1digits : {} -- Will contain the individual digits of n1, as integers.
property resultDigits : {} -- Will contain the digits of the final result, as integers.
end script
-- Since n1's digit characters will be accessed many times each, pre-coerce them to a list of integers.
set n1count to (count n1)
if (n1start is 2) then set beginning of o's n1digits to "-" -- Padding for programming convenience. Not used otherwise.
repeat with i from n1start to (n1count)
try
set end of o's n1digits to (character i of n1) as integer
on error msg number errNum
-- This character's either a decimal point or something spurious.
if (character i of n1 is not decPoint) then error msg number errNum
set n1count to n1count - 1
end try
end repeat
-- Initialise a left-shift controller for the intermediate multiplication results.
set leftShift to 0
-- This nested repeat block multiplies the digits of n1 by each digit in n2.
-- For each digit from right to left in n2.
repeat with i from (count n2) to n2start by -1
try
-- Get the digit value.
set n2digit to (character i of n2) as integer
if (n2digit is 0) then
-- No need to multiply all n1's digits by 0.
set beginning of o's resultDigits to n2digit
else
set carry to 0
-- Get the index in the result list so far of the column (if it exists) to which the last digit of this multiplication
-- by n1 will be added. Counting down this index will tell us when we need to add more columns at the front.
set c to (count o's resultDigits) - leftShift
-- For each digit from right to left in the digits of n1.
repeat with j from n1count to n1start by -1
-- Multiply the n1 digit by the current digit from n2 and add any carry from the previous iteration.
set columnTotal to ((item j of o's n1digits) * n2digit) div 1 + carry
if (c > 0) then
-- The target column already exists in the result list. Add its current value to this result.
set columnTotal to columnTotal + (item c of o's resultDigits)
-- . and update the column value to the low-order digit of the total.
set item c of o's resultDigits to columnTotal mod 10
else
-- Otherwise prepend a new column containing the low-order digit of the (multiplication + carry) result.
set beginning of o's resultDigits to columnTotal mod 10
end if
-- Set the carry to the high-order digit of the total obtained above.
set carry to columnTotal div 10
-- Decrement the "existing column" index.
set c to c - 1
end repeat
-- If there's a carry after multiplying all of n1's digits by the digit from n2, prepend a new column for it.
if (carry > 0) then set beginning of o's resultDigits to carry
end if
-- Increase the left shift by another column.
set leftShift to leftShift + 1
on error msg number errNum
-- This character in n2 is either a decimal point or something spurious.
if (character i of n2 is not decPoint) then error msg number errNum
end try
end repeat
set resultLength to (count o's resultDigits)
set astid to AppleScript's text item delimiters
-- The number of places after any decimal point in the result will be the sum of those after the points in the input numbers.
set AppleScript's text item delimiters to decPoint
set decPlaces to 0
if (n1 contains decPoint) then set decPlaces to (count text item 2 of n1)
if (n2 contains decPoint) then set decPlaces to decPlaces + (count text item 2 of n2)
if (decPlaces is 0) and ((n1 ends with decPoint) or (n2 ends with decPoint)) then
set decPlaces to 1
set end of o's resultDigits to 0
set resultLength to resultLength + 1
end if
if (decPlaces > 0) then
-- There will be a decimal point before the last 'decPlaces' digits we've obtained. Prepend it to the first of them.
set item -decPlaces of o's resultDigits to decPoint & item -decPlaces of o's resultDigits
-- Zap any trailing zeros that aren't concatenated to the decimal point.
set i to resultLength
repeat while (item i of o's resultDigits is 0)
set item i of o's resultDigits to ""
set i to i - 1
end repeat
end if
-- Zap any _leading_ zeros from the result list.
repeat with i from 1 to resultLength
if (item i of o's resultDigits is 0) then
set item i of o's resultDigits to ""
else
set firstNonZero to item i of o's resultDigits
-- Reinstate one leading zero if we've reached a decimal point concatenation.
if (firstNonZero's class is string) then set beginning of (o's resultDigits) to 0
-- Ensure that this exit route leaves i and resultLength with different values (for the test below).
set resultLength to resultLength + 1
exit repeat
end if
end repeat
if (i is resultLength) then
-- The result list was all zeros, which were zapped. Restore one of them.
set o's resultDigits to {0}
else if (neg) and (firstNonZero is not ".0") then
-- Otherwise, if the result's predicted to be negative and it isn't "0.0", insert the sign.
set beginning of o's resultDigits to "-"
end if
-- Coerce the result list to text.
set AppleScript's text item delimiters to ""
set resultString to o's resultDigits as string
set AppleScript's text item delimiters to astid
return resultString
end longMultiply
longMultiply("17.9769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216", "-1.79769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216")
--> "-32.317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230656"
There are more compact algorithms to do this, but why would anyone ever do this in AppleScript when you have bc available? Fire up terminal, read the man page for “bc”. Snuggle up. It does arbitrary precision math at a speed that AppleScript can’t dream of. If you feed it 233^645 you get the result:
880175066553007707425345945028785988439186447791744291686096109016635830052058580620419941962581938279103408830470501084567543345835829733779823467146062679515849863372241633135330991413643361036800457948802097449672538317539558048399738170716443747751155398590668759284907298519364418217931487493512140573860090075521588197499756975568137124819728931468777460396682644138880511383923215660606204967314209209822792244511296444777327121534099132191234875451152858088593212210885191689180695459127228773696344347591100607488154186223775372706802452482992887474834652104765698724394814598218655497052982544953408703665739119908939891698337330693555704019777735398361692878957475161987816609390628361438933290000951094547456668748046871657804861375119570829567406156806860843824724196192953785320975447305670206241894403292977527356396381586330995209909975665927971904243008840297157456186450660685078855583766131916506791677065119766485239500042839281914501299824189793038003712511966434080039844119510081376226093247893463741462792824688174802500003030419480553158589732060076961957878300250435711893645096474231104182681561415330305826593104948172332321977621974613238326296110942161863700019411158778989329174912864314213470094327917458665607317352472102631157686171738881453284773189452433120067777282971751578940582798504694615726046784107413362004682616497887761462098863146098844699522994688001888578974024325353176459849217471629268255104386980257276045653584645072961943513948197715051252462875795876044110069757620617993
before you have your hand off the key. If you haven’t warmed up to bc and you are into math then you need to take the plunge. Not only can you do stunningly large calculations, but you can define your own functions and load them when you start bc in interactive mode. You basically have an arbitrary precision calculator that will do a line by line interpretation of the code you feed it. It comprehends a syntax that is very nearly like C.
(note: the above line of digits goes waaaaay off the page, so copy and paste to see how long it is.)
If you want to check the results of your AppleScript code, use bc to check it. And also note that there is no issue with feeding arbitrarily long numbers to bc because stdin is always in text until it is fed to the UNIX application that will process it (std interfacing).
If you want to feed bc via AppleScript then you can do that with the do shell script command. I’ve got a system set up that I use all the time to do large binomial coefficient calculations and it’s triggered from TypeIt4Me. I type three letters, get an AppleScript dialog in which I can enter an arbitrary number of lines of code to feed bc, press enter and then I get the response in the clipboard. I could have manually encrypted the OED using RSA and bc in the time it took you to write all that code.
Come on guys, AppleScript is very cool and HUGELY useful, but for this job it sucks and bc buries it alive.
That’s undoubtedly true, since AppleScript wasn’t designed for situations where such large numbers need to be calculated with such precision. But in this case, The Experienced Noob started the thread for fun, sharing his response to a challenge from a friend. I certainly enjoyed joining in.
