#2821 zhegalkin_form takes a very long or infinite time

[Robert Dodier]

zhegalkin_form in share/logic takes a very long or infinite time for some relatively simple problems. I don't know what to expect for how the run time should scale, but this seems like a bug. E.g.:

foo : (a or b or c or d) and ((not a) or b or c or d) and ((not a) or (not b) or c or d)
 and ((not a) or (not b) or (not c) or d) and ((not a) or (not b) or (not c) or (not d))
 and ((not a) or (not b) or (not d) or c) and ((not a) or (not c) or b or d) and ((not a) or (not c) or (not d) or b)
 and ((not a) or (not d) or b or c) and ((not c) or a or b or d) and ((not c) or (not d) or a or b) $
load (logic);
zhegalkin_form (foo);
   => seems to run indefinitely

[Stavros Macrakis]

Yes, the algorithm is very slow and should be improved, but I don't think it's buggy.

A workaround in this case is lreduce(lambda([q,r],zhegalkin_form(q and r)),args(foo)). rreduce is a bit faster, tree_reduce is a bit slower. In general, the order can be critical.

Of course, in general, the size of the Z form of an expression is exponential in the size of the input: Z(or(a[i],i,1,n)) has 2^n-1 terms, so both intermediate and final expression blow-up is a very real possibility.