Project

General

Profile

Feature #5378 ยป prime.patch

h.shirosaki (Hiroshi Shirosaki), 10/01/2011 03:26 PM

View differences:

lib/prime.rb
316 316
    def rewind
317 317
      initialize
318 318
    end
319

  
320
    def each(&block)
321
      return self.dup unless block
322
      if @ubound
323
        EratosthenesSieve.instance.each(@ubound, &block)
324
      else
325
        loop do
326
          block.call(succ)
327
        end
328
      end
329
    end
319 330
    alias next succ
320 331
  end
321 332

  
......
427 438
    ENTRIES_PER_TABLE = 8
428 439
    NUMS_PER_TABLE = NUMS_PER_ENTRY * ENTRIES_PER_TABLE
429 440
    FILLED_ENTRY = (1 << NUMS_PER_ENTRY) - 1
441
    BITS_MASK = 0b00011111
442
    BITS_SHIFT = 1
443
    ENTRY_MASK = 0b11100000
444
    ENTRY_SHIFT = 5
445
    TABLE_SHIFT = 8
430 446

  
431 447
    def initialize # :nodoc:
432 448
      # bitmap for odd prime numbers less than 256.
......
437 453
      @tables = [[0xcb6e, 0x64b4, 0x129a, 0x816d, 0x4c32, 0x864a, 0x820d, 0x2196].freeze]
438 454
    end
439 455

  
456
    def each(ubound, &block)
457
      last_value = nil
458
      last_value = block.call(2) if ubound > 1
459
      ubound = (ubound-1).div(2)*2+1 # the biggist odd number less than or equal to ubound
460
      to_table_index, to_integer_index, to_bit_index = indices(ubound)
461
      extend_table until @tables.length > to_table_index
462

  
463
      for i in 0..to_table_index
464
        table_base = NUMS_PER_TABLE * i
465
        tables_i = @tables[i]
466
        end_integer_index = (i == to_table_index ? to_integer_index+1 : ENTRIES_PER_TABLE)
467
        for j in 0...end_integer_index
468
          tables_i_j = tables_i[j]
469
          unless tables_i_j.zero?
470
            integer_base = table_base + NUMS_PER_ENTRY * j
471
            end_bit_index = (i == to_table_index && j == to_integer_index ?
472
              to_bit_index+1 : BITS_PER_ENTRY)
473
            for k in 0...end_bit_index
474
              unless tables_i_j[k].zero?
475
                last_value = block.call(integer_base + 2*k+1)
476
              end
477
            end
478
          end
479
        end
480
      end
481
      last_value
482
    end
483

  
440 484
    # returns the least odd prime number which is greater than +n+.
441 485
    def next_to(n)
442 486
      n = (n-1).div(2)*2+3 # the next odd number to given n
......
462 506
      #   indices:            |-|    k  |  j  |     i
463 507
      # because of NUMS_PER_ENTRY, NUMS_PER_TABLE
464 508

  
465
      k = (n & 0b00011111) >> 1
466
      j = (n & 0b11100000) >> 5
467
      i = n >> 8
509
      k = (n & BITS_MASK) >> BITS_SHIFT
510
      j = (n & ENTRY_MASK) >> ENTRY_SHIFT
511
      i = n >> TABLE_SHIFT
468 512
      return i, j, k
469 513
    end
470 514

  
......
473 517
      ubound = lbound + NUMS_PER_TABLE
474 518
      new_table = [FILLED_ENTRY] * ENTRIES_PER_TABLE # which represents primarity in lbound...ubound
475 519
      (3..Integer(Math.sqrt(ubound))).step(2) do |p|
476
        i, j, k = indices(p)
520
        k = (p & BITS_MASK) >> BITS_SHIFT
521
        j = (p & ENTRY_MASK) >> ENTRY_SHIFT
522
        i = p >> TABLE_SHIFT
477 523
        next if @tables[i][j][k].zero?
478 524

  
479 525
        start = (lbound.div(p)+1)*p  # least multiple of p which is >= lbound
480 526
        start += p if start.even?
481 527
        (start...ubound).step(2*p) do |n|
482
          _, j, k = indices(n)
528
          k = (n & BITS_MASK) >> BITS_SHIFT
529
          j = (n & ENTRY_MASK) >> ENTRY_SHIFT
483 530
          new_table[j] &= FILLED_ENTRY^(1<<k)
484 531
        end
485 532
      end
test/test_prime.rb
171 171

  
172 172
    assert_not_include Prime.each(7*37).to_a, 7*37, "[ruby-dev:39465]"
173 173
  end
174

  
175
  def test_each_with_ubound
176
    primes = []
177
    value = Prime.each(541) do |p|
178
      primes << p
179
    end
180
    assert_equal PRIMES, primes
181
    assert_equal PRIMES, value
182
  end
183

  
184
  def test_each_inject_with_ubound
185
    assert_equal PRIMES, Prime.each(541).inject([]) {|a, p| a << p}
186
    assert_equal PRIMES[0, PRIMES.size-1], Prime.each(540).inject([]) {|a, p| a << p}
187
    assert_equal [], Prime.each(1).inject([]) {|a, p| a << p}
188
    assert_equal [2], Prime.each(2).inject([]) {|a, p| a << p}
189
    assert_equal [2, 3], Prime.each(3).inject([]) {|a, p| a << p}
190
  end
174 191
end