# Using Applescript to handle each digit of VERY big numbers

Hi All -

Some years ago I was taken up with solving the Project Euler problems (http://projecteuler.net/problems) and I wrote some routines for big numbers in VBA. I wondered how Applescript compared to VBA, so I translated a few. These routines work by adding digits by strings, vice as numbers.

``````
property Buffer : {}

repeat with i from 1 to N
set the end of padding to X
end repeat

set Buffer to {}
set carry to 0
set soln to 0
set L1 to length of Adder1
set L2 to length of Adder2
if L1 > L2 then
else if L2 > L1 then
end if
set L1 to length of Adder1 -- Also the length of Adder2
repeat with i from L1 to 1 by -1
set soln to carry + (text i of Adder1)
set soln to soln + (text i of Adder2)
set carry to (soln div 10)
if i â‰  1 then
set the end of Buffer to (soln mod 10)
else
set the end of Buffer to soln
end if
end repeat
set Answer to the reverse of Buffer

on MultByStrings(Multiplicand, Multiplier)
set Rslt to Multiplicand
repeat with i from 1 to Multiplier - 1
end repeat
return Rslt
end MultByStrings

on PowerByStrings(Nmbr, Power)
set Rslt to "1"
repeat with i from 1 to Power
set Rslt to MultByStrings(Rslt, Nmbr)
end repeat
return Rslt
end PowerByStrings

on FactorialByStrings(Nmbr)
set Rslt to "1"
repeat with i from 1 to Nmbr
set Rslt to MultByStrings(Rslt, i)
end repeat
return Rslt
end FactorialByStrings

``````

Using the above, 45^45 is 248063644451341145494649182395412689744530581492654164321720600128173828125.

``````
return PowerByStrings(45, 45)

``````

80! is 71569457046263802294811533723186532165584657342365752577109445058227039255480148842668944867280814080000000000000000000

``````
return FactorialByStrings(80)

``````

1234567890*5321 is 5334567852690

``````
MultByStrings("1234567890", "4321")

``````

69011111111111111111111+1234521 is 69011111111111112345632

``````

``````

Project Euler Question 16 asks: What is the sum of the digits of the number 2^1000?

You can do it at least three ways with the above.

``````
set M2 to PowerByStrings(2, 1000)
repeat with i from 1 to length of M2
end repeat

``````

or

``````
set expt to 1000
set M1 to "2"
repeat with i from 2 to expt
set M1 to M2
end repeat
repeat with i from 1 to length of M2
end repeat

``````

or

``````
set M2 to "2"
repeat with i from 2 to 1000
set M2 to MultByStrings(M2, 2)
end repeat
repeat with i from 1 to length of M2
end repeat

``````

All versions take about 9 seconds. Not to give away the answer, but 2^1000 is 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376 exactly.

Applescript suffers speedwise vs. VBA. I’d be interested in any tips to speed this up.

…Mick

This is quite slick. I’ll leave it here to get the “make it faster” question answered, but in the end, I’d like to move the whole string to Code Exchange.

Just a suggestion

Wouldn’t it be efficient to work upon lists versus strings, using the property tip of course ?

Yvan KOENIG (VALLAURIS, France) dimanche 12 janvier 2014 21:32:32

My original post is here: http://dailydoseofexcel.com/archives/2008/12/22/euler-problem-16/ 5+ years ago There are speedups suggested in the replies, but I couldn’t figure out how to consistently prevent scientific notation being implemented by Applescript except when I did it one digit at a time. I’m Michael over there.

Hi Yvan -

I did do a list. Research suggested a property: list {} gives the fastest data retrieval. I didn’t to a reference to the property because that seemed to make no difference. Digits were sent to the end of the list in right-to-left order. The last step is to reverse the listin to left to right order.

…Mick

Oops

One more time I read too fast.

Yvan KOENIG (VALLAURIS, France) lundi 13 janvier 2014 10:15:40

Using (id of text i of something) - 48 instead of just text i of something seems to speed up things by a factor greater than 2, presumably because taking the id of a character is less expensive than casting a string to an integer.

Other than that, I couldn’t significantly improve AddByStrings() in other ways. The bottleneck of that code is the parallel iteration over the two strings, and I don’t think you could do much better than what you’re already doing (I wish someone could prove me wrong!). Creating scripts or properties on the fly and/or taking references does not seem to help much in this case.

I guess you might squeeze some more performance if you implemented multiplication directly instead of using addition.

Hi.

1. Integers up to nine digits are safe from conversion to scientific notation as long as the first digit remains quite low. When adding two numbers, the carry digit can never be more than 1, so it’s safe to add eight-digit integers.

2. When coercing lists to text, AppleScript’s text item delimiters should be explicitly set to “” or to {“”} for safety.

3. There doesn’t appear to be any advantage here to using references to the lists, since the lists are relatively short and most of the time is taken up by the coercions.

``````on chop(N)
set A to {}
set L to (count N)
repeat (L div 8) times
set beginning of A to text (L - 7) thru L of N
set L to L - 8
end repeat
if (L > 0) then set beginning of A to text 1 thru L of N

return A
end chop

set L1 to (count A1)
set L2 to (count A2)
if (L2 > L1) then
tell A1
set A1 to A2
set A2 to it
end tell
tell L1
set L1 to L2
set L2 to it
end tell
end if

set carry to 0
repeat with i from -1 to -L2 by -1
set s to (item i of A1) + (item i of A2) + carry
set item i of A1 to text 2 thru 9 of ((100000000 + s) as text)
set carry to s div 100000000
end repeat
repeat with i from -L2 - 1 to -L1 by -1
if (carry is 0) then exit repeat
set s to (item i of A1) + carry
set item i of A1 to text 2 thru 9 of ((100000000 + s) as text)
set carry to s div 100000000
end repeat
set item 1 of A1 to ((beginning of A1) + carry * 100000000) as text

set astid to AppleScript's text item delimiters
set AppleScript's text item delimiters to ""
set A1 to A1 as text
set AppleScript's text item delimiters to astid

return A1

on MultByStrings(Multiplicand, Multiplier)
set Rslt to Multiplicand
repeat with i from 1 to Multiplier - 1
end repeat
return Rslt
end MultByStrings

on PowerByStrings(Nmbr, Power)
set Rslt to "1"
repeat with i from 1 to Power
set Rslt to MultByStrings(Rslt, Nmbr)
end repeat
return Rslt
end PowerByStrings

on FactorialByStrings(Nmbr)
set Rslt to "1"
repeat with i from 1 to Nmbr
set Rslt to MultByStrings(Rslt, i)
end repeat
return Rslt
end FactorialByStrings
``````

Hi Nigel -

Thank you. Two questions: What is preforming the function of pad() to make the strings the same length? And when I ran

``````
set M2 to PowerByStrings(2, 1000)
repeat with i from 1 to length of M2
end repeat

``````

I get an error (Can’t get beginning of {}.) on the line: set item 1 of A1 to ((beginning of A1) + carry * 100000000) as text

…Mick

Druido -

Thank you. It’s almost 3x faster.

…Mick

The problem was in the chop handler.
Now that Nigel has edited his code, no need to waste space

Yvan KOENIG (VALLAURIS, France) mardi 14 janvier 2014 16:21:35

There’s no need to make the strings the same length. It just stops adding when it runs out of digit blocks and carries. But there is some padding of the addition results to make sure any internal leading zeros are preserved.

Sorry about that. I’ve now restored the original chop(). Thanks, Yvan!

Nigel, Yvan – Thanks. As my old man would say, much “more better.”

…Mick