Article

Reading prime.rb - The built-in support for prime numbers in Ruby

In one of our coding katas one of the pairs asked the question how to find out if a number is prime. I knew a simple algorithm, because I solved the first few challenges on Project Euler - but I did not know that Ruby has prime support out of the box.

This week I want to share my notes on my reading of prime.rb. Part of Ruby 1.9.3 ...

Some tweaks to Integer

class Integer
  def Integer.from_prime_division(pd)
    Prime.int_from_prime_division(pd)
  end

  def prime_division(generator = Prime::Generator23.new)
    Prime.prime_division(self, generator)
  end

  def prime?
    Prime.prime?(self)
  end

  def Integer.each_prime(ubound, &block) # :yields: prime
    Prime.each(ubound, &block)
  end
end

If you require 'prime' you get some extra functions on integers.

You can check if a number is prime, can generate all prime numbers up to a certain upper bound or execute a prime factor decomposition.

Examples

21.prime? #=> false

100.prime_division # => [[2, 2], [5, 2]]

Integer.each_prime(20) { |prime| puts prime } # Prints all primes up to 20

Integer.from_prime_division(21.prime_division) # Reverses a prime_division

The prime division returns nice pairs - the prime and how often it's a divisor of the number.

For example: 4 is 2 * 2 and would return [[2,2]], whereas 12 is 2 * 2 * 3 and returns [[2, 2], [3, 1]].

The generators

Prime.rb contains several different generators for prime numbers.

They inherit from the same abstract base class.

class PseudoPrimeGenerator
  include Enumerable

  def initialize(ubound = nil)
    @ubound = ubound
  end

  def upper_bound=(ubound)
    @ubound = ubound
  end
  def upper_bound
    @ubound
  end

  def succ
    raise NotImplementedError, "need to define `succ'"
  end

  def next
    raise NotImplementedError, "need to define `next'"
  end

  def rewind
    raise NotImplementedError, "need to define `rewind'"
  end

  def each(&block)
    return self.dup unless block
    if @ubound
      last_value = nil
      loop do
        prime = succ
        break last_value if prime > @ubound
        last_value = block.call(prime)
      end
    else
      loop do
        block.call(succ)
      end
    end
  end

  alias with_index each_with_index

  def with_object(obj)
    return enum_for(:with_object) unless block_given?
    each do |prime|
      yield prime, obj
    end
  end
end

Every generator has an upper bound and has to be able to supply the next prime number or start over from scratch.

Interesting is also the each method that stops executing if the upper bound is reached. It's kind of obvious after you have read it - but it never occurred to me that you can (or might want to) modify each in this way if necessary - but for primes it makes sense of course, unless you are really patient...

There are 3 generators that are implemented in prime.rb:

EratosthenesGenerator

class EratosthenesGenerator < PseudoPrimeGenerator
  def initialize
    @last_prime = nil
    super
  end

  def succ
    @last_prime = @last_prime ? EratosthenesSieve.instance.next_to(@last_prime) : 2
  end

  def rewind
    initialize
  end
  alias next succ
end

This generator is based on the Sieve of Eratosthenes.

If the first prime number is found you start to cross out all its multiples and repeat this process for the next prime etc. (see below). Of course this only works with an upper bound - otherwise you would cross out numbers for a very long time...

A grid of numbers from 1 to 120 with prime numbers highlighted in gray.
Picture created by SKopp (License: CC BY-SA 3.0)

Sieving numbers is faster than pure brute-forcing but you have to keep track of the numbers that are not prime, which is memory-intensive.

This generator is also the default generator in prime.rb if you want to use Integer.each_prime() to iterate over all primes.

Trial Division

class TrialDivisionGenerator<PseudoPrimeGenerator
  def initialize
    @index = -1
    super
  end

  def succ
    TrialDivision.instance[@index += 1]
  end
  def rewind
    initialize
  end
  alias next succ
end

The TrialDivisionGenerator is a brute force generator. It divides the integer by all integers smaller than its square root. The TrialDivision class itself has some more tricks in it to make it faster - but that's pretty much it.

Interesting is how it's used. Have a close look at the succ function. It calls the trial division like this:

