Re: Speed of applets vs. compiled scripts
Re: Speed of applets vs. compiled scripts
- Subject: Re: Speed of applets vs. compiled scripts
- From: email@hidden (Michael Sullivan)
- Date: Mon, 28 Jan 2002 15:21:53 -0500
- Organization: Society for the Incurably Pompous
>
At 12:09 PM -0500 1/28/02, email@hidden wrote:
>
You only have to try divisors up to sqrt(i), rather than i/2. As i gets
>
large, the savings are significant. (Specifically, you get an advantage
>
of sqrt(i)/2.)
>
The advantage of only calculating to the square root is huge. The changes
>
below are more modest, cutting the time roughly in half.
>
set t to (current date)
>
set pList to {2}
>
repeat with i from 3 to 10001 by 2
>
set tHowMany to count pList
>
set tStopVal to sqrt (i)
>
repeat with j from 1 to tHowMany
>
set tWhichPrime to item j of pList
>
if tWhichPrime > tStopVal then
>
set end of pList to i
>
exit repeat
>
end if
>
if i mod tWhichPrime = 0 then exit repeat
>
end repeat
>
end repeat
The advantage of generating composites instead (a la Sieve of
eratosthenes and similar algorithms) is even larger. In general The
sieve should be O(n) on number of integers tested. All testing
algorithms will be n * log(n) or worse. I'd post a handler, but Arthur
already beat me to it.
If speed is *really* important and you've got a huge set of primes to
worry about, there's a pretty triangulation algorithm I've got lying
around somewhere (not as Applescript though) that avoids almost all the
repetition involved in doing the sieve.
Basically it prunes the sieve with the knowledge that all prime factors
of X are less than sqrt(X). You batch the sieve recursively by
generating primes up to some fairly small number N, then multiply out
all the possibilities of the known primes up to N^2 (by triangulation
you can assure that you generate very few numbers outside of the N+1 to
N^2 range, but will generate every composite number within the range,
guaranteeing that any number not generated is prime.
I'm not sure it's enough of an improvement on Arthur's algorithm though
to make a noticeable difference except on very large lists, and the
implementation is a lot hairier.
Michael
--
Michael Sullivan
Business Card Express of CT Thermographers to the Trade
Cheshire, CT email@hidden