Verifying uniform distribution of random numbers
Brad Hards
bhards at bigpond.net.au
Tue Apr 9 11:55:32 EST 2002
ObCLUG:
A little while back, there was some discussion of random number generation, as
part of Nemo's bash challenge. I regret not paying more notice and asking
questions at the time, because I now need to know about this...
Problem:
I am writing unit tests for the zeroconf IP tool (zcip), and there is a spec
requirement that says "When a host wishes to configure a link-local address,
it selects an address using a pseudo-random number generator with a uniform
distribution in the range from 169.254.1.0 to 169.254.254.255."
In addition to not paying much notice this time round, I was a lousy student
of stats, and while I think that there is some statistical test
(chi-squared?) to test hypothesis about distributions, I know nothing about
it. I don't even have the textbook (which might explain why I nearly failed
stats :)
A google search showed a lot of theoretical papers (and a surprising amount of
code), but it all seems to be oriented to crypto, not simple stuff like this.
Basically, the routine I am testing generates "random" IPs in the range above.
My unit test calls that routine 100 million times, and verifies that they are
all in range. The next test to write is the "uniform distribution" bit.
The approach I have in mind is to declare an array of 65024 "bins" (one per
valid IP), and count the number of times that each IP occurs. Then do some
comparison of actual count in each bin against the expected value (1598 or so
- I'll probably tweak the number of IPs to make it match).
The question is "how close is close enough for each bin?", given that there is
no confidence levels in the IETF draft, so "something reasonable" would have
to be assumed. If anyone has played with this, I'd be keen to hear some
guidance. Code would be even more appreciated :) Code with comments about
what the results mean would be ultra-appreciated.
Brad
BTW: If anyone knows about a Netcomm RK300 modem rack, could you contact me. I
got one at the Hymans auction, claiming to be a phone system, but it was
doco-less.
More information about the linux
mailing list