-- $dotat: life/find-adder.lua,v 1.1 2008/09/01 13:53:20 fanf2 Exp $
--
-- This was written by Tony Finch <dot@dotat.at>.
-- You may do anything with it, at your own risk.
--
-- This program searches for boolean functions that take three inputs
-- and produce two outputs whose combined value encodes the number of
-- true input bits. One example is the full adder; it requires 5 ALU
-- operations. This program shows that the fastest possible way to
-- compute such a function is 4 ALU operations. All the fastest such
-- functions are related to the following function by symmetry, e.g.
-- by permuting the arguments, etc.
--
--    function (a,b,c)
--       local d = X(a,b)
--       local e = X(b,c)
--       local f = X(c,d)
--       local g = V(d,e)
--       return f,g
--    end
--
-- i.e. using C operators, f = a^b^c, g = a^b | b^c. The truth table is:
--
--    a b c  f g
--    0 0 0  0 0
--    0 0 1  1 1
--    0 1 0  1 1
--    1 0 0  1 1
--    0 1 1  0 1
--    1 0 1  0 1
--    1 1 0  0 1
--    1 1 1  1 0
--
-- Tom Rokicki's bit-banging Life algorithm uses this function.
-- http://groups.google.com/group/comp.arch.embedded/msg/d835361b253897b5


-- check a function matches our requirements

local function test(str)
   local fn = assert(loadstring(str))()
   local zero = fn(0,0,0)
   local one  = fn(1,0,0)
   if    one ~= fn(0,1,0)
   or    one ~= fn(0,0,1)
   then return end
   local two  = fn(1,1,0)
   if    two ~= fn(1,0,1)
   or    two ~= fn(0,1,1)
   then return end
   local three = fn(1,1,1)
   if zero == one
   or zero == two
   or zero == three
   or one == two
   or one == three
   or two == three
   then return end
   print(zero, one, two, three, str)
end

-- ALU operations

function A(a,b)
   if a ~= 0 and b ~= 0 then
      return 1
   else
      return 0
   end
end

function V(a,b)
   if a ~= 0 or b ~= 0 then
      return 1
   else
      return 0
   end
end

function X(a,b)
   if a ~= b then
      return 1
   else
      return 0
   end
end

-- construct and test all the possible functions

local fns = { "A", "V", "X" }
local vars = { "a", "b", "c", "d", "e", "f", "g", "h" }

for fn1 = 1,3 do
   for fn2 = 1,3 do
      for fn3 = 1,3 do
         for fn4 = 1,3 do
            print(fns[fn1],fns[fn2],fns[fn3],fns[fn4],os.time())
for v1a = 1,2 do
for v1b = v1a+1,3 do
   for v2a = 1,3 do
   for v2b = v2a+1,4 do
      for v3a = 1,4 do
      for v3b = v3a+1,5 do
for vr = 4,5 do
   test("return function(a,b,c) "..
        "d="..fns[fn1].."("..vars[v1a]..","..vars[v1b]..") "..
        "e="..fns[fn2].."("..vars[v2a]..","..vars[v2b]..") "..
        "f="..fns[fn3].."("..vars[v3a]..","..vars[v3b]..") "..
        "return "..vars[vr].."+f*2 end")
end
         for v4a = 1,5 do
         for v4b = v4a+1,6 do
for vr = 4,6 do
   test("return function(a,b,c) "..
        "d="..fns[fn1].."("..vars[v1a]..","..vars[v1b]..") "..
        "e="..fns[fn2].."("..vars[v2a]..","..vars[v2b]..") "..
        "f="..fns[fn3].."("..vars[v3a]..","..vars[v3b]..") "..
        "g="..fns[fn4].."("..vars[v4a]..","..vars[v4b]..") "..
        "return "..vars[vr].."+g*2 end")
end
         end
         end
      end
      end
   end
   end
end
end
         end
      end
   end
end

-- eof