Path: ...!weretis.net!feeder8.news.weretis.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Paul <nospam@needed.invalid>
Newsgroups: comp.lang.c
Subject: Re: help with a logic algorithm
Date: Thu, 4 Apr 2024 10:03:54 -0400
Organization: A noiseless patient Spider
Lines: 175
Message-ID: <uumc0c$mhc6$1@dont-email.me>
References: <uuhr89$3e337$1@dont-email.me>
 <20240403143329.803ffa6eb0f1e166b4f3e4e0@g{oogle}mail.com>
 <f616e013-1d5e-41b6-ae9f-841f278d120e@gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Date: Thu, 04 Apr 2024 14:03:57 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="d545400f7190050e147e05d12d07dcf4";
	logging-data="738694"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+5eQo4b3S/wsQ06pGboy1qeQX2AHDs+yU="
User-Agent: Ratcatcher/2.0.0.25 (Windows/20130802)
Cancel-Lock: sha1:iVtQ53AHV8tr8p4NoVvwKAqsDZ0=
In-Reply-To: <f616e013-1d5e-41b6-ae9f-841f278d120e@gmail.com>
Content-Language: en-US
Bytes: 7314

On 4/3/2024 8:33 AM, Thiago Adams wrote:
> On 03/04/2024 08:33, Anton Shepelev wrote:
>> Thiago Adams:
>>
>>> I need an algorithm that finds the possible states of
>>> variables used in "ifs"
>>
>> The industrial approach (e.g. from digital circuitry) is to
>> convert the expression into a minimal sum of truth
>> constituents.  There are several algorithms to do so
>> efficiently, i.e. to find the minimal coverage of the truth
>> table by truth constituents. The only ones I know are by a
>> Russian author published in a Russian book by logic, so I
>> cannot provide a useful reference.
>>
>> A family of appraches is based on the Karnaugh map:
>>
>>    https://en.wikipedia.org/wiki/Karnaugh_map
>>
>> If you expressions are simple, however, a direct enumaration
>> of 2^n combinations could work.
>>
> 
> I think the number of variables will be small.
> 
> if (a) ...
> if (a && b) ...
> if (a || b) etc..
> 
> But even if I have let's say 10 variables, then 2^10 = 1024 still something fast to do.

I hope your problem is not as you describe it.

Performance will suck, when one of your customers (on purpose),
tests it with twenty variables, just so that individual can
file a bug report with your company :-) You know there are
people who do that sort of thing.

One of your posts suggested you were building a boolean expression
evaluator of some sort. For an unspecified purpose.

Logic manipulation is used for at least logic design,
and things like Quine McClusky helped minimize logic
gates in the jelly bean era. I was taught QM and Petrics
in uni, but no code was available to play with it, and
doing it by hand is, well, work.

One of the first things I did, when I got a job, is I got a
copy of QM from another engineer, and I ported it from C to Pascal
for the personal computer on my desk (which didn't have a  C compiler).

   https://en.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algorithm

My preferred notation would be like this. ABC on the vertical,
DEF variables horizontal. DEF spanning 000,001, .. 111 . And
the vertical ABC values 000..111 being spelled out explicitly.
The purpose of using a notation like this, is fewer lines of input.
Any sort of rectangular array or square array, will do.
                          _
ABC|DEF               A + ABCDEF  ==> A + BCDEF
-----------------
000|0 0 0 0 0 0 0 0
001|0 0 0 0 0 0 0 0
010|0 0 0 0 0 0 0 0
011|0 0 0 0 0 0 0 1
100|1 1 1 1 1 1 1 1
101|1 1 1 1 1 1 1 1
110|1 1 1 1 1 1 1 1
111|1 1 1 1 1 1 1 1

Parity trees are not reducible, which is one of your test
cases when writing code. A parity tree has diagonals in it
as a pattern. Like a garden trellis made of wood.

*******

There is a sample QM here.

The way the program inputs data, determines how useful it is
for visualization. This program has an emphasis on symbolic
manipulation, but for I/O, you could not handle a very
big problem this way. For my table of a six variable function,
the data input is only eight lines or so. The EXE here would
be 64 inputs, and the counting sequence and position of MSB:LSB
when counting, is the reverse of what I would use. But it
doesn't really matter how you fill the table, before the code runs.
Naturally, the O() of the method sucks, and if you have an extreme
number of variables for this sort of thing, and your users expect
"real time" response, this will be too slow. For evaluating two
variables, the execution time is too small to measure. With maybe
a dozen variables, my poor desktop computer back then needed
fifteen minutes to do the job.

https://sourceforge.net/projects/mini-qmc/

   https://sourceforge.net/projects/mini-qmc/files/

   Name: quine_mc_cluskey_v0.2.zip
   Size: 56368 bytes (55 KiB)
   SHA256: 5A415B4012C53623A7351F7E1B55C3ED5D6EB72A35DF735D59886FAF6FDA13E7

*******
File: readme.txt

Sample
======

Here a simple sample for a NAND operator:

Enter number of variables: 2
Please enter desired results: ( 0 or 1)
                                       _     _   __
yz = 0              yz|     Input is:  yz + yz + yz          ----+
                    ----                                         |
_                   11|0                                         |
yz = 1              01|1                                         |
                    10|1                                         +--- I added this section
 _                  00|1                                         |    for reference and
yz = 1             /  \                                          |    perspective
                  LSB MSB  CountDown sequence                    |
__               (normally it would be MSB:LSB and count up)     |
yz = 1                                                       ----+


Result:

_   _
y + z

*******

What you're doing in your ELSE clause is:    Input is: yz

yz = 1

_
yz = 0

 _
yz = 0

__
yz = 0


And the output would be yz.

But at least you can see there might be a pattern there.

I tested the program with an XOR pattern for input, and
it does not print out a logic equation with an XOR as
a compact notation.

For a practical QM program then, the I/O, the material
for visualization, for seeing what was done, that is just
as important as the grinding process.

Notice in the Wikipedia article, one of the problems has
two output solutions. You pick the solution with a "shared term"
you just happens to be generated elsewhere in the circuit :-)
A circuit design can have many logic trees, and some of
the trees may intersect and be reduced by the sharing you
discover.

Of course humans don't do this any more. Logic is defined
in Verilog and VHDL files, CAD tools do the minimization,
find the shared term, floor plan, use simulated annealing
for the layout, pour logic gates into a rectangular space
using a serpentine shaped pattern. And it's all done
while you drink coffee and look out the window.

But the hard work, is algorithm definition, and the test benches
for boundary conditions are the "tax" you pay for being so clever.

    Paul