valueDiff for arrays?

[Alex Tweedly]

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.