import sys def Log2(n): if n != int(n): raise Exception("Not an int: %g" % n) if n == 1: return 0 else: return Log2(n / 2.0)+1 assert Log2(1) == 0 assert Log2(2) == 1 assert Log2(4) == 2 assert Log2(64) == 6 NUMERIC = [int, long, float] def scalar(x): return type(x) in NUMERIC def add(x, y): if scalar(x) and scalar(y): return x + y else: return tuple([xe + ye for xe, ye in zip(x, y)]) def sub(x, y): if scalar(x) and scalar(y): return x - y else: return tuple([xe - ye for xe, ye in zip(x, y)]) def neg(x): if scalar(x): return -x else: return tuple([-e for e in x]) def conj(x): #print "conj <<", x if scalar(x): z = x elif len(x) == 2: a, b = x z = (a, -b) else: a, b = split(x) z = conj(a) + neg(b) # List add. #print "conj >>", z return z def split(x): h = len(x) / 2 return tuple(x[:h]), tuple(x[h:]) # Mathemetician's multiply: # multiplier is on the left (x). # Backwards of what we show the users. MUL_CACHE = {} def mul(x, y): if scalar(x) and scalar(y): return x * y cache_key = (x, y) cached = MUL_CACHE.get(cache_key) if cached: return cached lx, ly = len(x), len(y) assert lx == ly, (lx, ly) h = lx/2 if h == 1: # Components are scalars. a, b, c, d = x[0], x[1], y[0], y[1] else: # Components are complex. a, b, c, d = x[:h], x[h:], y[:h], y[h:] #print "mul <<<<<<", a, b, c, d t1 = mul(a, c) t2 = mul(d, conj(b)) left = sub(t1, t2) t3 = mul(conj(a), d) t4 = mul(c, b) right = add(t3, t4) #print "mul >>>>>>", t1, t2, t3, t4, ">>>>>>", left, right if scalar(left): z = tuple([left, right]) else: z = tuple(left + right) # List add. MUL_CACHE[cache_key] = z return z assert add(3, 4) == 7 assert add([10, 11], [20, 22]) == (30, 33) assert sub([10, 11], [20, 22]) == (-10, -11) assert conj(4) == 4 assert conj([55, 66]) == (55, -66) def TestQuaternions(): Q0, Q1 = (0, 0, 0, 0), (1, 0, 0, 0) Qi, Qj, Qk = (0, 1, 0, 0), (0, 0, 1, 0), (0, 0, 0, 1) assert neg(Q0) == (0, 0, 0, 0) assert neg(Q1) == (-1, 0, 0, 0) # Test multQiplyQing by 0. assert mul(Q0, Qi) == Q0 assert mul(Q0, Qj) == Q0 assert mul(Q0, Qk) == Q0 assert mul(Qi, Q0) == Q0 assert mul(Qj, Q0) == Q0 assert mul(Qk, Q0) == Q0 # Test multQiplyQing by 1. assert mul(Q1, Qi) == Qi assert mul(Q1, Qj) == Qj assert mul(Q1, Qk) == Qk assert mul(Qi, Q1) == Qi assert mul(Qj, Q1) == Qj assert mul(Qk, Q1) == Qk # Test rocQk-paper-scQissors wQith Qi, Qj, Qk. if 0: assert mul(Qi, Qj) == Qk assert mul(Qj, Qk) == Qi assert mul(Qk, Qi) == Qj assert mul(Qj, Qi) == neg(Qk) == (0, 0, 0, -1) assert mul(Qk, Qj) == neg(Qi) == (0, -1, 0, 0) assert mul(Qi, Qk) == neg(Qj) == (0, 0, -1, 0) TestQuaternions() def BasisVec(n, i): vec = n * [0] vec[i] = 1 return tuple(vec) def DecodeUnitVector(vec): assert 1 == sum([e != 0 for e in vec]) assert 1 == sum([e in [1, -1] for e in vec]) if vec[0]==1: return "1" if vec[0]==-1: return "-1" sign = sum(vec) assert sign==1 or sign==-1 i = abs(sum([x*y for x,y in zip(vec, range(len(vec)))])) assert 0 <= i < len(vec) s = '' c = ord('a') while i > 0: if i & 1: s += chr(c) i >>= 1 c += 1 return "%s%s" % (('-' if sign<0 else ''), s) def TestOctonions(): # Build the octonions. K = [BasisVec(8, i) for i in range(8)] K0 = tuple(8 * [0]) K1 = K[0] Kminus1 = tuple(-e for e in K1) for i in range(8): #print "Octonion Basis #%d: %s" % (i, K[i]) assert K[i] == mul(K1, K[i]) # test mult by 1 assert K[i] == mul(K[i], K1) # test mult by 1 assert K0 == mul(K[i], K0) # test mult by 0 assert K0 == mul(K0, K[i]) # test mult by 0 assert neg(K[i]) == mul(Kminus1, K[i]) # test mult by -1 assert neg(K[i]) == mul(K[i], Kminus1) # test mult by -1 def CheckOctonions(): for i in range(8): print for j in range(8): prod = mul(K[i], K[j]) #print "Octonion #%d x #%d = %s" % (i, j, prod) # Check that units are closed under mul: # -- Exactly 1 member of prod is nonzero. assert 1 == sum([e != 0 for e in prod]) # -- Exactly 1 member of prod is 1 or -1. assert 1 == sum([e in [1, -1] for e in prod]) if i == j: # If a basis is multiplied by itself, if i == 0: # -- Real basis squares to be 1. assert (1, 0, 0, 0, 0, 0, 0, 0) == prod if i > 1: # -- Imaginary bases square to be -1. assert (-1, 0, 0, 0, 0, 0, 0, 0) == prod elif i>0 and j>0: # If not multiplied by itself, and neither is 1, check anti-commutativity. backwards_prod = mul(K[j], K[i]) # Multiplied backwards. assert neg(prod) == backwards_prod, (i, j, K[i], K[j], prod, backwards_prod) CheckOctonions() TestOctonions() def TestNions(n): # Build the basis vectors N. N = [BasisVec(n, i) for i in range(n)] Zero = tuple(n * [0]) One = N[0] MinusOne = neg(One) for i in range(n): print "%dNion Basis #%d: %s" % (n, i, N[i]) assert N[i] == mul(One, N[i]) # test mult by 1 assert N[i] == mul(N[i], One) # test mult by 1 assert Zero == mul(N[i], Zero) # test mult by 0 assert Zero == mul(Zero, N[i]) # test mult by 0 assert neg(N[i]) == mul(MinusOne, N[i]) # test mult by -1 assert neg(N[i]) == mul(N[i], MinusOne) # test mult by -1 def CheckNions(): for i in range(n): print for j in range(n): prod = mul(N[i], N[j]) backwards_prod = mul(N[j], N[i]) # Multiplied backwards. print "%dNion #%d x #%d = %s" % (n, i, j, prod) # Check that units are closed under mul: # -- Exactly 1 member of prod is nonzero. assert 1 == sum([e != 0 for e in prod]) # -- Exactly 1 member of prod is 1 or -1. assert 1 == sum([e in [1, -1] for e in prod]) # Check type of associativity. for k in range(n): left = mul(prod, N[k]) right = mul(N[i], mul(N[j], N[k])) if n < 8: # Must be associative. assert left==right, (i, j, k, left, right) else: # Must be plus-or-minus associative. assert left == neg(right) or left==right, (i, j, k, left, right) if left == (right): print 'ASSOC: %s, %s, %s' % (i, j, k) if left == neg(right): print 'ANTI: %s, %s, %s' % (i, j, k) # Check alternative property. if i==j or j==k or k==i: assert left==right, (i, j, k, left, right, 'Alternative?') if i == j: # If a basis is multiplied by itself, if i == 0: # -- Real basis squares to be 1. assert One == prod if i > 1: # -- Imaginary bases square to be -1. assert MinusOne == prod elif i>0 and j>0: # If not multiplied by itself, and neither is 1, check anti-commutativity. assert neg(prod) == backwards_prod, (i, j, N[i], N[j], prod, backwards_prod) CheckNions() #TestNions(2) #TestNions(4) #TestNions(8) #TestNions(16) #TestNions(32) #TestNions(64) #TestNions(128) def Brief(vec): return ''.join(['1' if e==1 else '-' if e==-1 else '.' if e==0 else '?' for e in vec]) def UnitNames(alphabet): def Inner(s): if len(s) == 1: yield '' yield s else: for e in Inner(s[1:]): yield e yield s[0]+e return list((e if e else '1') for e in Inner(alphabet)) return sorted((e if e else '1') for e in Inner(alphabet)) #print repr(UnitNames('abcxy')) def AssignNames(D, T, N, alphabet): n = len(N) def LeftToRight(s): x = N[0] #print 'LeftToRight(%s):' % s for c in s: if c == '1': pass elif c == '-': x = neg(x) else: f = D[c] x = mul(f, x) #print 'LeftToRight: %s -> f = %s -> x = %s' % (c, f, x) #print 'LeftToRight(%9s) = %s' % (s, Brief(x)) return x b = 1 i = 0 while b < n: c = alphabet[i] vec = BasisVec(n, b) D[c] = vec T[vec] = c b <<= 1 i += 1 for s in UnitNames(alphabet): vec = LeftToRight(s) D[s] = vec T[vec] = s D['-' + s] = neg(vec) T[neg(vec)] = '-' + s return LeftToRight def Alphabet(n): ALFA = 'abcdefghijklmnopqrstuvwxyz' ALFA = 'abcxyzpqrstuv' s = '' b = 1 i = 0 while b < n: s += ALFA[i] b <<= 1 i += 1 return s def PrintAbsoluteTable(n, ht): alfa = Alphabet(n) N = [BasisVec(n, i) for i in range(n)] D, T = {}, {} left2right = AssignNames(D, T, N, alfa) print >>ht, '' for i in range(n): a = N[i] ta = T[a] print >>ht, '' for j in range(n): b = N[j] tb = T[b] prod = mul(b, a) # Proper multiplication. tprod = T[prod] if tprod.startswith('-'): print >>ht, '
 ', tprod else: print >>ht, ' ', tprod print >>ht, '

