#! perl -slw
use strict;
use Math::Random::MT qw[ rand ];

sub R(){ rand( 0xFFFFFFFF ) }

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

    return ["R", 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;
}

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] = $sp_expr;
    }
}

our $N ||= 1000;

for(my $i=1;$i<32;$i++) {
    my $exp = $got[$i];
    my $sub = eval "sub { pack 'V', $exp }" or die $!;;

    my $t = 0;
    for ( 1 .. $N ) {
        $t += unpack '%32b*', $sub->();
    }
    printf "$i : %-50s : result: %f\n", $exp, $t / $N;
}

__END__
C:\test>hawtinBooleanMath.pl
1 : (R) & ((R) & ((R) & ((R) & (R))))                  : result: 1.012000
2 : (R) & ((R) & ((R) & (R)))                          : result: 2.036000
3 : (R) & ((R) & ((R) & ((R) | (R))))                  : result: 3.038000
4 : (R) & ((R) & (R))                                  : result: 4.060000
5 : (R) & ((R) & ((R) | ((R) & (R))))                  : result: 5.088000
6 : (R) & ((R) & ((R) | (R)))                          : result: 6.012000
7 : (R) & ((R) & ((R) | ((R) | (R))))                  : result: 6.956000
8 : (R) & (R)                                          : result: 8.116000
9 : (R) & ((R) | ((R) & ((R) & (R))))                  : result: 8.990000
10 : (R) & ((R) | ((R) & (R)))                          : result: 9.984000
11 : (R) & ((R) | ((R) & ((R) | (R))))                  : result: 10.911000
12 : (R) & ((R) | (R))                                  : result: 12.165000
13 : (R) & ((R) | ((R) | ((R) & (R))))                  : result: 12.999000
14 : (R) & ((R) | ((R) | (R)))                          : result: 13.951000
15 : (R) & ((R) | ((R) | ((R) | (R))))                  : result: 15.019000
16 : R                                                  : result: 16.017000
17 : (R) | ((R) & ((R) & ((R) & (R))))                  : result: 16.972000
18 : (R) | ((R) & ((R) & (R)))                          : result: 18.053000
19 : (R) | ((R) & ((R) & ((R) | (R))))                  : result: 18.778000
20 : (R) | ((R) & (R))                                  : result: 19.910000
21 : (R) | ((R) & ((R) | ((R) & (R))))                  : result: 21.056000
22 : (R) | ((R) & ((R) | (R)))                          : result: 22.041000
23 : (R) | ((R) & ((R) | ((R) | (R))))                  : result: 22.989000
24 : (R) | (R)                                          : result: 24.085000
25 : (R) | ((R) | ((R) & ((R) & (R))))                  : result: 24.959000
26 : (R) | ((R) | ((R) & (R)))                          : result: 26.171000
27 : (R) | ((R) | ((R) & ((R) | (R))))                  : result: 27.023000
28 : (R) | ((R) | (R))                                  : result: 27.904000
29 : (R) | ((R) | ((R) | ((R) & (R))))                  : result: 28.985000
30 : (R) | ((R) | ((R) | (R)))                          : result: 29.978000
31 : (R) | ((R) | ((R) | ((R) | (R))))                  : result: 30.972000