Re: n! script
Re: n! script
- Subject: Re: n! script
- From: Olof Hellman <email@hidden>
- Date: Sat, 13 Nov 2004 21:37:54 -0800
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
--makeBigNum converts an integer such as 425 into a list { 5, 2 , 4}
-- the first number is the ones place, the second number is the tens
place, etc.
-- note that 425 could also be expressed as { 15, 21, 2} - we'll
take adavantage of that later
to makeBigNum(n)
set bigNum to {}
repeat while n > 0
set lastDigit to (n mod 10)
set bigNum to bigNum & (lastDigit as integer)
set n to (n - lastDigit) / 10
end repeat
return (bigNum)
end makeBigNum
--makeEmptyBigNum just starts us out with a list of zeros n items long
-- this is used as a starter value when doing the product
to makeEmptyBigNum(n)
set C to {}
repeat n times
set C to C & 0
end repeat
return C
end makeEmptyBigNum
-- trimBigNum gets rid of zeros in higher order places
-- it is important to do this often so that we don't end up doing a lot
of multiply by zeros
to trimBigNum(bigNum)
set lastDigit to count bigNum
repeat while (lastDigit > 1) and item lastDigit of bigNum is 0
set lastDigit to lastDigit - 1
end repeat
set bigNum to items 1 thru lastDigit of bigNum
return (bigNum)
end trimBigNum
-- flattenBigNum turns the number 42 expressed as bigNum { 12, 3 }
-- into the bigNum { 2, 4 }
-- this means that as we are doing the multiplication, we don't worry
about carrying over until the end
-- we use recursion, so that we only ever care about carrying over one
place at a time
-- warning to anyone who might use this routine for something else :
this routine doesn't handle the case of negative numbers
to flattenBigNum(bigNum)
set didCarry to false
repeat with bigNumIndex from 1 to count bigNum
set thisDigit to item bigNumIndex of bigNum
if (thisDigit > 9) then
set remainder to thisDigit mod 10
if ((count bigNum) < bigNumIndex) then
set bigNum to bigNum & 0
end if
set item (bigNumIndex + 1) of bigNum to (item (bigNumIndex + 1) of
bigNum) + ((thisDigit - remainder) div 10)
set item (bigNumIndex) of bigNum to remainder
set didCarry to true
end if
end repeat
if (didCarry) then
set bigNum to flattenBigNum(bigNum)
end if
set bigNum to trimBigNum(bigNum)
return (bigNum)
end flattenBigNum
--BigProd goes through and does the simple multiplication digit by
digit and then flattens
to BigProd(a, b)
set bigNum to makeEmptyBigNum((count a) + (count b))
repeat with indexInA from 1 to count a
repeat with indexInB from 1 to count b
set indexInC to indexInA + indexInB - 1
set item indexInC of bigNum to (item indexInC of bigNum) + (item
indexInB of b) * (item indexInA of a)
end repeat
end repeat
set bigNum to flattenBigNum(bigNum)
return (bigNum)
end BigProd
-- for output, we'll need a string, because we can't convert to an
integer
to getStringFromBigNum(bigNum)
set bigNum to flattenBigNum(bigNum)
set bigStr to ""
repeat with a from 1 to count bigNum
set bigStr to bigStr & ((item -a of bigNum) as string)
end repeat
return bigStr
end getStringFromBigNum
to bigFactorial(a)
set bn to makeBigNum(1)
repeat with n from 1 to a
set bf to makeBigNum(n)
set bn to BigProd(bn, bf)
end repeat
return (getStringFromBigNum(bn))
end bigFactorial
bigFactorial(100)
_______________________________________________
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