search

rtoy / maxima

A Clone of Maxima's repo
Other
0 stars 0 forks source link

zhegalkin_form takes a very long or infinite time #769

Open rtoy opened 4 months ago

rtoy commented 4 months ago

Imported from SourceForge on 2024-07-03 10:32:58 Created by robert_dodier on 2014-10-16 19:21:35 Original: https://sourceforge.net/p/maxima/bugs/2821

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
rtoy commented 4 months ago

Imported from SourceForge on 2024-07-03 10:32:59 Created by macrakis on 2014-10-26 21:36:23 Original: https://sourceforge.net/p/maxima/bugs/2821/#dfb9

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.