Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling
 
PerlMonks  

Re: Boolean math: Fill in the blanks.

by hawtin (Prior)
on Oct 10, 2008 at 09:54 UTC ( [id://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 (Patriarch) 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 (Patriarch) 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.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://716407]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others having a coffee break in the Monastery: (3)
As of 2024-04-19 19:44 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found