Re: Sieve of Eratosthenes performance question

[Rici Lake <lua@...>]

On 6-Jun-07, at 1:27 PM, Shoaib Meenai wrote:

> On 6/6/07, Philippe Lhoste <PhiLho@gmx.net> wrote:
> > ... I believe the difference is because I made 'composite' an array 
> > with
> > contiguous numerical indexes, with optimized access in Lua 5.1 (direct
> > offset computing), while in the previous code, Lua probably has to 
> > make
> > more complex tests (hashing the index?) to see if the slot is empty 
> > ...
>
> Might be a stupid question, but would the optimization apply even if
> the first index was, say, 1296?

Probably not. The optimization requires (roughly) that the array uses 
more
than half of the indices in the range [1, 2^k] for some integer k (and
applies to the indices in that range: anything outside of the range is
stored in the hash part of the table).