lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


On 2011-Jan-21 (Fri) at 18:08 (+0100), Valerio Schiavoni wrote:

>> hello Joseph
>> 
>> On Fri, Jan 21, 2011 at 12:04 PM, Joseph Manning <manning@cs.ucc.ie> wrote:
>> 
>> >>>         for kk = k*2, max, k do
>> 
>> > faster :   for kk = k*k, max, k do
>> 
>> does it mean k*k is faster than k*2 ?

No, sorry, I guess my initial message may have been too terse.

I simply meant to convey that the overall Sieve of Eratosthenes program
will be faster if the above loop starts at  k*k  rather than at  k*2 ,
since it will have fewer iterations to go through.

And it's quite safe to start with  k*k  as being the first multiple of k
to be eliminated, since smaller multiples of the form  k*i ( i < k )
will already have been eliminated, since they are multiples of i.

Perhaps in the context of benchmarking, the whole point is moot anyway,
as a slower algorithm can serve as a better benchmark than a faster one,
in the sense of better highlighting the difference in run-time speed
between different systems.

-- Joseph

------------------------------------------------------------------------
Joseph Manning / Computer Science / UCC Cork Ireland / manning@cs.ucc.ie
------------------------------------------------------------------------