/gist:9211fd24c3759f7f340dede28929c659
Forked from zwegner/gist:6841688fa897aef64a11016967c36f2d
Last active Jan 13, 2020
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