Re: How to make this faster?

Path	csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!nuzba.szn.dk!pnx.dk!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From	Robert Klemme <shortcutter@googlemail.com>
Newsgroups	comp.lang.ruby
Subject	Re: How to make this faster?
Date	Fri, 16 Nov 2012 19:52:09 +0100
Lines	64
Message-ID	<agngaqF27gsU1@mid.individual.net> (permalink)
References	<d6bb66f9-5360-4720-b31f-76d0a0f9293c@googlegroups.com>
Mime-Version	1.0
Content-Type	text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding	7bit
X-Trace	individual.net cwCxUfD55ekGyVWxXgweWwn8j6yTZxyk6h44EdTHw2XZEkoV/UGVNMztNB/Qoagd0=
Cancel-Lock	sha1:PO+sJ8Ds2NTU/luzsvgna+SSk6Y=
User-Agent	Mozilla/5.0 (Windows NT 6.0; WOW64; rv:16.0) Gecko/20121026 Thunderbird/16.0.2
In-Reply-To	<d6bb66f9-5360-4720-b31f-76d0a0f9293c@googlegroups.com>
Xref	csiph.com comp.lang.ruby:6675

Show key headers only | View raw

On 13.11.2012 22:07, jzakiya@gmail.com wrote:
> I have this code snippet below:
>
>        p=11
>        while p <= sqrtN
>          return false if
>          n%(p)    == 0 or n%(p+2)  ==0 or n%(p+6)  == 0 or n%(p+8)  ==0 or
>          n%(p+12) == 0 or n%(p+18) ==0 or n%(p+20) == 0 or n%(p+26) ==0 or
>          n%(p+30) == 0 or n%(p+32) ==0 or n%(p+36) == 0 or n%(p+42) ==0 or
>          n%(p+48) == 0 or n%(p+50) ==0 or n%(p+56) == 0 or n%(p+60) ==0 or
>          n%(p+62) == 0 or n%(p+68) ==0 or n%(p+72) == 0 or n%(p+78) ==0 or
>          n%(p+86) == 0 or n%(p+90) ==0 or n%(p+92) == 0 or n%(p+96) ==0 or
>          n%(p+98) == 0 or n%(p+102)==0 or n%(p+110)== 0 or n%(p+116)==0 or
>          n%(p+120)== 0 or n%(p+126)==0 or n%(p+128)== 0 or n%(p+132)==0 or
>          n%(p+138)== 0 or n%(p+140)==0 or n%(p+146)== 0 or n%(p+152)==0 or
>          n%(p+156)== 0 or n%(p+158)==0 or n%(p+162)== 0 or n%(p+168)==0 or
>          n%(p+170)== 0 or n%(p+176)==0 or n%(p+180)== 0 or n%(p+182)==0 or
>          n%(p+186)== 0 or n%(p+188)==0 or n%(p+198)== 0 or n%(p+200)==0
>          p += mod
>        end
>        return true
>
> that I can replace with this:
>
>       modk,r=0,1;  p=11
>       while (p+modk) <= sqrtN
>         return false if ( s=false; res[1..-1].each {|r| s ||= n%(r+modk)==0}; s)
>         modk +=mod
>       end
>       return true
>
> The second snippet is much shorter than the first, but slower.
>
> Is there a way to make the line below faster?
>
> return false if ( s=false; res[1..-1].each {|r| s ||= n%(r+modk)==0}; s)
>
> What I want to do is take an element from res and do -- n%(r+modk)==0.
> If it becomes true I want to return false (immediately if possible). If it's always false for every array element I go through the loop again until the end
> condition is met.

Here's another approach for your benchmarking:

OFFSETS = [0, 2, 6, 8, ...]

...

p = 11

while p <= sqrtN
   return false if OFFSETS.any? {|off| n % (p + off) == 0}
   p += mod
end

return true

Cheers

	robert


-- 
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/

Back to comp.lang.ruby | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

How to make this faster? jzakiya@gmail.com - 2012-11-13 13:07 -0800
  Re: How to make this faster? Robert Klemme <shortcutter@googlemail.com> - 2012-11-16 19:52 +0100

csiph-web