C-Style Ints (#85)

The three rules of Ruby Q.:

  1. Please do not post any solutions or spoiler discussion for this quiz
    until
    48 hours have passed from the time on this message.

  2. Support Ruby Q. by submitting ideas as often as you can:

http://www.rubyquiz.com/

  1. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone
on Ruby T. follow the discussion. Please reply to the original quiz
message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Aaron P.

Write a class that can represent a signed or unsigned number with an
arbitrary
number of bits. This class should support all bitwise operations ( & ^
~ | ),
basic math operations ( + - / * ), and comparison operators. It would
behave
like an integer in C (except with arbitrary length!), so an unsigned int
0xFFFFFFFF + 1 would equal 0x00000000.

One edge case is what to do in an overflow case ( see the first irb
session
number 2 ). Another is how to handle numbers that are wider than the
specified
number of bits. I’m not really sure how to handle that part, but what I
do is
just take the last N number of bits. So if 0xFFEE was passed in to my 8
bit
vector, I would just take 0xEE.

Example irb sessions

Here is an example of using an 8 bit unsigned int with an initial value
of 0xFF:

irb(main):001:0> n = UnsignedFixedWidthInt.new(0xFF, 8)
=> 255
irb(main):002:0> n += 2
=> 1
irb(main):003:0> n = n << 1
=> 2
irb(main):004:0> n = n >> 1
=> 1
irb(main):005:0> ~n
=> 254
irb(main):006:0> n += 12
=> 13
irb(main):007:0> n = n & 0x0E
=> 12
irb(main):008:0>

Now an example of an 8 bit signed int with an initial value of 0x01:

irb(main):001:0> n = SignedFixedWidthInt.new(0x01, 8)
=> 1
irb(main):002:0> n = n << 7
=> -128
irb(main):003:0> n -= 1
=> 127
irb(main):004:0> n = n >> 6
=> 1
irb(main):005:0> n -= 2
=> -1
irb(main):006:0> n = n ^ 0xF3
=> 12
irb(main):007:0> n = n | 0x01
=> 13
irb(main):008:0>

Here is an example of handling numbers that are too wide:

irb(main):001:0> n = UnsignedFixedWidthInt.new(0x0, 8)
=> 0
irb(main):002:0> n += 0xFFEE
=> 238
irb(main):003:0>

Hi!

At Fri, 30 Jun 2006 22:47:46 +0900, Ruby Q. wrote:

Write a class that can represent a signed or unsigned number with an
arbitrary number of bits.
:
irb(main):001:0> n = UnsignedFixedWidthInt.new(0xFF, 8)
:
irb(main):001:0> n = SignedFixedWidthInt.new(0x01, 8)

Does “write a class” imply that UnsignedFixedWidthInt and
SignedFixedWidthInt are two different names for the just one class?

Josef ‘Jupp’ Schugt

I have some questions about some more edge cases.

Ruby Q. [email protected] writes:

irb(main):006:0> n += 12
=> 13
irb(main):007:0> n = n & 0x0E
=> 12
irb(main):008:0>

It would seem from the above that whenever there’s arithmetic with a
FWI as one operand and an Integer as the other, the result should be a
FWI and we should do simple twos-complement arithmetic in that width.

Now, should we also try to ensure that (2 + n) has the same result as
(n + 2) ?

What happens when we operate on two FWIs at once? I would propose
that the answer should be that the result is a FWI with as many bits
as the larger of the two operands, but I’m stuck as to what to do when
you add a SignedFixedWidthInt to an UnsignedFixedWidthInt. What is
the result?

I’d like to propose these rules of arithmetic:

Any operation between a FWI and a Float, Rational, or Complex has the
same result as though the FWI were replaced by an Integer of equal
value.

For operations +, -, ^, &&, *, /, %, and ||, an Integer with a FWI (in
either order) produces the same type of FWI as the FWI argument. For
those same operations, two FWIs produce an FWI with as many bits as
the longer of the two and unsigned if either operand is unsigned.
(rationale: like C)

An alternative set of rules (I’m asking for a ruling here) sets the
result of * and / to the same type as the first argument, and % to the
same type as the second argument. (Rationale: a * 2 is (a + a),
whether a is a Fixnum, Float, Array, or String. This seems like a
property we might want to preserve when a is a FWI, even if “2” is
only a FWI with the value of “2”)

For ** (exponentiation), I’m not sure. My instinct is to say that
it’s an error to raise a FWI to a negative power, and that FWI **
FWI should produce the same type as the first argument. (Rationale:
it’s like repeated multiplication)

As for just taking the last n bits when passed an initial argument
that’s too wide - that’s exactly what you want to do. That lets us
emulate the C cast-to-smaller-type:

short int g = (short int) some_big_variable;

with FWI.new(). C is always taking only the least significant
portion, so if we want to look like C…

On Jun 30, 2006, at 4:41 PM, Josef ‘Jupp’ SCHUGT wrote:

Does “write a class” imply that UnsignedFixedWidthInt and
SignedFixedWidthInt are two different names for the just one class?

Hmm, good point. Confusing wording there. Go with whatever method
is easiest to implement. (I would probably make two classes.)

James Edward G. II

It certainly looks like two classes to me (and that is what my earlier
test
harness assumes).
The only way to do it with a single class would be to somehow tell it
whether it was signed or unsigned.
My plan is to implement one of them and then use it or extend it from
the
other one.

If I didn’t have this darn job I would be doing the quiz right now…
:slight_smile:
JB

fr ruby quiz:

Write a class that can represent a signed or unsigned number

with an arbitrary number of bits. This class should support all

bitwise

operations ( & ^ ~ | ), basic math operations ( + - / * ), and

comparison

and bonus if it handles ++ ?:slight_smile:

Peña schrieb:

and bonus if it handles ++ ?:slight_smile:

How do you plan to implement the pre increment operator?
Is this even possible?

Rob

Sorry for my ignorance but FWI stands for what?
(http://www.acronymattic.com/results.aspx?q=fwi)

./alex

.w( the_mindstorm )p.

(http://themindstorms.blogspot.com)

fr robert:

How do you plan to implement the pre increment operator?

Is this even possible?

sorry, i was just joking. i thought the smiley was enough to give hint
:slight_smile:
kind regards -botp

On 1 Jul 2006, at 09:53, Alexandru P. wrote:

Sorry for my ignorance but FWI stands for what?

Kerry

On Sat, Jul 01, 2006 at 05:20:10PM +0900, Peña, Botp wrote:

fr robert:

How do you plan to implement the pre increment operator?

Is this even possible?

sorry, i was just joking. i thought the smiley was enough to give hint :slight_smile:

Actually, it is possible.
I’ll be posting some code after the 48H no-spoiler period, since it
resembles
that of a possible solution to the quiz.

Robert R. [email protected] writes:

Peña schrieb:

and bonus if it handles ++ ?:slight_smile:

How do you plan to implement the pre increment operator?
Is this even possible?

Pre is, post isn’t.
The rest is left as an exercise to the reader. :wink:

On 1 Jul 2006, at 10:43, Kerry B. wrote:

On 1 Jul 2006, at 09:53, Alexandru P. wrote:

Sorry for my ignorance but FWI stands for what?

Kerry

Hmmm. I’m sure there were words in there when I typed it. I thought I
said “fixed-width integers”.

Kerry

“Alexandru P.” [email protected] writes:

Sorry for my ignorance but FWI stands for what?
(http://www.acronymattic.com/results.aspx?q=fwi)

FixedWidthInt, meant to include both UnsignedFixedWidthInt and
SignedFixedWidthInt.

On Sat, Jul 01, 2006 at 09:57:18AM +0900, Daniel M. wrote:

irb(main):004:0> n = n >> 1

FWI as one operand and an Integer as the other, the result should be a

I’d like to propose these rules of arithmetic:

Any operation between a FWI and a Float, Rational, or Complex has the
same result as though the FWI were replaced by an Integer of equal
value.

I agree. And that’s a good hint for implementation :stuck_out_tongue:

property we might want to preserve when a is a FWI, even if “2” is
only a FWI with the value of “2”)

I like this second set of rules much better, or something even
simpler: The result has to be of the same class as the first
argument. If I am going to use a width-restricted integer class at
all, I expect the width to stay the same for things like

fwi += other

and not be coerced to the larger width of both or some other class.
If other would be an (infinite size) ruby int, we don’t coerce to that
either, don’t we?

I also think we can safely ignore subtle points about C floats,
rationals etc, since we don’t need to reimplement all of C’s numeric
types here and sane interaction with other ruby numerics is hard
enough.

-Jürgen

On Sat, Jul 01, 2006 at 07:40:43PM +0900, Mauricio F. wrote:

On Sat, Jul 01, 2006 at 05:20:10PM +0900, Peña, Botp wrote:

fr robert:

How do you plan to implement the pre increment operator?

Is this even possible?

sorry, i was just joking. i thought the smiley was enough to give hint :slight_smile:

Actually, it is possible.
I’ll be posting some code after the 48H no-spoiler period, since it resembles
that of a possible solution to the quiz.

It’s Mon Jul 3 00:16:10 JST; I think the 48H are over.
I wrote about a way to implement such preincrement/decrement operators
at
http://eigenclass.org/hiki.rb?ruby+preincrement+operator

Jupp wrote:

Does “write a class” imply that UnsignedFixedWidthInt and
SignedFixedWidthInt are two different names for the just one class?

This is my first quiz submission for a while. This question is what
intrigued me, actually.

In C, an unsigned int is a different type to an unsigned long long.
Therefore, my solution provides a mechanism for generating these
subtypes: one class for each distinct combination of size and either
signed or unsigned, which all share the parent class FixedWidthInt.

Here’s what the code that uses this library looks like:

UInt32 = FixedWidthInt.type(:unsigned, 32) # define a new int type
i = UInt32.get(42) # get instance of the type
i == 42 #=> true

j = FixedWidthInt.get(:unsigned, 32, 86) # no explicit type in call
j.kind_of? UInt32 #=> true # but result type is same

k = UnsignedFixedWidthInt.new(0xFF00FF00, 32) # quiz compatible syntax
k.kind_of? UnsignedFixedWidthInt #=> true
k.kind_of? UInt32 #=> true

My solution is not well-tested, and is pretty much guaranteed to have
some bugs due to the way it uses method_missing to delegate to an
underlying Integer. I also threw in Mauricio F.’ WeakHash (an
improved version to work with Bignum values) for the heck of it.

Here’s the code:

http://dave.burt.id.au/ruby/fixed_width_ints.rb
http://dave.burt.id.au/ruby/weak_hash.rb

Cheers,
Dave

Hello,

I am lazy, so I avoided math as much as possible. In fact, I went to
some length to avoid dealing with the problem altogether, delegating
to ruby’s Integer and even let ruby define my delegated functions :slight_smile:

Fixed Width Integer Class for Ruby Q. #85

© 2006 Jürgen Strobel [email protected]

This program is free software; you can redistribute it

and/or modify it under the terms of the GNU General Public

License as published by the Free Software Foundation;

either version 2 of the License, or (at your option) any

later version.

require “forwardable.rb”

Base class for Integer classes with a fixed bit width

Almost all methods are delegated to an encapsulated integer object.

Metaprogramming is used to automate delegation & conversion.

class FixedWidthInt

include Comparable
extend Forwardable
private_class_method :new

def self.def_fwi_delegator(accessor, method) # taken from forward.rb
module_eval(<<-EOS, “(FWI_DELEGATION)”, 1)
def #{method}(*args, &block)
begin
#puts “delegating #{method} and converting the result”
self.class.new(#{accessor}.send(:#{method}, *args,
&block), width)
rescue Exception
[email protected]_if{|s| /^\(FWI_DELEGATION\):confused: =~ s} unless
Forwardable::debug
Kernel::raise
end
end
EOS
end
def method_missing(op, *args) # a method is missing?
if @i.respond_to?(op) # our @i could handle
it?
#puts “defining new method #{op}”
FixedWidthInt.def_fwi_delegator :@i, op # define it by
delegation!
self.send(op, *args) # and try again
else # else
super # NoMethodError
end
end

def initialize(i = 0, w = 8)
w = w.to_i
raise “Invalid width” unless w >= 1
@width, @i = w, i.to_i & ((1<<w) - 1)
end

def coerce_to_width(nw)
self.class.new(i, nw)
end

def inspect
“#{self.i}(#{self.class.name[0,1]}#{width})”
end

attr_reader :i, :width
def_delegators :@i, :[], :zero?
def_delegators :i, :to_i, :to_s, :<=>, :times, :coerce, :divmod, :quo,
:to_f

We might have to define or delegate more methods explicitly which

are not working correctly with #method_missing. Especially those

not returning a FixedWidthInt.

end

A fixed width unsigned integer

class UnsignedFixedWidthInt < FixedWidthInt
public_class_method :new
end

A fixed width signed integer

class SignedFixedWidthInt < FixedWidthInt
public_class_method :new

Interpret @i differently if the highest bit is set, everything

else works magically thanks to 2’s complement arithmentic.

def i
if (@i >> (width-1)).zero?
@i
else
@i - (1 << width)
end
end
end

############ snip

I also took the tests from the irb session und extended them:

#!/usr/bin/ruby

Fixed Width Integer Class Unit Tests (Ruby Q. #85)

© 2006 Jürgen Strobel [email protected]

This program is free software; you can redistribute it

and/or modify it under the terms of the GNU General Public

License as published by the Free Software Foundation;

either version 2 of the License, or (at your option) any

later version.

require “fixed_width_int.rb”
require ‘test/unit’

class FWITest < Test::Unit::TestCase
def test_unsigned
assert_equal 255, (n = UnsignedFixedWidthInt.new(0xff, 8))
assert_equal 1, (n += 2)
assert_equal 2, (n = n << 1)
assert_equal 1, (n = n >> 1)
assert_equal 254, (~n)
assert_equal 13, (n += 12)
assert_equal 12, (n = n & 0x0E)

assert_kind_of FixedWidthInt, n
assert_instance_of UnsignedFixedWidthInt, n
assert_equal 144, (n * n)
assert_equal 0, (n-n)
assert_equal 3, (m = -9 + n)
assert_kind_of Integer, m
assert_kind_of Float, n.to_f

end

def test_signed
assert_equal 1, (n = SignedFixedWidthInt.new(0x01, 8))
assert_equal -128, (n = n << 7)
assert_equal 127, (n -= 1)
assert_equal 1, (n = n >> 6)
assert_equal -1, (n -= 2)
assert_equal 12, (n = n ^ 0xF3)
assert_equal 13, (n = n | 0x01)

assert_kind_of FixedWidthInt, n
assert_instance_of SignedFixedWidthInt, n
assert_equal -169&0xff, (n * (-n))
assert_equal 0, (n-n)
assert_equal -1, (m = -14 + n)
assert_kind_of Integer, m
assert_kind_of Float, n.quo(17)

end

def test_too_wide
assert_equal 0, (n = UnsignedFixedWidthInt.new(0x0, 8))
assert_equal 238, (n += 0xFFEE)
end
end

############### snip

~/ruby/% ruby test_fixed_width_int.rb
Loaded suite test_fixed_width_int
Started

Finished in 0.023573 seconds.

-Jürgen

My solution consists of two functions which generate new FWI classes
you can use.
By using coerce it supports calculations with any combination of FWI
and normal integers.

rafb link: http://rafb.net/paste/results/We7miQ42.html

require ‘delegate’

def UnsignedFWI(bits = 32)
Class.new(DelegateClass(Bignum)) {
define_method(:fix) {|n| n & (1<<bits)-1 }
define_method(:initialize){|n| super fix(n.to_i) }
define_method(:coerce) {|n| [self.class.new(n),self.to_i] }
[:+,:-,:/,:*,:%,:**,:[email protected],:[email protected],:&,:|,:^,:<<,:>>,:~].each{|m|
define_method(m) {|*args| self.class.new super(*args) }
}
}
end

def SignedFWI(bits = 32)
Class.new(UnsignedFWI(bits)) {
define_method(:fix){|n| (n & (1<<bits)-1) - (n[bits-1] << bits) }
}
end

Hello,
This is my first participation to the quiz.

I reimplemented all the behavior of the C integers without using the
ruby core classes (Not counting the interaction with them).

class Bit
include Comparable

def initialize(bit = false)
if bit.respond_to? :to_i
@bit = (bit.to_i & 1) == 1
else
@bit = true & bit
end
end

def &(bit)
Bit.new(@bit & Bit.new(bit).high?)
end

def |(bit)
Bit.new(@bit | Bit.new(bit).high?)
end

def ^(bit)
Bit.new(@bit ^ Bit.new(bit).high?)
end

def [email protected]
Bit.new(!@bit)
end

def <<(int)
Bit.new(0)
end
alias :>> :<<

def <=>(bit)
cmp = Bit.new(bit)
if (self & cmp | ~self & ~cmp).high?
0
elsif (self & ~cmp).high?
1
else
-1
end
end

def to_s
to_i.to_s
end
alias :inspect :to_s

def to_i
if @bit
1
else
0
end
end

def high?
@bit
end

def low?
!@bit
end

Returns 2 bits : [result, carry]

def add(bit, carry)
[Bit.new(self ^ bit ^ carry), Bit.new(self & bit | self & carry |
bit & carry)]
end
end

class DivisionByZero < StandardError; end

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 to_s
@bits.reverse.join
end
alias :inspect :to_s

def to_a
@bits.reverse
end

def
if index.between? 0, width-1
@bits[index]
else
Bit.new(0)
end
end

def []=(index, value)
@bits[index] = Bit.new(value)
end

def <=>(cint)
cmp = self.class.new(cint, width)
to_a <=> cmp.to_a
end

def &(cint)
a = self.class.new(cint, width)
self.class.new(width) {|bit| @bits[bit] & a[bit] }
end

def |(cint)
o = self.class.new(cint, width)
self.class.new(width) {|bit| @bits[bit] | o[bit] }
end

def ^(cint)
x = self.class.new(cint, width)
self.class.new(width) {|bit| @bits[bit] ^ x[bit] }
end

def [email protected]
self.class.new(width) {|bit| [email protected][bit] }
end

def [email protected]
self
end

def >>(int)
self.class.new(width) {|bit| self[bit+int] }
end

def <<(int)
self.class.new(width) {|bit| self[bit-int] }
end

def +(cint)
added = self.class.new(cint, width)
carry = 0
self.class.new(width) { |bit|
r, carry = self[bit].add(added[bit], carry)
r
}
end

def -(cint)
sub = ~self.class.new( cint, width)+1
self + sub
end

def *(cint)
mult = self.class.new( cint, width)
wide_self = self.class.new(self, 2 * width)
res = self.class.new(0, 2 * width)
width.times { |bit|
res += wide_self << bit if mult[bit].high?
}
res
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

class SFWI < UFWI
alias :unsigned_to_i :to_i
def to_i
if @bits.last.high?
-((~self).unsigned_to_i + 1)
else
unsigned_to_i
end
end

def [email protected]
~self+1
end
end

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