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 L.'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{& ^ | << >> + - * / [email protected] [email protected] [email protected]}.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 M.'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.)

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs