Rocu.de

Love, caffeine and omlette

Month: October 2012

Reading prime.rb - The build 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 read 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]]

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

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

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

For example:
4 = 2 * 2 => [[2,2]]
12 = 2 * 2 * 3 => [[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.

Intersting is also the each method, that stops executing if the upper
bound is reached. Its kind of obvious after you have read it - but it
never occured 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..

/images/uploads/sieve_of_eratosthenes_animation.gif
Picture created by Skoop (License: CC BY-SA 3.0)

Sieving numbers is faster than pure brute-forcing but you have to keep track of the number 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 through all integers smaller to its square root. The TrialDivision class itself has some more tricks in it, to make it faster - but thats pretty much it.

Interesting is how its used. Have a close look at the succ function. It calls the trial divsion like this:

TrialDivision.instance[prime_number]

TrialDivision calcuates all prime numbesr 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 supprised - and I am not sure, if I like that syntax. Its 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 of 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 is should be the fastest generator of them all - it also does not consume memory. But - its 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. Its 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 delive proper primes and sieving is faster, then 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 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 rest again - unless its 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 Atkins 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.

Reading Set.rb - tipps for working with Ruby sets.

I like to read code. Often I take notes and it's a shame that I did never share them. But it's never to late to start.

So here are some notes on Ruby's set.rb. I hope you in turn share an interesting read with the world 😉

How to initialize a set

def initialize(enum = nil, &block)  
  @hash ||= Hash.new

  enum.nil? and return

  if block
    do_with_enum(enum) { |o| add(block[o]) }
  else
    merge(enum)
  end
end  

Ok much to notice here:

  • A Set uses a hash internally to avoid duplicates
  • Per default the merge method will just add() to the hash
  • Interestingly enough you can pass a block to prepare the data

Some examples what this means:

Set.new
 => #<Set: {}>

 Set.new([1,2,2,3])
 => #<Set: {1, 2, 3}>

 Set.new(["ape", "APE", "aPe"]) { |val| val.downcase  }
 #<Set: {"ape"}>

A second possibility is hidden at the bottom of the file:

module Enumerable  
  def to_set(klass = Set, *args, &block)
    klass.new(self, *args, &block)
  end
end  

Some examples:

%w{hello, hello, you}.to_set
=> #<Set: {"hello,", "you"}>

 %w{hello, hello, world, "!"}.to_set {|val| val.upcase }
 => #<Set: {"HELLO,", "WORLD,", ""!""}>

Here is a third way:

def self.[](*ary)  
  new(ary)
end  

This is pretty nice trick. It produces a nice shortcut to create a set.

Set[1,2,3,4]
#<Set: {1, 2, 3, 4}>

Set arithmetic in set.rb

A nice feature of sets is, that they support set arithmetic. The implementation is pretty straightforward, this is one of the instances where Ruby's syntax really shines 🙂

  # given enumerable object.
  def |(enum)
    dup.merge(enum)
  end
  alias + |             ##
  alias union |         ##

  # Returns a new set built by duplicating the set, removing every
  # element that appears in the given enumerable object.
  def -(enum)
    dup.subtract(enum)
  end
  alias difference -    ##

  # Returns a new set containing elements common to the set and the
  # given enumerable object.
  def &(enum)
    n = self.class.new
    do_with_enum(enum) { |o| n.add(o) if include?(o) }
    n
  end
  alias intersection &  ##

  # Returns a new set containing elements exclusive between the set
  # and the given enumerable object.  (set ^ enum) is equivalent to
  # ((set | enum) - (set & enum)).
  def ^(enum)
    n = Set.new(enum)
    each { |o| if n.include?(o) then n.delete(o) else n.add(o) end }
    n
  end

Some examples:

Merging

a = Set["a", "b", "c"]
 => #<Set: {"a", "b", "c"}>

b = Set["d", "e"]
 => #<Set: {"d", "e"}>

a | b
 => <Set: {"a", "b", "c", "d", "e"}>

Substracting another enumerable

a = Set[1, 2, 3]
=> #<Set: {1, 2, 3}>

a - [3]
=> #<Set: {1, 2}>

Intersection between a set and an array

a = Set[2,3,4]
 => #<Set: {2, 3, 4}>

 b & [1,2,3]
 => #<Set: {2, 3}>

I think you get the idea. For some problems, this kind of arithmethic is ideal.

Set is just another enum

Of course it might be obvious to you, if you are not new to Ruby 🙂 Set is just another enumerable. It is interchangable with an array for example.

Another nice trait of course is, that you have all the nice methods that come with enumerables at your disposal, wen working with a set.

I highly recommend you reading the enumerable documentation, since this is something out of scope for this little article.

Random stuff about set.rb

  • A SortedSet exists as well
  • There is a RestrictedSet, that is commented - wtf?
  • There are many tests for set within the same file. So scroll down for more examples

Bottom line

Sets are awesome. Sometimes it makes sense to write this kind of arithmetical functions.

This class is really big, but it still makes sense this way. The functions are very small and focused and its quite simple to read.

Set uses some nice tricks. I really love the def self.[] trick for example.

One of the biggest suprises for me was, that you can pass a block to the constructor. I'm not sure if I am a fan of that.

I loved the implementation of set arithmetics - its simple and beautiful.

Reading this file was fun, you should read it as well

IPv6 at home

Recently I listened to a fantastic episode of "Chaosradio Express", that covers IPv6 in great detail. The guest explained how great this is for accessing your home network.

That's when I decided to set up a free account for IPv6 through IPv4 tunneling at SixXs.

The Result

Without having to set up dyndns I can just do:

$ ssh mbair.zipf

And reach my machines inside of my home network. Each machine has its own public IP. Thats exactly how it's supposed to be..

This article describes how you can do the same.

Set up the first tunnel

Its relatively simple. Here are the steps I had to do until it worked.

  • sign up on this page.
  • confirm your email-address
  • wait until SIxXs activates your account
  • Request a tunnel (AYIYA variant)
  • wait unitl SixXS activates the tunnel
  • download the tunnel driver for Mac OS X
  • alt-klick on the pkg and install it
  • brew install aiccu
  • set user/pw in /usr/local/etc/aiccu.conf with your login
  • set ipv6_interface in your aicuu.conf to tun0
  • restart you're Mac
  • Dont forget to turn on your firewall. You have your own public IP in a minute
  • Last but not least start the tunnel:

    sudo /usr/local/sbin/aiccu start

You should have connectivity now. You can check it by pinging another IPv6 enabled host. For example:

ping6 google.com
PING6(56=40+8+8 bytes) 2001:4dd0:ff00:f7e::2 --> 2a00:1450:4016:800::1003
16 bytes from 2a00:1450:4016:800::1003, icmp_seq=0 hlim=55 time=80.803 ms
16 bytes from 2a00:1450:4016:800::1003, icmp_seq=1 hlim=55 time=116.723 ms
16 bytes from 2a00:1450:4016:800::1003, icmp_seq=2 hlim=55 time=80.783 ms
16 bytes from 2a00:1450:4016:800::1003, icmp_seq=3 hlim=55 time=77.813 ms

Setting up the second tunnel

Sixxs has a credit system, in order to only give ressources to user, who really use IPv6 it. You have keep your first tunnel active for about one week, before you can request the second tunnel.

This one you can use for you devices at home.

Aftwerwads you're done. For convenience you might want to add an entry to your /etc/hosts.

2a00:4aa0:4016:fba::2 homeserver

Done.

I hope you find this as usefull as I do.

How to setup your Mac automatically with chef

Recently I joined a team that practices DevOps. That's why I had to learn Chef:

With Chef, you write abstract definitions as source code to describe how you want each part of your infrastructure to be built, and then apply those descriptions to individual servers.

Since I regard my iMac as part of my infrastructure - I decided to give Chef a shot. In this post I explain how I did it.

Bootstrapping chef

Before the first Chef run, you have to prepare youre machine.

I store my cookbooks on Dropbox. So after installing the OS (manually), I download and install Dropbox.

After Dropbox finished syncing I run bootstrap.sh :

USERNAME=shostakovich

mkdir ~/tmp  
cd ~/tmp


# Install GCC + Git

curl https://github.com/downloads/kennethreitz/osx-gcc-installer/GCC-10.7-v2.pkg > GCC-10.7-v2.pkg  
    sudo installer -pkg GCC-10.7-v2.pkg -target /

# Install chef

sudo gem install chef

# Prepare Directory for Homebrew

sudo mkdir /usr/local  
sudo chown -R $USERNAME /usr/local  

This installs a compiler, Homebrew and some dev-tools like GIT on the machine.

Last but not least bootstrap.sh installs Chef itself.

Installing apps & packages

I have my standard set of tools. Instead of installing them manually I wanted to use Chef.

Luckily there are already cookbooks that can install dmg's and apps within zip files.

You just have to download them and then you can specify which apps to
install:

dmg_package "Google Chrome" do  
  dmg_name "googlechrome"
  source "https://dl-ssl.google.com/chrome/mac/stable/GGRM/googlechrome.dmg"
  action :install
end

zip_app_package "Mou" do  
  source "http://mouapp.com/download/Mou.zip"
end

dmg_package "Virtualbox" do  
  source "http://dlc.sun.com.edgesuite.net/virtualbox/4.1.18/VirtualBox-4.1.18-78361-OSX.dmg"
  type "mpkg"
end  

For all my Unix tools I use the Homebrew cookbook.

This way I can specify all the packages I need in my node.json - the configuration file I use to run chef-solo.

{
  "run_list": [
      "recipe[main]",
      "recipe[git]",
      "recipe[rvm]",
      "recipe[apps]"
  ],

  "packages" : [
     "wget",
     "tmux",
     "watch",
     "mobile-shell",
     "imagemagick",
     "solr",
     "mysql",
     "aspell",
     "htmldoc",
     "ghostscript",
     "redis",
     "pdftohtml"
  ],

  "homedir" : "/Users/shostakovich",
  "user" : "shostakovich"
}

Configuration

I store most of my dotfiles on my Dropbox.

When i set up a new machine i symlink them into my home directory. Last but not least, i change some defaults - for example to move the Dock out of the way..

template "#{node['homedir']}/.vimrc" do  
  source "vimrc.erb"
  owner node['user']
end

execute "set dock to be on left" do  
  command "defaults write com.apple.dock orientation -string left"
  user node['user']
end

execute "relaunch dock" do  
  command "killall Dock"
end  

`

How can you get started?

I highly recommend giving it a shot! It's a good way to learn chef.

For a kick start with chef-solo, watch RailsCast 339.

If you have problems setting up chef-solo on a Mac, have a look at how to fix solo.rb.

If you need further ideas, have a look at the workstation setup of pivotal.

The end

I used this a couple of times already. Its kind of boring, to watch chef setting up your dev-machine. But hey - you can drink coffee in the meantime.

© 2017 Rocu.de

Theme by Anders NorenUp ↑