Re: n! script
Re: n! script
- Subject: Re: n! script
- From: Barry Wainwright <email@hidden>
- Date: Mon, 15 Nov 2004 10:32:15 +0000
On 14/11/04 5:37 am, "Olof Hellman" <email@hidden> wrote:
> Here's a script which seems to be almost twice as fast as Martin's at
> doing the factorial ( which is in turn way faster than Brian's for
> large numbers ). BigFactorial (100) takes about 5 seconds on my G4
> 1.25 GHz machine. BigFactorial (200) takes less than a minute. I think
> it is a little faster because it avoids doing a lot of string to
> integer conversions, and does less work when carrying, accumulating
> all the carries into one operation.
>
> Rather than working on a string, integers are converted to lists of
> integers, item 1 for the ones place, item 2 for the tens place etc. It
> ought to be a little easier to follow, and the technique is better
> extended to other bigNum operations, not just multiplication.
>
> Enjoy.
>
> - Olof
And here's another...
100! Takes less than a second, 200! Under 5 seconds.
You all make the big mistake of working with single digits. Applescript can
quite happily work with 9999*9999, so why not use much bigger chunks?
I haven't made any attempt to speed up the script beyond using 4 digit
chunks. I have made use of div and mod which are terribly slow and also
several loops where I am sure there are better ways. This iteration I was
just concentrating on the arithmetic.
set t1 to current date
set myAnswer to "1"
repeat with x from 1 to 200
set myAnswer to longMultiply(myAnswer, x as text)
end repeat
set t2 to current date
return {myAnswer, t2 - t1}
on longMultiply(firstnumber, secondNumber)
-- parse firstNumber to list
set number1 to {}
repeat until (count firstnumber) < 5
copy (text -1 thru -4 of firstnumber) as integer to beginning of
number1
set firstnumber to text 1 thru -5 of firstnumber
end repeat
copy firstnumber as integer to beginning of number1
-- parse secondNumber to list
set number2 to {}
repeat until (count secondNumber) < 5
copy (text -1 thru -4 of secondNumber) as integer to beginning of
number2
set secondNumber to text 1 thru -5 of secondNumber
end repeat
copy secondNumber as integer to beginning of number2
-- start the multiplication
-- set up theAnswer
set theAnswer to {}
set blockCount to (count number1) + (count number2)
repeat blockCount times
copy 0 to end of theAnswer
end repeat
-- multiply the blocks
repeat with x from 1 to (count number1)
repeat with y from 1 to (count number2)
set partAnswer to (item -x of number1) * (item -y of number2)
set item -(x + y - 1) of theAnswer to (item -(x + y - 1) of
theAnswer) + (partAnswer mod 10000)
set item -(x + y) of theAnswer to (item -(x + y) of theAnswer) +
(partAnswer div 10000)
end repeat
end repeat
-- convert theanswer back to string
set leadingZero to true
repeat with anItem in theAnswer
if anItem contains 0 and leadingZero is true then
set contents of anItem to ""
else
if leadingZero is true then
set contents of anItem to anItem as text
else
set contents of anItem to text -4 thru -1 of ("0000" &
(contents of anItem as text))
end if
set leadingZero to false
end if
end repeat
return theAnswer as text
end longMultiply
--
Barry
_______________________________________________
Do not post admin requests to the list. They will be ignored.
Applescript-users mailing list (email@hidden)
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden