They're not just any random functions. They're random functions with bugs. Testing this is always fun.
Random functions require random tests, of course.
Just like documentation: if it was hard to write, it should be hard to read.
Pseudo code for an inadequate number of tests of an imaginary model, assumed not unlike a bell-curve - your mileage WILL vary -
$fut= \&FunctionUnderTest;
my @X= map { $fut->() } 1..$N;
use Acme::Statistics; # Fantasy package that provides what I use below...
ok( abs(mean(@X)) < 0.5, "mean near 0");
ok( abs(stddev(@X) - 1) < 0.2, "StdDev near 1");
ok( abs(skew(@X) < 0.1, "symetric");
my %Count; $Count{$_}++ for @X;
ok( chisq(values %Count) > 0.9,"distribution ok");
ok( abs(corr(@X[grep { $_ % 2 } 0..$#X],
@X[grep {!($_ % 2)} 0..$#X] ))
< 0.1, "Not auto correlated even/odd");
The classical references on this are Knuth http://isbn.nu/0201896842, and then GG&M JACM 1986 and B&M SIAM JoC; ACM CALGO has good stuff buried in it too. WikiPedia has reference & short summary of the German standard for rating random functions; and the US NIST standard is voluminous, with test info.
Just remember
Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin. -- John von Neumann
Re:Writing tests for random functions
Ovid on 2006-09-19T20:56:55
Interesting. I was just talking to a coworker about that. It's been years since statistics classes and I was struggling to remember the formulae involved in calculating what I was interested in. I wasn't thinking of a distribution under a bell curve so much as I was thinking "if X might not be correct, how many times do I need to calculate X to ensure the odds of it being incorrect are acceptably minimized?" More inportantly, I can't have randomly failing tests, but I'm quite happy to have a test which statistically is less likely to fail than, say, a random power outage or some weird CPU glitch (there are algorithms which are known to be mathematically flawed but fail so seldom that the computer's more likely to break down first).
Of course, there's also a cost factor. I won't spend a million pounds if that's what it takes to ensure a test is effectively deterministic. However, I'm willing to spend more than £5. Where's the breakeven point?
In any event, thanks for the pointers!
