Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

What are the odds of two adjacent, 4-byte aligned, 32-bit values, at any random offset within the memory space of an application on a 32-bit processor, xoring to 0?

To clarify. 

                     |-any random offset in ram
- - - --------------------------------------------------------- - - -
      |    |    |    |AAAA|BBBB|    |     |    |    |    |    |
- - - --------------------------------------------------------- - - - 

AAAA XOR BBBBB == 0

[download]

Replies are listed 'Best First'.
Re: (OT): Probability problem
by moritz (Cardinal) on Mar 09, 2009 at 08:51 UTC

    .oO( why does this smell like homework? )

    Anyway: for each possible 32 bit value there is exactly one other value which XOR's it to zero, so if you assume uniform probability for all values and no correlation between adjacent words the probability is 2**(-32)

[reply]
[d/l]

      I work from home, but there is nothing academic about what I do.

      That number is good (perfect for my needs) from a purely theoretic POV, but now consider if you will the reality of a process' memory in a generic application. What influences are likey to increase the likelyhood of the occurance?

[reply]
        Well, it'll be much harder to find a theoretical model than to simply try it. Write a short program (to become on-topic again) to analyze /dev/mem, and tell us what you found.

        (Update: I tried it, and it comes with no surprise that probability is much higher than the theoretical value, because the RAM doesn't contain all that much entropy).

[reply]
[d/l]

        This, again, sounds a lot like homework. Maybe you can tell us the practical application you're using this for?

        Otherwise, it's not really hard to find the underlying assumption of moritz's statement, at least if you haven't slept through your stochastics lectures.

[reply]
Re: (OT): Probability problem
by locked_user sundialsvc4 (Abbot) on Mar 09, 2009 at 13:27 UTC

    The theoretical probability having been correctly stated already, then the pragmatic probability can only be determined through empirical observation. And, it will constantly change with the environment. Every two computers will be different.

    If you simply reduce your problem to “two adjacent words in a data-stream,” you are now talking about the same sort of problem as describing the frequency-of-occurrence of “digraphs” (two-letter groups) in a classical cryptography-type scenario. Once again, it depends upon the particular data-stream (e.g. the native language of Alice and Bob).

Re: (OT): Probability problem
by bellaire (Hermit) on Mar 09, 2009 at 13:19 UTC
    Trying to figure out what could possibly be the practical application of this problem, I can see only two possibilities:
    1. You need some event to fire with a probability of 2**-32. If that's the case, just use a real RNG rather than peeking into memory.
    2. Having two adjacent memory locations XOR to zero unexpectedly is an error case, and you want to know whether it's likely that'll happen by chance so you can decide whether to check for the error ahead of time. If that's the case, just check for the error. Error checking builds character. ;)
[reply]

Back to Seekers of Perl Wisdom