' def SingleLetterMoves(n): alfa = Alphabet(n) N = [BasisVec(n, i) for i in range(n)] D, T = {}, {} left2right = AssignNames(D, T, N, alfa) print '============= Single Letter Moves: n=', n for i in range(n): a = N[i] ta = T[a] print for j in range(n): b = N[j] tb = T[b] if j == 0 or len(tb) != 1: continue m = mul(b, a) tm = T[m] print 'From Cell', ta, ' Times ',tb, 'Moves To', tm def SingleLetterAssociativeCheck(n): alfa = Alphabet(n) N = [BasisVec(n, i) for i in range(n)] D, T = {}, {} left2right = AssignNames(D, T, N, alfa) print '============= AssociativeCheck: n=', n for i in range(n): a = N[i] ta = T[a] print for j in range(n): b = N[j] tb = T[b] if j == 0 or len(tb) != 1: continue m = mul(b, a) tm = T[m] #print ta, tb, tm # Conjecture: count moves until multiplier is in place, then anihilate. jumps = sum([(e > tb) for e in ta]) if jumps: tp = ta[:-jumps] + tb.upper() + ta[-jumps:] else: tp = ta + tb.upper() print ta, tb, jumps, tp, '......', tm anihilate = 0 after = tp for k in range(len(tp)-1): if tp[k].lower() == tp[k+1].lower(): after = "" + tp[:k] + tp[k+2:] anihilate += 1 break strikes = anihilate + jumps print ta, tb, jumps, tp, '......', anihilate, after, strikes, '...', tm # Test our conjecture: odd strikes implies assert (0 != ((strikes) & 1)) == tm.startswith('-'), (anihilate, jumps, tm) def MultiLetterMultiply(n): alfa = Alphabet(n) N = [BasisVec(n, i) for i in range(n)] D, T = {}, {} left2right = AssignNames(D, T, N, alfa) print '============= AssociativeCheck: n=', n for i in range(n): a = N[i] ta = T[a] print for j in range(n): b = N[j] tb = T[b] if j == 0: continue m = mul(b, a) tm = T[m] print '%8s %8s %8s' % (ta, tb, tm) SingleLetterMoves(32) sys.exit(0) MultiLetterMultiply(32) # sys.exit(0) # for n in [2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]: # But not 128! # for n in [2, 4, 8, 16, 32, 64, 128]: for n in [2, 4, 8, 16, 32, 64]: SingleLetterAssociativeCheck(n) # sys.exit(0) def AssociativeCheck(n): alfa = Alphabet(n) N = [BasisVec(n, i) for i in range(n)] D, T = {}, {} left2right = AssignNames(D, T, N, alfa) print '============= AssociativeCheck: n=', n for i in range(n): a = N[i] ta = T[a] if len(ta) != 2: continue for j in range(n): b = N[j] tb = T[b] if len(tb) != 2: continue for k in range(n): c = N[k] tc = T[c] if len(tc) != 2: continue # (a * b) * c left = mul(c, mul(b, a)) # a * (b * c) right = mul(mul(c, b), a) if left == right: print 'okay: (%s * %s) * %s == %s * (%s * %s) == %s' % (ta, tb, tc, ta, tb, tc, T[left]) elif left == neg(right): print 'NEG : (%s * %s) * %s == neg( %s * (%s * %s)) == %s ... %s * %s = %s ... %s * %s = %s' % (ta, tb, tc, ta, tb, tc, T[left], ta, tb, T[mul(b, a)], tb, tc, T[mul(c, b)], ) else: raise Exception( 'DIFF: %s = (%s * %s) * %s != %s * (%s * %s) = %s' % (T[left], ta, tb, tc, ta, tb, tc, T[right]) ) AssociativeCheck(32) # sys.exit(0) def PrintTable(n, ht=None, only=None, candy=None): alfa = Alphabet(n) N = [BasisVec(n, i) for i in range(n)] D, T = {}, {} left2right = AssignNames(D, T, N, alfa) candyTmp = {} print '=============================' print '==== Table n = %d' % n if ht: print >>ht, '' Right = dict([(i, 0) for i in range(n)]) Wrong = dict([(i, 0) for i in range(n)]) # Pink for wrong, lightgreen for right. for i in range(n): a = N[i] ta = T[a] if ht: print >>ht, '' % repr((i, a, T[a])) print for j in range(n): b = N[j] tb = T[b] if only: #print (n, i, j, tb, only), tb in only if j!=0 and tb not in only: continue prod = mul(b, a) # Proper multiplication. jam = N[0] # Jamming multiplication. for c in T[a] + T[b]: if c == '-': jam = neg(jam) else: jam = mul(D[c], jam) print '%6s * %6s = %6s [ %s ] %s' % (T[a], T[b], T[prod], T[jam], prod == jam) assert prod == jam or prod == neg(jam) Right[j] += int(prod == jam) Wrong[j] += int(prod != jam) if ht: print >>ht, '' # The right/wrong count. for j in range(n): b = N[j] tb = T[b] if only: if j!=0 and tb not in only: continue if ht: print >>ht, '' # Repeat the column header as a footer. for j in range(n): b = N[j] tb = T[b] if only: if j!=0 and tb not in only: continue if ht: print >>ht, '
%d,%d' % ( ' bgcolor="gray" ' if Right[j]==16 else '', Right[j], Wrong[j]) if ht: print >>ht, ' %s ' % ( 'lightgreen' if prod==jam else 'pink', T[prod], repr((j, b, T[b]))) if candy: for k, v in candy.items(): print k, v, tb, prod, jam, candyTmp if tb in v and prod != jam: candyTmp[k] = candyTmp.get(k, {}) candyTmp[k][ta] = candyTmp[k].get(ta, []) candyTmp[k][ta].append(tb) if ht: print >>ht, '