Keep It Simple, Stupid PerlMonks

### Re: Boolean math: Fill in the blanks.

by hawtin (Prior)
 on Oct 10, 2008 at 09:54 UTC ( #716407=note: print w/replies, xml ) Need Help??

in reply to Boolean math: Fill in the blanks.

Since & halves the number of 1s and | halves the number of 0s one would expect that the pattern for 1-X would just be the pattern for X with all the operators inverted:

```21 = (32 - 11) => ( ( R & R ) | R & R ) | R
27 = (32 - 5) => ( R | R & R ) | R | R

I see that 9 is also missing from your list.

I presume that the goal is to get exact ratios with the smallest number of operators? One way to explore this space is to create a Perl script to list the resulting spread for all the expressions with a certain number of operators

Update: I think this is about right (and if not then it should be fixable)

```use strict;
use warnings;

sub operations
{
my(\$num_ops) = @_;

#return (["M | M", 3 , 4], ["M & M", 1, 4])
#                                if(\$num_ops == 1);
return ["M", 1, 2] if(\$num_ops == 0);

my @result;
for(my \$i=0;\$i<\$num_ops;\$i++)
{
my @first = operations(\$i);
my @second = operations(\$num_ops - \$i - 1);
foreach my \$first_part (@first)
{
my(\$fp_expr,\$fp_top,\$fp_bot) = @{\$first_part};
foreach my \$second_part (@second)
{
my(\$sp_expr,\$sp_top,\$sp_bot) = @{\$second_part};
# Two choices & or |
# (NY + M(X-N))/(X*Y)
# (X*Y - ((X-N)Y + (Y-M)N))/(X*Y)
push @result,["(\$fp_expr) & (\$sp_expr)",
\$fp_bot*\$sp_bot -
(\$fp_bot - \$fp_top)*\$sp_bot -
(\$sp_bot - \$sp_top)*\$fp_top,
\$fp_bot*\$sp_bot],
["(\$fp_expr) | (\$sp_expr)",
\$fp_top*\$sp_bot +
\$sp_top*(\$fp_bot - \$fp_top),
\$fp_bot*\$sp_bot];
}
}
}
return @result;
}

# Update: Edited the calling routine to provide easier to use results
my @got;

foreach my \$count_expr (0..4)
{
foreach my \$expr (operations(\$count_expr))
{
my(\$sp_expr,\$top,\$bot) = @{\$expr};
\$top = \$top * (32 / \$bot);
next if(defined \$got[\$top]);

\$sp_expr =~ s/\(M\)/M/g;
\$got[\$top] = sprintf "%02d: \$sp_expr\n",\$top;
}
}

for(my \$i=1;\$i<32;\$i++)
{
print \$got[\$i];
}

Which gives results:

```01: M & (M & (M & (M & M)))
02: M & (M & (M & M))
03: M & (M & (M & (M | M)))
04: M & (M & M)
05: M & (M & (M | (M & M)))
06: M & (M & (M | M))
07: M & (M & (M | (M | M)))
08: M & M
09: M & (M | (M & (M & M)))
10: M & (M | (M & M))
11: M & (M | (M & (M | M)))
12: M & (M | M)
13: M & (M | (M | (M & M)))
14: M & (M | (M | M))
15: M & (M | (M | (M | M)))
16: M
17: M | (M & (M & (M & M)))
18: M | (M & (M & M))
19: M | (M & (M & (M | M)))
20: M | (M & M)
21: M | (M & (M | (M & M)))
22: M | (M & (M | M))
23: M | (M & (M | (M | M)))
24: M | M
25: M | (M | (M & (M & M)))
26: M | (M | (M & M))
27: M | (M | (M & (M | M)))
28: M | (M | M)
29: M | (M | (M | (M & M)))
30: M | (M | (M | M))
31: M | (M | (M | (M | M)))

Replies are listed 'Best First'.
Re^2: Boolean math: Fill in the blanks.
by BrowserUk (Pope) on Oct 10, 2008 at 11:36 UTC

Your code wasn't here the first time I replied, and having failed to achieve results with my own attempt I was dismissive. For which I apologise.

This is brilliant! I combined your generator with my test harness and got:

Now I going to look into extending that to produce a custom sub to approximate any given probability. Many thanks!

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
Re^2: Boolean math: Fill in the blanks.
by psini (Deacon) on Oct 10, 2008 at 10:12 UTC

Sorry, but it's not so simple. <s>& halves the number of 1's only if both expression are identical, same thing for |<s>.

In fact, if I'm right, your expression for 21 gives an average of 23 ones and the expression for 27 gives an average of 29.

Update: on second sight, your solution for 27 is equivalent to that given by BrowserUk for 29

Update: & doesn't half the number of 1's. The result is the product divided by 32, so it halves the number of 1's of an expression if and only if the other is R

Rule One: "Do not act incautiously when confronting a little bald wrinkly smiling man."

What I meant to convey is that if you replace all 0s with 1s and all & with | then you get the same result. If the operations are done in the same order then, I think my expression gives the results I have stated. The problem is that precedence is changing the way Perl combines the operators. When defining these expressions I should have put brackets round everything.

Re^2: Boolean math: Fill in the blanks.
by BrowserUk (Pope) on Oct 10, 2008 at 10:17 UTC
1. 21 = (32 - 11) => ( ( R & R ) | R & R ) | R actually gives 23 (which is good :)
2. 27 = (32 - 5) => ( R | R & R ) | R | R actually gives 29 which I alrady have.
One way to explore this space is to create a Perl script to list the resulting spread for all the expressions with a certain number of operators

I had a go at this, but precedence make is pretty aakward. (Eg, I was unsuccessful!)

I see that 9 is also missing from your list.

I'd missed that, but tit is an easy one: 18 = R & R & R | R so 9 = ( R & R & R | R ) & R. I'll add it in the OP.

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

Create A New User
Node Status?
node history
Node Type: note [id://716407]
help
Chatterbox?
 [LanX]: blocked by FW :( oldtechaa takes a cookie from the platter on the sideboard. [choroba]: LanX Check it on a phone :)

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (10)
As of 2017-04-26 12:10 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
I'm a fool:

Results (474 votes). Check out past polls.