Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?
 
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)))


Comment on Re: Boolean math: Fill in the blanks.
Select or Download Code
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.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (9)
As of 2015-07-31 17:28 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (279 votes), past polls