BrowserUk has asked for the wisdom of the Perl Monks concerning the following question:
If you pick a bunch of random 32-bit values and and average the number of bits set, if your PRNG is any good, the average will tend toward 16 (50% of 32).
Update: swapped AND & OR in the descriptions of the next two examples as pointed out by GrandFather++
If you pick another set, but this time bit-wise AND each pair of values together, and this time average the number of bits set in the results, the average will tend toward 8 (25%).
Do the same thing once more, this time bit-wise ORing each pair and the average number of bits in the results will tend toward 24 (75%).
By extending the number of values you combine to derive each result, whilst varying the sequence of AND & OR operations you use to combine them, you can derive sequences of values who's average number of bits tends toward each of the ordinal values 1 through 31. For example, using R to represent a random unsigned integer in the range 0 .. 2**32, you can derive an average that tends toward 1 by combining 5 R using AND:
#! perl -slw use strict; use Math::Random::MT qw[ rand ]; sub R(){ rand( 0xFFFFFFFF ) } our $N ||= 1000; my $t = 0; for ( 1 .. $N ) { $t += unpack '%32b*', pack 'V', R & R & R & R & R; } print $t / $N; __END__ C:\test>junk7 1.029 C:\test>junk7 1.019 C:\test>junk7 1.014 C:\test>junk7 1.031 C:\test>junk7 0.985 C:\test>junk7 0.964
If you alternatively OR 5 R together(substitute pack 'V', R | R | R | R | R; above), the average tends toward 31:
C:\test>junk7 30.979 C:\test>junk7 31.028 C:\test>junk7 31.023
I've found some patterns in this. For example, to obtain the low order odd averages, you take the equation for double the value and apply & R to it's result. eg. to get 14, I have R & R | R & R, so to get 7 I use ( R & R | R & R ) & R. but that runs out for odd values greater than 15.
I've managed to find most of them through a combination of recognising some patterns and trial and error:
00 0.00% => 0 1 3.12% => R & R & R & R & R 2 6.25% => R & R & R & R 3 9.37% => ( R | R ) & R & R & R 4 12.50% => R & R & R 5 15.62% => ( R & R | R ) & R & R 6 18.75% => (R | R) & R & R 7 21.87% => ( R & R | R & R ) & R 8 25.00% => R & R 9 28.12% => (R & R & R | R ) & R ## Originally omitted. 10 31.25% => ( R & R | R ) & R 11 34.37% => ( ( R | R ) & R | R ) & R 12 37.50% => ( R | R ) & R 13 40.62% => ( R & R | R | R ) & R 14 43.75% => R & R | R & R 15 46.87% => ( R | R | R | R ) & R 16 50.00% => R 17 53.12% => R & R & R & R | R 18 56.25% => R & R & R | R 19 59.37% => R & R & ( R | R ) | R 20 62.50% => R & R | R 21 65.62% => ( R & R | R ) & R | R ## By [psini] 22 68.75% => R & R | R | R ## By [psini] 23 71.87% => ( R & R | R & R ) | R ## By [hawtin] 24 75.00% => R | R 25 78.12% => R & R & R | R | R 26 81.25% => R & R | R | R 27 84.37% => ( R | R ) & R | R | R ## By [psini] 28 87.50% => R | R | R 29 90.62% => R & R | R | R | R 30 93.75% => R | R | R | R 31 96.87% => R | R | R | R | R 32 100.00% => 0xffffffff
but 3 values, 21, 23, & 27 elude me. Update: I now have the 'full set', but there is an auxillary, and much harder challenge in Re^4: Boolean math: Fill in the blanks. for those will real mathematical & perl aptitude!
Firstly, I wonder if anyone can fill in those blanks?
Secondly, and more intellectually satisfying, is can anyone see an overall pattern that they can describe?
Finally, I do have a real use for this. It is not just intellectual curiosity. Thanks.
|
---|
Replies are listed 'Best First'. | |
---|---|
Re: Boolean math: Fill in the blanks.
by psini (Deacon) on Oct 10, 2008 at 09:53 UTC | |
by pjotrik (Friar) on Oct 10, 2008 at 10:47 UTC | |
by BrowserUk (Patriarch) on Oct 10, 2008 at 10:23 UTC | |
by psini (Deacon) on Oct 10, 2008 at 10:45 UTC | |
by BrowserUk (Patriarch) on Oct 10, 2008 at 11:07 UTC | |
by pjotrik (Friar) on Oct 10, 2008 at 13:56 UTC | |
| |
by BrowserUk (Patriarch) on Oct 10, 2008 at 10:55 UTC | |
Re: Boolean math: Fill in the blanks.
by hawtin (Prior) on Oct 10, 2008 at 09:54 UTC | |
by BrowserUk (Patriarch) on Oct 10, 2008 at 11:36 UTC | |
by psini (Deacon) on Oct 10, 2008 at 10:12 UTC | |
by hawtin (Prior) on Oct 10, 2008 at 11:21 UTC | |
by BrowserUk (Patriarch) on Oct 10, 2008 at 10:17 UTC | |
Re: Boolean math: Fill in the blanks.
by gone2015 (Deacon) on Oct 10, 2008 at 11:37 UTC | |
by BrowserUk (Patriarch) on Oct 10, 2008 at 11:53 UTC | |
Re: Boolean math: Fill in the blanks.
by repellent (Priest) on Oct 12, 2008 at 01:55 UTC | |
by BrowserUk (Patriarch) on Oct 12, 2008 at 08:25 UTC | |
by repellent (Priest) on Oct 12, 2008 at 16:54 UTC | |
Re: Boolean math: Fill in the blanks.
by JavaFan (Canon) on Oct 10, 2008 at 20:15 UTC | |
by BrowserUk (Patriarch) on Oct 10, 2008 at 21:55 UTC |