Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"
 
PerlMonks  

Re: Boolean math: Fill in the blanks.

by repellent (Priest)
on Oct 12, 2008 at 01:55 UTC ( #716647=note: print w/ replies, xml ) Need Help??


in reply to Boolean math: Fill in the blanks.

Very interesting topic!

I see an overall pattern, which I would like to share :-)

First, a few basic observations:

  • There seems to be a certain symmetry evident from how R & R results in 8 bits set on average (halfway between 1 and 16) versus R | R resulting in 24 bits set on average (halfway between 16 and 32). I'll be sure to make my hypothesis symmetrical, in that regard.
  • If we apply AND, the average bits set goes down due to higher likelihood of 0 bits swallowing the 1 bits. Conversely, if we apply OR, the average bits set goes up due to higher likelihood of 1 bits overriding the 0 bits.
  • Non-associative rules apply for AND and OR:

      ( (A & B) | C )  !=  ( A & (B | C) )

    So evaluating the expression from left-to-right is important! Update: Perl gives precedence to the & operator over |

Hypothesis:

Each AND/OR operation is evaluated in the following way:
    ( <left_gained_avg_bits_set> <op> <right_modifier> ) = <resulting_avg_bits_set>
Whenever an AND/OR <op> is applied, it induces a change to the already gained average bits on the left-side. That change is a multiplicative factor determined by the average bits set on the right-side:

    right_mod_factor = right_avg_set_bits / total_bits

Cases:

For <op> = AND, we would take right_mod_factor and multiply it with left_avg_bits_set to get <resulting_avg_bits_set>. Examples:
    R & (R & R) => 16 * (8 / 32) = 4 bits set on average

    (R | R) & (R & R & R) => 24 * (4 / 32) = 3 bits set on average

That is, if there are more bits set on average on the AND right-side, there will be less chance of swallowing, so more bits are set on average in the result.

Conversely, for <op> = OR, we would take right_mod_factor and multiply it with left_avg_unset_bits. Then, take that result and add it to left_avg_set_bits to get <resulting_avg_bits_set>. Examples:
    R | (R | R) => 16 + 16 * (24 / 32) = 28 bits set on average [second 16 is # of avg unset bits]

    (R | R) | (R & R & R) => 24 + 8 * (4 / 32) = 25 bits set on average

    R & R & R | R | R = (R & R & R) | (R | R) => 4 + 28 * (24 / 32) = 25 bits set on average
    or
    R & R & R | R | R = (R & R & R) | R | R => 4 + 28 * (16 / 32) + 14 * (16 / 32) = 25 bits set on average [got 14 from 32 - ( 4 + 28 * (16 / 32) )]

That is, if there are more bits set on average on the OR right-side, there will be more chance of overriding, so more bits are set on average in the result.

Conclusion:

So, following my pattern hypothesis, I see some inconsistent results in your "full set". For instance, 7 of ( R & R | R & R ) & R evaluates to 5 bits set on average. Attention has to be paid to precedence of AND/OR evaluations. Also, 22 & 26 are the same, when 22 of R & R | R | R evaluates to 26 bits set on average.

There may be some fallacy in my hypothesis, so feedback is welcomed :)

So, given the following legend:
    n = total # bits per sample L1 = # bits set on average on left-side of AND/OR L0 = # bits unset on average on left-side of AND/OR = n - L1 R1 = # bits set on average on right-side of AND/OR

we can derive a set of equations to calculate the resulting average bits set for each AND/OR operation:
    AND : L1 * R1 / n OR : L1 + L0 * R1 / n = L1 + (n - L1) * R1 / n = L1 + R1 - L1 * R1 / n = L1 * ( 1 - R1 / n ) + R1


Comment on Re: Boolean math: Fill in the blanks.
Select or Download Code
Re^2: Boolean math: Fill in the blanks.
by BrowserUk (Pope) on Oct 12, 2008 at 08:25 UTC
    Conclusion: ... I see some inconsistent results ... 7 of ( R & R | R & R ) & R evaluates to 5 bits set on average.

    If you plug ( R & R | R & R ) & R into the OP code and run it a few times, you'll see that the average does approximate 7:

    C:\test>booleanBuk -N=1e2 7.02 C:\test>booleanBuk -N=1e2 6.88 C:\test>booleanBuk -N=1e2 7.06 C:\test>booleanBuk -N=1e2 7.06 C:\test>booleanBuk -N=1e2 6.92 C:\test>booleanBuk -N=1e2 7.08

    And as you increase the number of iterations, the more closely the observations coincide with the theoretical value:

    C:\test>booleanBuk -N=1e5 7.00138 C:\test>booleanBuk -N=1e5 6.98986 C:\test>booleanBuk -N=1e5 6.99812 C:\test>booleanBuk -N=1e5 7.00729 C:\test>booleanBuk -N=1e6 6.994402 C:\test>booleanBuk -N=1e6 7.002038

    That's how I like my proofs. Tangible :)

    Sorry if I have misunderstood your hypothesis.


    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.
      But plug in
        (( R & R ) | R ) & R & R

      into the OP code and it tends towards 5, which was how I was interpreting the expression:
        ( R & R | R & R ) & R

      My mistake. Perl evaluates ( R & R | R & R ) & R as ( (R & R) | (R & R) ) & R and that, according to my hypothesis, results in 7 bits set on average.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (13)
As of 2014-07-10 13:35 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    When choosing user names for websites, I prefer to use:








    Results (211 votes), past polls