diff options
author | yugui <yugui@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2010-01-30 12:49:21 +0000 |
---|---|---|
committer | yugui <yugui@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2010-01-30 12:49:21 +0000 |
commit | 3ac7927ea610c6c1c6e3fa86fc13751fe2e7cc64 (patch) | |
tree | 30b70b7f034c47bae7b6d7b5ad73a0d99adb90dc | |
parent | caa2bb47b35969918e67d3339441750255edb18c (diff) |
merges r25388 from trunk into ruby_1_9_1.
--
* test/test_prime.rb
(TestPrime#test_eratosthenes_works_fine_after_timeout):
test for [ruby-dev:39465].
* lib/prime.rb (Prime::EratosthenesSieve):
fixed [ruby-dev:39465].
suppressed memory reallocation.
constantified some magic numbers.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/branches/ruby_1_9_1@26491 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
-rw-r--r-- | ChangeLog | 11 | ||||
-rw-r--r-- | lib/prime.rb | 62 | ||||
-rw-r--r-- | test/test_prime.rb | 26 | ||||
-rw-r--r-- | version.h | 2 |
4 files changed, 81 insertions, 20 deletions
@@ -1,3 +1,14 @@ +Sun Oct 18 09:49:14 2009 Yuki Sonoda (Yugui) <yugui@yugui.jp> + + * test/test_prime.rb + (TestPrime#test_eratosthenes_works_fine_after_timeout): + test for [ruby-dev:39465]. + + * lib/prime.rb (Prime::EratosthenesSieve): + fixed [ruby-dev:39465]. + suppressed memory reallocation. + constantified some magic numbers. + Fri Oct 17 00:05:53 2009 wanabe <s.wanabe@gmail.com> * st.c (unpack_entries): save table->bins and never change the table diff --git a/lib/prime.rb b/lib/prime.rb index 8846b14174..d28302581c 100644 --- a/lib/prime.rb +++ b/lib/prime.rb @@ -408,44 +408,68 @@ class Prime class EratosthenesSieve include Singleton + BITS_PER_ENTRY = 16 # each entry is a set of 16-bits in a Fixnum + NUMS_PER_ENTRY = BITS_PER_ENTRY * 2 # twiced because even numbers are omitted + ENTRIES_PER_TABLE = 8 + NUMS_PER_TABLE = NUMS_PER_ENTRY * ENTRIES_PER_TABLE + FILLED_ENTRY = (1 << NUMS_PER_ENTRY) - 1 + def initialize # :nodoc: # bitmap for odd prime numbers less than 256. - # For an arbitrary odd number n, @table[i][j] is 1 when n is prime where i,j = n.divmod(32) . - @table = [0xcb6e, 0x64b4, 0x129a, 0x816d, 0x4c32, 0x864a, 0x820d, 0x2196] + # For an arbitrary odd number n, @tables[i][j][k] is + # * 1 if n is prime, + # * 0 if n is composite, + # where i,j,k = indices(n) + @tables = [[0xcb6e, 0x64b4, 0x129a, 0x816d, 0x4c32, 0x864a, 0x820d, 0x2196].freeze] end # returns the least odd prime number which is greater than +n+. def next_to(n) - n = (n-1).div(2)*2+3 # the next odd number of given n - i,j = n.divmod(32) + n = (n-1).div(2)*2+3 # the next odd number to given n + table_index, integer_index, bit_index = indices(n) loop do - extend_table until @table.length > i - if !@table[i].zero? - (j...32).step(2) do |k| - return 32*i+k if !@table[i][k.div(2)].zero? + extend_table until @tables.length > table_index + for j in integer_index...ENTRIES_PER_TABLE + if !@tables[table_index][j].zero? + for k in bit_index...BITS_PER_ENTRY + return NUMS_PER_TABLE*table_index + NUMS_PER_ENTRY*j + 2*k+1 if !@tables[table_index][j][k].zero? + end end + bit_index = 0 end - i += 1; j = 1 + table_index += 1; integer_index = 0 end end private + # for an odd number +n+, returns (i, j, k) such that @tables[i][j][k] represents primarity of the number + def indices(n) + # binary digits of n: |0|1|2|3|4|5|6|7|8|9|10|11|.... + # indices: |-| k | j | i + # because of NUMS_PER_ENTRY, NUMS_PER_TABLE + + k = (n & 0b00011111) >> 1 + j = (n & 0b11100000) >> 5 + i = n >> 8 + return i, j, k + end + def extend_table - orig_len = @table.length - new_len = [orig_len**2, orig_len+256].min - lbound = orig_len*32 - ubound = new_len*32 - @table.fill(0xFFFF, orig_len...new_len) + lbound = NUMS_PER_TABLE * @tables.length + ubound = lbound + NUMS_PER_TABLE + new_table = [FILLED_ENTRY] * ENTRIES_PER_TABLE # which represents primarity in lbound...ubound (3..Integer(Math.sqrt(ubound))).step(2) do |p| - i, j = p.divmod(32) - next if @table[i][j.div(2)].zero? + i, j, k = indices(p) + next if @tables[i][j][k].zero? - start = (lbound.div(2*p)*2+1)*p # odd multiple of p which is greater than or equal to lbound + start = (lbound.div(p)+1)*p # least multiple of p which is >= lbound + start += p if start.even? (start...ubound).step(2*p) do |n| - i, j = n.divmod(32) - @table[i] &= 0xFFFF ^ (1<<(j.div(2))) + _, j, k = indices(n) + new_table[j] &= FILLED_ENTRY^(1<<k) end end + @tables << new_table.freeze end end diff --git a/test/test_prime.rb b/test/test_prime.rb index d7c3bf5720..8317c2e369 100644 --- a/test/test_prime.rb +++ b/test/test_prime.rb @@ -1,6 +1,7 @@ require 'test/unit' require 'prime' require 'stringio' +require 'timeout' class TestPrime < Test::Unit::TestCase # The first 100 prime numbers @@ -143,4 +144,29 @@ class TestPrime < Test::Unit::TestCase assert !-4.prime? end end + + def test_eratosthenes_works_fine_after_timeout + sieve = Prime::EratosthenesSieve.instance + sieve.send(:initialize) + begin + # simulates that Timeout.timeout interrupts Prime::EratosthenesSieve#extend_table + def sieve.Integer(n) + n = super(n) + sleep 10 if /extend_table/ =~ caller.first + return n + end + + begin + Timeout.timeout(0.5) { Prime.each(7*37){} } + flunk("timeout expected") + rescue Timeout::Error + end + ensure + class << sieve + remove_method :Integer + end + end + + refute_includes Prime.each(7*37).to_a, 7*37, "[ruby-dev:39465]" + end end @@ -1,5 +1,5 @@ #define RUBY_VERSION "1.9.1" -#define RUBY_PATCHLEVEL 396 +#define RUBY_PATCHLEVEL 397 #define RUBY_VERSION_MAJOR 1 #define RUBY_VERSION_MINOR 9 #define RUBY_VERSION_TEENY 1 |