From: Yusuke Endoh <mame@...>
Date: 2011-10-03T23:12:20+09:00
Subject: [ruby-core:39872] [Ruby 1.9 - Feature #5378][Assigned] Prime.each is slow


Issue #5378 has been updated by Yusuke Endoh.

Status changed from Open to Assigned
Assignee set to Yuki Sonoda

Hello,

Just slowness is not a bug unless it is a regression, I think.
So I moved this ticket to the feature tracker.


I believe that there is no perfect algorithm to enumerate
primes.  Any algorithm has drawback and advantage.  Note that
speed is not the single important thing.  I could be wrong,
but I guess that prime.rb does not priotize speed (especially,
linear-order cost), but high-abstract design.


Even in terms of speed, my version is about 2 times faster
than Peter's, though it uses extra memory.  So, there are
trade-offs.


  def primes_up_to_yusuke(n)
    primes = [2]
    n /= 2
    prime_table = [true] * n
    i = 1
    while i < n
      if prime_table[i]
        primes << j = i * 2 + 1
        k = i + j
        while k < n
          prime_table[k] = false
          k += j
        end
      end
      i += 1
    end
    primes
  end


                  user     system      total        real
primes_up_to_mike  1.720000   0.010000   1.730000 (  1.726733)
primes_up_to_peter  0.780000   0.020000   0.800000 (  0.795156)
primes_up_to_yusuke  0.410000   0.000000   0.410000 (  0.419209)
Prime.each    4.760000   0.010000   4.770000 (  4.765654)


I think every prime-aholic should implement their own favorite
algorithm by himself :-)

-- 
Yusuke Endoh <mame@tsg.ne.jp>
----------------------------------------
Feature #5378: Prime.each is slow
http://redmine.ruby-lang.org/issues/5378

Author: Mike Conigliaro
Status: Assigned
Priority: Normal
Assignee: Yuki Sonoda
Category: 
Target version: 


See discussion here: https://gist.github.com/1246868


require 'benchmark'
require 'prime'

def primes_up_to(n)
  s = [nil, nil] + (2..n).to_a
  (2..(n ** 0.5).to_i).reject { |i| s[i].nil? }.each do |i|
    (i ** 2).step(n, i) { |j| s[j] = nil }
  end
  s.compact
end

Benchmark.bm(12) do |x|
  x.report('primes_up_to') { primes_up_to(2000000).inject(0) { |memo,obj| memo + obj } }
  x.report('Prime.each') { Prime.each(2000000).inject(0) { |memo,obj| memo + obj } }
end


$ ruby -v
ruby 1.9.2p290 (2011-07-09 revision 32553) [x86_64-darwin10.8.0]
$ ruby lol.rb 
                  user     system      total        real
primes_up_to  1.470000   0.020000   1.490000 (  1.491340)
Prime.each    7.820000   0.010000   7.830000 (  7.820969)


-- 
http://redmine.ruby-lang.org