benchmark/so_nsieve_bits.yml


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

prelude: |
  #!/usr/bin/ruby
  #coding: us-ascii
benchmark:
  so_nsieve_bits: |
    #
    # The Great Computer Language Shootout
    # http://shootout.alioth.debian.org/
    #
    # nsieve-bits in Ruby
    # Contributed by Glenn Parker, March 2005

    CharExponent = 3
    BitsPerChar = 1 << CharExponent
    LowMask = BitsPerChar - 1

    def sieve(m)
      items = "\xFF" * ((m / BitsPerChar) + 1)
      masks = ""
      BitsPerChar.times do |b|
        masks << (1 << b).chr
      end

      count = 0
      pmax = m - 1
      2.step(pmax, 1) do |p|
        if items[p >> CharExponent][p & LowMask] == 1
          count += 1
          p.step(pmax, p) do |mult|
    	a = mult >> CharExponent
    	b = mult & LowMask
    	items[a] -= masks[b] if items[a][b] != 0
          end
        end
      end
      count
    end

    n = 9 # (ARGV[0] || 2).to_i
    n.step(n - 2, -1) do |exponent|
      break if exponent < 0
      m = 2 ** exponent * 10_000
      count = sieve(m)
      printf "Primes up to %8d %8d\n", m, count
    end
loop_count: 1