benchmark/bm_so_nsieve_bits.rb

   1 #!/usr/bin/ruby
   2 #
   3 # The Great Computer Language Shootout
   4 # http://shootout.alioth.debian.org/
   5 #
   6 # nsieve-bits in Ruby
   7 # Contributed by Glenn Parker, March 2005
   8
   9 CharExponent = 3
  10 BitsPerChar = 1 << CharExponent
  11 LowMask = BitsPerChar - 1
  12
  13 def sieve(m)
  14   items = "\xFF" * ((m / BitsPerChar) + 1)
  15   masks = ""
  16   BitsPerChar.times do |b|
  17     masks << (1 << b).chr
  18   end
  19
  20   count = 0
  21   pmax = m - 1
  22   2.step(pmax, 1) do |p|
  23     if items[p >> CharExponent][p & LowMask] == 1
  24       count += 1
  25       p.step(pmax, p) do |mult|
  26         a = mult >> CharExponent
  27         b = mult & LowMask
  28         items[a] -= masks[b] if items[a][b] != 0
  29       end
  30     end
  31   end
  32   count
  33 end
  34
  35 n = 9 # (ARGV[0] || 2).to_i
  36 n.step(n - 2, -1) do |exponent|
  37   break if exponent < 0
  38   m = 2 ** exponent * 10_000
  39   count = sieve(m)
  40   printf "Primes up to %8d %8d\n", m, count
  41 end
  42