summaryrefslogtreecommitdiff
path: root/benchmark/so_nsieve_bits.yml
diff options
context:
space:
mode:
Diffstat (limited to 'benchmark/so_nsieve_bits.yml')
-rw-r--r--benchmark/so_nsieve_bits.yml46
1 files changed, 46 insertions, 0 deletions
diff --git a/benchmark/so_nsieve_bits.yml b/benchmark/so_nsieve_bits.yml
new file mode 100644
index 0000000..08b47f5
--- /dev/null
+++ b/benchmark/so_nsieve_bits.yml
@@ -0,0 +1,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