#! 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.012
+000
2 : (R) & ((R) & ((R) & (R)))                          : result: 2.036
+000
3 : (R) & ((R) & ((R) & ((R) | (R))))                  : result: 3.038
+000
4 : (R) & ((R) & (R))                                  : result: 4.060
+000
5 : (R) & ((R) & ((R) | ((R) & (R))))                  : result: 5.088
+000
6 : (R) & ((R) & ((R) | (R)))                          : result: 6.012
+000
7 : (R) & ((R) & ((R) | ((R) | (R))))                  : result: 6.956
+000
8 : (R) & (R)                                          : result: 8.116
+000
9 : (R) & ((R) | ((R) & ((R) & (R))))                  : result: 8.990
+000
10 : (R) & ((R) | ((R) & (R)))                          : result: 9.98
+4000
11 : (R) & ((R) | ((R) & ((R) | (R))))                  : result: 10.9
+11000
12 : (R) & ((R) | (R))                                  : result: 12.1
+65000
13 : (R) & ((R) | ((R) | ((R) & (R))))                  : result: 12.9
+99000
14 : (R) & ((R) | ((R) | (R)))                          : result: 13.9
+51000
15 : (R) & ((R) | ((R) | ((R) | (R))))                  : result: 15.0
+19000
16 : R                                                  : result: 16.0
+17000
17 : (R) | ((R) & ((R) & ((R) & (R))))                  : result: 16.9
+72000
18 : (R) | ((R) & ((R) & (R)))                          : result: 18.0
+53000
19 : (R) | ((R) & ((R) & ((R) | (R))))                  : result: 18.7
+78000
20 : (R) | ((R) & (R))                                  : result: 19.9
+10000
21 : (R) | ((R) & ((R) | ((R) & (R))))                  : result: 21.0
+56000
22 : (R) | ((R) & ((R) | (R)))                          : result: 22.0
+41000
23 : (R) | ((R) & ((R) | ((R) | (R))))                  : result: 22.9
+89000
24 : (R) | (R)                                          : result: 24.0
+85000
25 : (R) | ((R) | ((R) & ((R) & (R))))                  : result: 24.9
+59000
26 : (R) | ((R) | ((R) & (R)))                          : result: 26.1
+71000
27 : (R) | ((R) | ((R) & ((R) | (R))))                  : result: 27.0
+23000
28 : (R) | ((R) | (R))                                  : result: 27.9
+04000
29 : (R) | ((R) | ((R) | ((R) & (R))))                  : result: 28.9
+85000
30 : (R) | ((R) | ((R) | (R)))                          : result: 29.9
+78000
31 : (R) | ((R) | ((R) | ((R) | (R))))                  : result: 30.9
+72000
[download]