# Multiply # multiply two numbers (written as a sum of ones) # # Input 11..11011..11 # # Output 11..11 (product) # St R W M New (0,1, ,1,r) (0,0, ,2,r) # Fix this (1,0, ,3,r) # Zero here -- clean up! (1,1, ,4,r) # Erase this one, copy y (4,1,1,4,r) # Skip remainder of x. (4,0,0,5,r) # At beginning of y (5,1,j,6,r) (5,x,x,7,l) (6, ,x,8,l) # Wrote the one (as an x) (6,1,1,6,r) (6,x,x,9,r) (9,1,1,9,r) (9, ,1,10,l) (10,1,1,10,l) (10,x,x,8,l) (8,1,1,8,l) # Move left until we hit a j (8,j,j,5,r) (7,j,1,7,l) # We've finished the copy. Rewrite j as 1 (7,0,0,7,l) (7,1,1,7,l) (7, , ,1,r) (3,1,1,3,r) (3,x,1,11,l) #11 1 1 l 11 #11 _ _ r 12 #12 1 _ l 12 (2,1, ,2,r) #14 1 1 l 14 #14 j j r 4