Re: Simplify needs ages to finish
- To: mathgroup at smc.vnet.net
- Subject: [mg44792] Re: Simplify needs ages to finish
- From: Don Taylor <dont at agora.rdrop.com>
- Date: Thu, 27 Nov 2003 11:38:16 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
Sorry to trouble you but Newsgroups.com appears to have broken moderation
again, We got them to fix this once and I have no idea what they did now.
Would you be so kind and post this as a follow-up to the recent posting
with this subject line? It was posted a few days ago.
Thank you
In comp.soft-sys.math.mathematica you write:
>I've got the following simple (well, IMO) boolean equations and can't
>believe that it takes more than 2 hours on an Intel(R) Xeon(TM) CPU
>2.00GHz to evaluate the last output: foo[a1, a2, a3, a4, b1, b2, b3, b4]
>I'm using mathematica 4.1.
..
>foo[a1_, a2_, a3_, a4_, b1_, b2_, b3_, b4_] :=
> Simplify[Xor[oparity[a1, a2, a3, a4, b1, b2, b3, b4],
> !oparity[!a1, !a2, !a3, !a4, !b1, !b2, !b3, !b4]]];
>foo[a1, a2, a3, a4, b1, b2, b3, b4]
I fiddled with this for a while. Finally I wrote some really awful code
and created an 8-variable k-map for foo[]. This evaluates in seconds.
I hope I haven't made a mistake in this.
This needs just the right fixed width font and squint your eyes really
tight to see the pretty pattern that is hiding inside his data,
substituting True->1 and False->0.
{{1,0,1,1,1,0,0,1,1,0,1,1,1,1,0,1},
{0,1,1,1,0,1,1,0,0,1,1,1,1,1,1,0},
{1,1,1,0,0,1,1,0,1,1,1,0,0,1,1,1},
{1,1,0,1,1,0,0,1,1,1,0,1,1,0,1,1},
{1,0,0,1,1,0,1,1,1,1,0,1,1,0,1,1},
{0,1,1,0,0,1,1,1,1,1,1,0,0,1,1,1},
{0,1,1,0,1,1,1,0,0,1,1,1,1,1,1,0},
{1,0,0,1,1,1,0,1,1,0,1,1,1,1,0,1},
{1,0,1,1,1,1,0,1,1,0,1,1,1,0,0,1},
{0,1,1,1,1,1,1,0,0,1,1,1,0,1,1,0},
{1,1,1,0,0,1,1,1,1,1,1,0,0,1,1,0},
{1,1,0,1,1,0,1,1,1,1,0,1,1,0,0,1},
{1,1,0,1,1,0,1,1,1,0,0,1,1,0,1,1},
{1,1,1,0,0,1,1,1,0,1,1,0,0,1,1,1},
{0,1,1,1,1,1,1,0,0,1,1,0,1,1,1,0},
{1,0,1,1,1,1,0,1,1,0,0,1,1,1,0,1}}
Even easier to see, comma->space and True->. and False->0.
{{. 0 . . . 0 0 . . 0 . . . . 0 .}
{0 . . . 0 . . 0 0 . . . . . . 0}
{. . . 0 0 . . 0 . . . 0 0 . . .}
{. . 0 . . 0 0 . . . 0 . . 0 . .}
{. 0 0 . . 0 . . . . 0 . . 0 . .}
{0 . . 0 0 . . . . . . 0 0 . . .}
{0 . . 0 . . . 0 0 . . . . . . 0}
{. 0 0 . . . 0 . . 0 . . . . 0 .}
{. 0 . . . . 0 . . 0 . . . 0 0 .}
{0 . . . . . . 0 0 . . . 0 . . 0}
{. . . 0 0 . . . . . . 0 0 . . 0}
{. . 0 . . 0 . . . . 0 . . 0 0 .}
{. . 0 . . 0 . . . 0 0 . . 0 . .}
{. . . 0 0 . . . 0 . . 0 0 . . .}
{0 . . . . . . 0 0 . . 0 . . . 0}
{. 0 . . . . 0 . . 0 0 . . . 0 .}}
Now Simplify is NEVER going to recognize this pattern and produce
something dramatically simpler. But I think that if you stare at
the k-map for a while you might be able to come up with a much
simpler expression than you started with. I didn't expect to have
this much luck with this.
I swapped an email or two with the original poster and his real
problem is far larger than this. But with this promising start
I think he might have a non-zero chance with his problem now.
Note: Hasn't anyone written Karnaugh Map functions for Mathematica?
I googled around for Mathematica logic reduction stuff and had no success.