Nice improvement !
And I like the variable names much more ... though it could be argued
that "tYes", should be called"tMayYetBeAPrime" :-)
I now get this version consistently running in 25% of the original time.
There is another version which runs about twice as fast - i.e. 14% of
the original - but I'm not sure it is quite within the spirit of this
comparison.
This should be a comparison of the performance of "the same" algorithm
in a variety of scripting languages. It seems wrong to speed up our LC
implementation by tweaking the algorithm.
If our purpose was simply to improve the speed of finding primes, that
would be different.
So for anyone who wants to find primes faster - here revised code that
does so, though I doubt if it tells us anything about the relative
performance of LC.
The "pure" version of the Sieve would have crossed all multiples of
every prime, but the original code only needs to cross-off those
multiples of 3 and above - i.e the 'pure' inner loop would be
repeat with i = 2 to tMroot
rather than
repeat with i = 3 to tMroot step 2
The original code is an improvement over the 'pure' version by taking
advantage of the knowledge that all even numbers (>2) cannot be
prime.You can do (part of) that optimization for all primes up to
(small) 'm' rather than just for '2'. Pre-calculate the pattern for
1...M (where big M is the product of all primes <= small m), and then
initialize the sieve table with that pattern repeated as often as
needed. Then you can go through the sieve crossing-off only for primes >
'm'. This code uses m=5 (i.e. M=2*3*5=30).
function get_primes pN
local tMroot, tPrimes, tIsItPrime, tYes, tNo
put numtobyte(66) into tYes
put numtobyte(65) into tNo
if pN < 2 then return empty
if pN = 2 then return 2
repeat with i = 1 to 30
put tNo into byte i of tIsItPrime
end repeat
repeat for each item L in "1,7,11,13,17,19,23,29"
put tYes into byte L of tIsItPrime
end repeat
local t30
put byte 1 to 30 of tIsItPrime into t30
put t30 into tIsItPrime
repeat pN div 30 times
put t30 after tIsItPrime
end repeat
put 2 &CR & 3 & CR & 5 into tPrimes
put trunc(sqrt(pN)) - 1 into tMroot
repeat with i = 7 to tMroot step 2
if byte i of tIsItPrime is tNo then next repeat
put cr & i after tPrimes
repeat with j = i^2 to pN step i
put tNo into byte j of tIsItPrime
end repeat
end repeat
repeat with i = tMroot + (tMroot + 1) mod 2 to pN - 1 step 2
if byte i of tIsItPrime is tYes then put cr & i after tPrimes
end repeat
return tPrimes
end get_primes
and that runs in just over half the time.
Alex.
_______________________________________________
use-livecode mailing list
use-livecode@lists.runrev.com
Please visit this url to subscribe, unsubscribe and manage your subscription
preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
