From: Ruby Quiz <james@...>
Date: 2006-07-06T23:32:05+09:00
Subject: [SUMMARY] C-Style Ints (#85)

There was quite a bit of confusion over what we were after in the quiz. 
Ironically, I think that's all my fault for giving the author's simple quiz the
name "C-Style Ints."  Things are always complicated when you drag C into them
and some solvers bent over backwards to dissect C's behavior.  Luckily, that
lead to some cool solutions for us to examine.

One way to tackle this problem is to rebuild all the needed math operations. 
That leads to quite a bit of code like this excerpt from Hank Lords's
submission:

	# ...
	
	class UFWI
	 include Comparable
	
	 attr_reader :width
	
	 def initialize(int=0, width=8)
	   if block_given?
	     @width = int
	     @bits = Array.new(@width) {|index| Bit.new(yield( index)) }
	   else
	     @width = width
	     @bits = Array.new(@width) {|bit| Bit.new(int.to_i >> bit) }
	   end
	 end
	
	 def to_i
	   @bits.reverse.inject(0) {|num, bit| (num << 1) + bit.to_i}
	 end
	 alias :to_int :to_i
	
	 def coerce(*args)
	   to_int.coerce(*args)
	 end
	
	 # ...
	
	 def &(cint)
	   a = self.class.new(cint, width)
	   self.class.new(width) {|bit| @bits[bit] & a[bit] }
	 end
	
	 # ...
	
	 def / (cint)
	   # Binary euclidian division
	
	   b = self.class.new(cint, width)
	   raise DivisionByZero if b == 0
	   b0 = self.class.new(1, width)
	   width.times {
	     break if self < b0*b
	     b0 <<= 1
	   }
	   a0 = b0 >> 1
	
	   while b0 - a0 > 1 do
	     c = (a0 >> 1) + (b0 >> 1)
	     if c * b <= self
	       a0 = c
	     else
	       b0 = c
	     end
	   end
	   a0
	 end
	end
	
	# ...

Obviously, I'm showing only a couple of operations here and you can see that
this code uses a Bit class (not shown).  Hank did the work by teaching Ruby to
work with ordinary bits and then building the needed number operations on top of
that framework.  You can see the numbers being constructed as an Array of Bits
in initialize(), either from a provided integer or using a block to generate the
bits iteratively.

The next couple of methods allow these numbers to be used in math operations
with Ruby's native numbers.  The first step is to provide a conversion for this
UFWI to a normal Ruby Integer.  Once we have that, a coerce() method is defined
which Ruby uses to resolve numerical operations with custom objects.  This
version just converts our UFWI to a normal Integer, then delegates the call to
the built-in coerce().

Finally, I've left in two example operations.  You can see that Hank resolves
these operations using handle-rolled bit math.  In some cases (like &()), this
can be done trivially, but others (like /()) get a little complicated.  Hank did
a top notch job creating all the needed operations.  I've just left them out
here to keep this summary reasonably small.

Hank's solution is solid, but it took a lot of work to create.  What we really
want to do is to get Ruby to do as much of that work for us as humanly possible.
Many quiz solvers found ways to do this.  Here's a lovely version by Boris
Prinz:

	class UnsignedFixedWidthInt
	  def initialize(value, bits)
	    raise ArgumentError.new('number of bits must be > 0') if bits <= 0
	    @bits  = bits
	    @value = value % 2**@bits
	  end
	
	  # operators returning a new FixedWidthInt
	  %w{& ^ | << >> + - * / +@ -@ ~@}.each do |operator|
	    define_method operator do |*other|
	      self.class.new(@value.send(operator, *other), @bits)
	    end
	  end
	
	  # methods forwarded to @value
	  %w{== < > <=> inspect to_s to_i to_int}.each do |meth|
	    define_method meth do |*other|
	      @value.send(meth, *other)
	    end
	  end
	
	  def coerce(other)
	    Integer == other ? [other, @value] : [Float(other), Float(@value)]
	  end
	end
	
	class SignedFixedWidthInt < UnsignedFixedWidthInt
	  def initialize(value, bits)
	    super(value, bits)
	    # value is negative if MSB is set:
	    @value -= 2**@bits if @value[@bits - 1] == 1
	  end
	end

With this example, the majority of the work is done in the initialize() methods
of UnsignedFixedWidthInt and SignedFixedWidthInt.  They simply store the bit
width and numerical value for future use.  It the passed number is larger than
the indicated width, it is truncated at this time.  The SignedFixedWidthInt adds
a check for the sign bit and negates the number when set.

Next Boris uses a little metaprogramming to quickly define a bunch of similar
math operations.  These methods just delegate to the proper math method on the
actual numerical object and hand the results back to the class constructor. 
This insures that any result is truncated, if needed.

Boris also uses the metaprogramming trick to define a handful of methods that
return native Ruby types.  The end result is 20 method definitions in just a few
lines of code.  Very nice results.

Finally, Boris does add the coerce() method, similar to Hank's code, so the new
integer types can be used in math operation with normal Ruby numerical types.

My thanks to all who took a stab at this quiz.  Sorry my naming of it made it
seem more involved than intended.  Have a look at Daniel Martin's thorough C
conversion for a great example of that solution path.

Tomorrow we will try our luck with a panagram problem...  (I had to look that
word up.)