Using Applescript to handle each digit of VERY big numbers

Mick536 · January 12, 2014, 6:46pm

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 : {}

on pad(N, X)
	set padding to {}
	repeat with i from 1 to N
		set the end of padding to X
	end repeat
	return padding as text
end pad

on AddByStrings(Adder1, Adder2)
	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
		set Adder2 to pad(L1 - L2, "0") & Adder2
	else if L2 > L1 then
		set Adder1 to pad(L2 - L1, "0") & Adder1
	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
	return Answer as text
end AddByStrings

on MultByStrings(Multiplicand, Multiplier)
	set Rslt to Multiplicand
	repeat with i from 1 to Multiplier - 1
		set Rslt to AddByStrings(Rslt, Multiplicand)
	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


return AddByStrings("69011111111111111111111", "1234521")

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 Answer to 0
set M2 to PowerByStrings(2, 1000)
repeat with i from 1 to length of M2
	set Answer to Answer + (text i of M2)
end repeat
return Answer

or


set expt to 1000
set M1 to "2"
set Answer to 0
repeat with i from 2 to expt
	set M2 to AddByStrings(M1, M1)
	set M1 to M2
end repeat
repeat with i from 1 to length of M2
	set Answer to Answer + (text i of M2)
end repeat
return Answer

or


set M2 to "2"
set Answer to 0
repeat with i from 2 to 1000
	set M2 to MultByStrings(M2, 2)
end repeat
repeat with i from 1 to length of M2
	set Answer to Answer + (text i of M2)
end repeat
return Answer

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

Adam_Bell · January 12, 2014, 8:16pm

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.

Yvan_Koenig · January 12, 2014, 8:32pm

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

Mick536 · January 12, 2014, 11:24pm

Hi Adam -

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

Yvan_Koenig · January 13, 2014, 9:15am

Oops

One more time I read too fast.

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

druido · January 13, 2014, 7:10pm

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.

Nigel_Garvey · January 13, 2014, 8:36pm

Hi.

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.
When coercing lists to text, AppleScript’s text item delimiters should be explicitly set to “” or to {“”} for safety.
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

on AddByStrings(Adder1, Adder2)
	set A1 to chop(Adder1)
	set A2 to chop(Adder2)
	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
end AddByStrings

on MultByStrings(Multiplicand, Multiplier)
	set Rslt to Multiplicand
	repeat with i from 1 to Multiplier - 1
		set Rslt to AddByStrings(Rslt, Multiplicand)
	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

Edit: Tidier code in AddByStrings().

Mick536 · January 14, 2014, 2:43pm

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) 
set Answer to 0
repeat with i from 1 to length of M2
	set Answer to Answer + (text i of M2)
end repeat
return Answer

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

Mick536 · January 14, 2014, 2:49pm

Druido -

Thank you. It’s almost 3x faster.

…Mick

Yvan_Koenig · January 14, 2014, 3:21pm

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

Nigel_Garvey · January 14, 2014, 3:49pm

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.

And when I ran
set M2 to PowerByStrings(2, 1000) 
set Answer to 0
repeat with i from 1 to length of M2
	set Answer to Answer + (text i of M2)
end repeat
return Answer
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

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

Mick536 · January 14, 2014, 4:41pm

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

…Mick