Re: Sieve of Eratosthenes performance question

["Shoaib Meenai" <shobiz91@...>]

On 6/6/07, Rici Lake <lua@ricilake.net> wrote:
> 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).

But if I used, for example, indices 1296 to 65536 (which is 2^16),
would the optimization apply? Or does k have some preset value which
varies from system to system?