satdiv.rb

def fsmdiv(r)
	
	fsm = {}

	r.times \
	{
		|x|
		x0 = (x * 2) % r
		x1 = (x * 2 + 1) % r
		fsm[[x, 0]] = x0
		fsm[[x, 1]] = x1
	}

	return fsm
	
end

def newvar(c, v)
	
	l = []
	c.times { |x| n = $v.size; $v[n] = "#{v}_#{x}"; l << n }
	return l
end

def bits(v, s)
	
	b = sprintf("%0#{v.size}b", s)
	i = -1
	return v.map { |x| i += 1; x * [-1, 1][b[i, 1].to_i] }
	
end

def equalbits(v1, v2, s1, s2, x)

	l = bits(v1, s1).map { |x| -x }
	bits(v2, s2).each \
	{
		|y|
		puts([[-x] + l + [y]].join(" "))
	}
	
#	$stderr.puts("\t#{s1} => #{s2} #{v1} #{v2} if #{x}")
end

def applyfsm1(x, i, fsm, v1)

	v2 = newvar(v1.size, "s#{i + 1}")
	fsm.each \
	{
		|a, s2|
		s1, b = a
		equalbits(v1, v2, s1, s2, x * [-1, 1][b])
	}
	return v2
end

def applyfsm(fsm, w, r)
	

	v = (1..w).to_a
	w2 = r.to_s(2).length
	v2 = newvar(w2, 's0')
	v2.each { |x| p(-x) }

	v.each_with_index \
	{
		|x, i|
		v2 = applyfsm1(x, i, fsm, v2)
	}
end

def fsmrun(fsm, w, r)
	
	w2 = r.to_s(2).length
	x = sprintf("%0#{w}b", z = rand(2 ** w))
	l = x.split('').map { |x| x.to_i }

	l.each_with_index { |x, i| p((i + 1) * [-1, 1][x]) }
	
	l2 = [nil] + l
	l2 += [0] * w2
	s = 0
	l.each \
	{
		|b|
		s = fsm[[s, b.to_i]]
		l2 += sprintf("%0#{w2}b", s).split('').map { |x| x.to_i }
	}
	$stderr.puts(["w= #{w}", "z= #{z}", "r= #{r}", "z % r= #{z % r}", "s= #{s}"].inspect)
	
	l1 = ([(0...$v.size).to_a] + [l2, $v]).transpose[1..-1]
#	l1.each { |x| $stderr.puts(x.inspect) }

	l1.map! { |x| x[0] * [-1, 1][x[1]] }
	
	$stderr.puts(l1.inspect)

	return s
end

r = [7, 11, 13][rand(3)]
fsm = fsmdiv(r)

$l = []
$v = [nil]

w = 5
v = newvar(w, 'n')

applyfsm(fsm, w, r)


fsmrun(fsm, w, r)