diff options
Diffstat (limited to 'benchmark/so_nsieve_bits.rb')
-rw-r--r-- | benchmark/so_nsieve_bits.rb | 43 |
1 files changed, 43 insertions, 0 deletions
diff --git a/benchmark/so_nsieve_bits.rb b/benchmark/so_nsieve_bits.rb new file mode 100644 index 0000000000..6f958ee44e --- /dev/null +++ b/benchmark/so_nsieve_bits.rb @@ -0,0 +1,43 @@ +#!/usr/bin/ruby +#coding: us-ascii +# +# 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 + |