TrialDivision.instance[prime_number]

TrialDivision calculates all prime numbers up to this index, saves them in its @primes variable and then returns the result.

def [](index)
  while index >= @primes.length
    #calculate the number and push it to primes
  end
  return @primes[index]
end

To be honest I was quite surprised - and I am not sure if I like that syntax. It's not really clear what this will do from the outside.

Another aspect is that the next time you iterate over a set of primes they are cached already. On the other hand this means that the highest prime you can calculate is limited by the amount of your RAM and not by the time you invest to brute-force. (I guess that is no big concern in most cases, since brute forcing is so slow after a few minutes that it makes no big difference)

The TrialDivision generator is not used in the rest of the file.

Generator 23

This should be the fastest generator of them all - it also does not consume memory. But - it's a fake... You can try to figure out why: If you can't, you can read the original file - it's commented in there of course ;)

class Generator23 < PseudoPrimeGenerator
  def initialize
    @prime = 1
    @step = nil
    super
  end

  def succ
    loop do
      if (@step)
        @prime += @step
        @step = 6 - @step
      else
        case @prime
          when 1; @prime = 2
          when 2; @prime = 3
          when 3; @prime = 5; @step = 2
        end
      end
      return @prime
    end
  end
  alias next succ
  def rewind
    initialize
  end
end

This generator is used to do the prime division. And to check if a number is prime. It's just a speed improvement - you will see why in a second.

Putting it all together

class Prime
  include Enumerable
  @the_instance = Prime.new

  def initialize
    @generator = EratosthenesGenerator.new
    warn "Prime::new is obsolete. use Prime::instance or class methods of Prime."
  end

  class << self
    extend Forwardable
    include Enumerable
    # Returns the default instance of Prime.
    def instance; @the_instance end

    def method_added(method) # :nodoc:
      (class<< self;self;end).def_delegator :instance, method
    end
  end

  def each(ubound = nil, generator = EratosthenesGenerator.new, &block)
    generator.upper_bound = ubound
    generator.each(&block)
  end

  def prime?(value, generator = Prime::Generator23.new)
    value = -value if value < 0
    return false if value < 2
    for num in generator
      q,r = value.divmod num
      return true if q < num
      return false if r == 0
    end
  end

  def int_from_prime_division(pd)
    pd.inject(1){|value, (prime, index)|
      value *= prime**index
    }
  end

  def prime_division(value, generator= Prime::Generator23.new)
    raise ZeroDivisionError if value == 0
    if value < 0
      value = -value
      pv = [[-1, 1]]
    else
      pv = []
    end
    for prime in generator
      count = 0
      while (value1, mod = value.divmod(prime)
             mod) == 0
        value = value1
        count += 1
      end
      if count != 0
        pv.push [prime, count]
      end
      break if value1 <= prime
    end
    if value > 1
      pv.push [value, 1]
    end
    return pv
  end
end

The Prime class puts this all together. As you can see the each() method employs the EratosthenesGenerator - it has to deliver proper primes and sieving is faster than mere brute force.

The prime? method on the other hand uses Generator23 - because it does trial division from the smallest number up. Even if some of the numbers of the Generator are no primes, the result will not change - in fact you could even use all natural numbers...

The prime_division function also uses trial division from the lowest generated number up. This way a bigger number will not divide without a remainder again - unless it's a real prime and a prime factor.

So using Generator23 - that only returns numbers that are not divisible by 2 or 3 - is a speed improvement.

Bottom line

Some questions remain after reading this file:

  • Why is there a TrialDivision generator that is not really in use?
  • Do tests exist?

I like how this file reads. It has functions that are quite short and focused. It's really awesome that Ruby has some built-in tools for playing around with prime numbers.

This file seems to be a good foundation to build other prime number generators upon. For example the Sieve of Atkin comes to mind (even to me as a prime number noob ;)...

As always: I invite you to read the code - especially if you are interested in prime numbers.

If you liked this, have a look at my notes on Reading set.rb as well.

  • ruby
  • reading-code

Replies

To reply from the fediverse, follow @robert@rocu.de or look up the address of this post from your account.