1 files changed, 43 insertions, 0 deletions
diff --git a/benchmark/bm_so_nsieve_bits.rb b/benchmark/bm_so_nsieve_bits.rb
new file mode 100644
index 0000000000..6f958ee44e
--- /dev/null
+++ b/benchmark/bm_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
+