124 lines
2.7 KiB
Ruby
124 lines
2.7 KiB
Ruby
class BalancedTernary
|
|
include Comparable
|
|
def initialize(str = "")
|
|
if str =~ /[^-+0]+/
|
|
raise ArgumentError, "invalid BalancedTernary number: #{str}"
|
|
end
|
|
@digits = trim0(str)
|
|
end
|
|
|
|
I2BT = {0 => ["0",0], 1 => ["+",0], 2 => ["-",1]}
|
|
def self.from_int(value)
|
|
n = value.to_i
|
|
digits = ""
|
|
while n != 0
|
|
quo, rem = n.divmod(3)
|
|
bt, carry = I2BT[rem]
|
|
digits = bt + digits
|
|
n = quo + carry
|
|
end
|
|
new(digits)
|
|
end
|
|
|
|
BT2I = {"-" => -1, "0" => 0, "+" => 1}
|
|
def to_int
|
|
@digits.chars.inject(0) do |sum, char|
|
|
sum = 3 * sum + BT2I[char]
|
|
end
|
|
end
|
|
alias :to_i :to_int
|
|
|
|
def to_s
|
|
@digits.dup # String is mutable
|
|
end
|
|
alias :inspect :to_s
|
|
|
|
def <=>(other)
|
|
to_i <=> other.to_i
|
|
end
|
|
|
|
ADDITION_TABLE = {
|
|
"---" => ["-","0"], "--0" => ["-","+"], "--+" => ["0","-"],
|
|
"-0-" => ["-","+"], "-00" => ["0","-"], "-0+" => ["0","0"],
|
|
"-+-" => ["0","-"], "-+0" => ["0","0"], "-++" => ["0","+"],
|
|
"0--" => ["-","+"], "0-0" => ["0","-"], "0-+" => ["0","0"],
|
|
"00-" => ["0","-"], "000" => ["0","0"], "00+" => ["0","+"],
|
|
"0+-" => ["0","0"], "0+0" => ["0","+"], "0++" => ["+","-"],
|
|
"+--" => ["0","-"], "+-0" => ["0","0"], "+-+" => ["0","+"],
|
|
"+0-" => ["0","0"], "+00" => ["0","+"], "+0+" => ["+","-"],
|
|
"++-" => ["0","+"], "++0" => ["+","-"], "+++" => ["+","0"],
|
|
}
|
|
|
|
def +(other)
|
|
maxl = [to_s.length, other.to_s.length].max
|
|
a = pad0_reverse(to_s, maxl)
|
|
b = pad0_reverse(other.to_s, maxl)
|
|
carry = "0"
|
|
sum = a.zip( b ).inject("") do |sum, (c1, c2)|
|
|
carry, digit = ADDITION_TABLE[carry + c1 + c2]
|
|
sum = digit + sum
|
|
end
|
|
self.class.new(carry + sum)
|
|
end
|
|
|
|
MULTIPLICATION_TABLE = {
|
|
"-" => "+0-",
|
|
"0" => "000",
|
|
"+" => "-0+",
|
|
}
|
|
|
|
def *(other)
|
|
product = self.class.new
|
|
other.to_s.each_char do |bdigit|
|
|
row = to_s.tr("-0+", MULTIPLICATION_TABLE[bdigit])
|
|
product += self.class.new(row)
|
|
product << 1
|
|
end
|
|
product >> 1
|
|
end
|
|
|
|
# negation
|
|
def -@()
|
|
self.class.new(@digits.tr('-+','+-'))
|
|
end
|
|
|
|
# subtraction
|
|
def -(other)
|
|
self + (-other)
|
|
end
|
|
|
|
# shift left
|
|
def <<(count)
|
|
@digits = trim0(@digits + "0"*count)
|
|
self
|
|
end
|
|
|
|
# shift right
|
|
def >>(count)
|
|
@digits[-count..-1] = "" if count > 0
|
|
@digits = trim0(@digits)
|
|
self
|
|
end
|
|
|
|
private
|
|
|
|
def trim0(str)
|
|
str = str.sub(/^0+/, "")
|
|
str = "0" if str.empty?
|
|
str
|
|
end
|
|
|
|
def pad0_reverse(str, len)
|
|
str.rjust(len, "0").reverse.chars
|
|
end
|
|
end
|
|
|
|
a = BalancedTernary.new("+-0++0+")
|
|
b = BalancedTernary.from_int(-436)
|
|
c = BalancedTernary.new("+-++-")
|
|
|
|
%w[a b c a*(b-c)].each do |exp|
|
|
val = eval(exp)
|
|
puts "%8s :%13s,%8d" % [exp, val, val.to_i]
|
|
end
|