Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save dougallj/9211fd24c3759f7f340dede28929c659 to your computer and use it in GitHub Desktop.
Save dougallj/9211fd24c3759f7f340dede28929c659 to your computer and use it in GitHub Desktop.
Ternary logic multiplication (0, 1, unknown)
N_BITS = 8
MASK = (1 << N_BITS) - 1
class Ternary:
def __init__(self, ones, unknowns):
self.ones = ones & MASK
self.unknowns = unknowns & MASK
assert (self.ones & self.unknowns) == 0, (bin(self.ones), bin(self.unknowns))
def __add__(self, other):
x = self.ones + other.ones
u = self.unknowns | other.unknowns | (x ^ (x + self.unknowns + other.unknowns))
return Ternary(x & ~u, u)
def __sub__(self, other):
x = self.ones - other.ones
u = self.unknowns | other.unknowns | ((x + self.unknowns) ^ (x - other.unknowns))
return Ternary(x & ~u, u)
def __or__(self, other):
o = self.ones | other.ones
return Ternary(o, (self.unknowns | other.unknowns) & ~o)
def __lshift__(self, count):
return Ternary(self.ones << count, self.unknowns << count)
def __mul__(self, other):
# imprecise
result = Ternary(0, 0)
for i in range(N_BITS):
if self.ones & 1 << i:
result += other << i
elif self.unknowns & 1 << i:
u = other << i
result += Ternary(0, u.ones | u.unknowns)
return result
def __repr__(self):
return ''.join('U' if self.unknowns & 1 << i else str(self.ones >> i & 1)
for i in reversed(range(N_BITS)))
def iter_values(self):
ones = self.ones
mask = self.unknowns
value = 0
while True:
yield ones | value
value = (value - mask) & mask
if value == 0:
return
def union(a, b):
return Ternary(a.ones & b.ones, a.unknowns | b.unknowns | (a.ones ^ b.ones))
def slow_op(a, b, op):
r = Ternary(op(a.ones, b.ones), 0)
for A in a.iter_values():
for B in b.iter_values():
r = union(r, Ternary(op(A, B), 0))
return r
def test_op(f, name, input_size=4):
good = 0
imprecise = 0
wrong = 0
for ao in range(1 << input_size):
for au in range(1 << input_size):
if (ao & au) != 0:
continue
for bo in range(1 << input_size):
for bu in range(1 << input_size):
if (bo & bu) != 0:
continue
a = Ternary(ao, au)
b = Ternary(bo, bu)
r0 = slow_op(a, b, f)
r1 = f(a, b)
if repr(r0) != repr(r1):
if (r0.unknowns & ~r1.unknowns) != 0 or (r1.ones & ~(r0.unknowns | r1.unknowns)) != (r0.ones & ~(r0.unknowns | r1.unknowns)):
wrong += 1
print('wrong: %r %s %r -> slow=%r, fast=%r' % (a, name, b, r0, r1))
else:
imprecise += 1
print('imprecise: %r %s %r -> slow=%r, fast=%r' % (a, name, b, r0, r1))
else:
good += 1
print('testing %r: %d good, %d imprecise, %d wrong' % (name, good, imprecise, wrong))
test_op(lambda a, b: (a * b), "*")
test_op(lambda a, b: (a + b), "+")
test_op(lambda a, b: (a - b), "-")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment