| 1 | package Statistics::Test::RandomWalk; | ||||||||||||||
| 2 | |||||||||||||||
| 3 | 3 | ▶ | use 5.006; | ||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||
| 4 | 3 | ▶ | use strict; | ||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||
| 5 | 3 | ▶ | use warnings; | ||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||
| 6 | |||||||||||||||
| 7 | 3 | our $VERSION = '0.02'; | |||||||||||||
| 8 | |||||||||||||||
| 9 | 3 | ▶ | use Carp qw/croak/; | ||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||
| 10 | 3 | ▶ | use Params::Util qw/_POSINT _ARRAY _CODE/; | ||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||
| 11 | 3 | ▶ | use Memoize; | ||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||
| 12 | 3 | ▶ | use Math::BigFloat; | ||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||
| 13 | 3 | ▶ | use Statistics::Test::Sequence; | ||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||
| 14 | 3 | ▶ | use Class::XSAccessor { | ||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||
| 15 | 3 | constructor => 'new', | |||||||||||||
| 16 | getters => { | ||||||||||||||
| 17 | rescale_factor => 'rescale', | ||||||||||||||
| 18 | }, | ||||||||||||||
| 19 | setters => { | ||||||||||||||
| 20 | set_rescale_factor => 'rescale', | ||||||||||||||
| 21 | }, | ||||||||||||||
| 22 | 3 | }; | |||||||||||||
| 23 | |||||||||||||||
| 24 | =head1 NAME | ||||||||||||||
| 25 | |||||||||||||||
| 26 | Statistics::Test::RandomWalk - Random Walk test for random numbers | ||||||||||||||
| 27 | |||||||||||||||
| 28 | =head1 SYNOPSIS | ||||||||||||||
| 29 | |||||||||||||||
| 30 | use Statistics::Test::RandomWalk; | ||||||||||||||
| 31 | my $tester = Statistics::Test::RandomWalk->new(); | ||||||||||||||
| 32 | $tester->set_data( [map {rand()} 1..1000000] ); | ||||||||||||||
| 33 | |||||||||||||||
| 34 | my $no_bins = 10; | ||||||||||||||
| 35 | my ($quant, $got, $expected) = $tester->test($no_bins); | ||||||||||||||
| 36 | print $tester->data_to_report($quant, $got, $expected); | ||||||||||||||
| 37 | |||||||||||||||
| 38 | =head1 DESCRIPTION | ||||||||||||||
| 39 | |||||||||||||||
| 40 | This module implements a Random Walk test of a random number generator | ||||||||||||||
| 41 | as outlined in Blobel et al (Refer to the SEE ALSO section). | ||||||||||||||
| 42 | |||||||||||||||
| 43 | Basically, it tests that the numbers C<[0,1]> generated by a | ||||||||||||||
| 44 | random number generator are distributed evenly. It divides C<[0,1]> | ||||||||||||||
| 45 | into C<n> evenly sized bins and calculates the number of expected and | ||||||||||||||
| 46 | actual random numbers in the bin. (In fact, this counts the | ||||||||||||||
| 47 | cumulated numbers, but that works the same.) | ||||||||||||||
| 48 | |||||||||||||||
| 49 | =head1 METHODS | ||||||||||||||
| 50 | |||||||||||||||
| 51 | =head2 new | ||||||||||||||
| 52 | |||||||||||||||
| 53 | Creates a new random number tester. | ||||||||||||||
| 54 | |||||||||||||||
| 55 | =head2 set_rescale_factor | ||||||||||||||
| 56 | |||||||||||||||
| 57 | The default range of the random numbers [0, 1) can be rescaled | ||||||||||||||
| 58 | by a constant factor. This method is the setter for that factor. | ||||||||||||||
| 59 | |||||||||||||||
| 60 | =head2 rescale_factor | ||||||||||||||
| 61 | |||||||||||||||
| 62 | Returns the current rescaling factor. | ||||||||||||||
| 63 | |||||||||||||||
| 64 | =head2 set_data | ||||||||||||||
| 65 | |||||||||||||||
| 66 | Sets the random numbers to operate on. First argument | ||||||||||||||
| 67 | must be either an array reference to an array of random | ||||||||||||||
| 68 | numbers or a code reference. | ||||||||||||||
| 69 | |||||||||||||||
| 70 | If the first argument is a code reference, the second | ||||||||||||||
| 71 | argument must be an integer C<n>. The code reference is | ||||||||||||||
| 72 | called C<n>-times and its return values are used as | ||||||||||||||
| 73 | random numbers. | ||||||||||||||
| 74 | |||||||||||||||
| 75 | The code reference semantics are particularily useful if | ||||||||||||||
| 76 | you do not want to store all random numbers in memory at | ||||||||||||||
| 77 | the same time. You can write a subroutine that, for example, | ||||||||||||||
| 78 | generates and returns batches of 100 random numbers so no | ||||||||||||||
| 79 | more than 101 of these numbers will be in memory at the | ||||||||||||||
| 80 | same time. Note that if you return 100 numbers at once and | ||||||||||||||
| 81 | pass in C<n=50>, you will have a sequence of 5000 random | ||||||||||||||
| 82 | numbers. | ||||||||||||||
| 83 | |||||||||||||||
| 84 | =cut | ||||||||||||||
| 85 | |||||||||||||||
| 86 | 2 | ▶ | sub set_data { | ||||||||||||
|
Subroutine
set_data: called CC=4 SCAR=14.3
Pod
documented
| |||||||||||||||
| 87 | 2 | my $self = shift; | |||||||||||||
| 88 | 2 | my $data = shift; | |||||||||||||
| 89 | 2 | ▶ | if (_ARRAY($data)) { | ||||||||||||
|
Branch: 2 branches
| |||||||||||||||
| 90 | 1 | $self->{data} = $data; | |||||||||||||
| 91 | 1 | return 1; | |||||||||||||
| 92 | } | ||||||||||||||
| 93 | elsif (_CODE($data)) { | ||||||||||||||
| 94 | 1 | $self->{data} = $data; | |||||||||||||
| 95 | 1 | my $n = shift; | |||||||||||||
| 96 | 1 | ▶ | if (not _POSINT($n)) { | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 97 | 0 | croak("'set_data' needs an integer as second argument if the first argument is a code reference."); | |||||||||||||
| 98 | } | ||||||||||||||
| 99 | 1 | $self->{n} = $n; | |||||||||||||
| 100 | 1 | return 1; | |||||||||||||
| 101 | } | ||||||||||||||
| 102 | else { | ||||||||||||||
| 103 | 0 | croak("Invalid arguments to 'set_data'."); | |||||||||||||
| 104 | } | ||||||||||||||
| 105 | } | ||||||||||||||
| 106 | |||||||||||||||
| 107 | =head2 test | ||||||||||||||
| 108 | |||||||||||||||
| 109 | Runs the Random Walk test on the data that was previously set using | ||||||||||||||
| 110 | C<set_data>. | ||||||||||||||
| 111 | |||||||||||||||
| 112 | First argument must be the number of bins. | ||||||||||||||
| 113 | |||||||||||||||
| 114 | Returns three array references. First is an array of quantiles. | ||||||||||||||
| 115 | If the number of bins was ten, this (and all other returned arrays) | ||||||||||||||
| 116 | will hold ten items. | ||||||||||||||
| 117 | |||||||||||||||
| 118 | Second are the determined numbers of random numbers below the | ||||||||||||||
| 119 | quantiles. Third are the expected counts. | ||||||||||||||
| 120 | |||||||||||||||
| 121 | =cut | ||||||||||||||
| 122 | |||||||||||||||
| 123 | 2 | ▶ | sub test { | ||||||||||||
|
Subroutine
test: called CC=15 SCAR=27.3
Pod
documented
| |||||||||||||||
| 124 | 2 | my $self = shift; | |||||||||||||
| 125 | 2 | my $bins = shift; | |||||||||||||
| 126 | 2 | ▶ | if (not _POSINT($bins)) { | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 127 | 0 | croak("Expecting number of bins as argument to 'test'"); | |||||||||||||
| 128 | } | ||||||||||||||
| 129 | 2 | ▶ | my $rescale_factor = $self->rescale_factor||1; | ||||||||||||
|
Condition50%1/2
$self->rescale_factor || 1
MC/DC0%0/1
$self->rescale_factor || 1
$self->rescale_factor
Truth table50%1/2
A
A= $self->rescale_factor
| |||||||||||||||
| 130 | |||||||||||||||
| 131 | |||||||||||||||
| 132 | 2 | my $data = $self->{data}; | |||||||||||||
| 133 | |||||||||||||||
| 134 | 2 | ▶ | if (not defined $data) { | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 135 | 0 | croak("Set data using 'set_data' first."); | |||||||||||||
| 136 | } | ||||||||||||||
| 137 | |||||||||||||||
| 138 | 2 | my $step = 1 / $bins * $rescale_factor; | |||||||||||||
| 139 | 2 | my @alpha; | |||||||||||||
| 140 | 2 | push @alpha, $_*$step for 1..$bins; | |||||||||||||
| 141 | |||||||||||||||
| 142 | 2 | my @bins = (0) x $bins; | |||||||||||||
| 143 | 2 | my $numbers; | |||||||||||||
| 144 | |||||||||||||||
| 145 | 2 | ▶ | if (_ARRAY($data)) { | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 146 | 1 | $numbers = @$data; | |||||||||||||
| 147 | |||||||||||||||
| 148 | 1 | foreach my $i (@$data) { | |||||||||||||
| 149 | 10000 | foreach my $ai (0..$#alpha) { | |||||||||||||
| 150 | 54565 | ▶ | if ($i < $alpha[$ai]) { | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 151 | 10000 | $bins[$_]++ for $ai..$#alpha; | |||||||||||||
| 152 | 10000 | last; | |||||||||||||
| 153 | } | ||||||||||||||
| 154 | } | ||||||||||||||
| 155 | } | ||||||||||||||
| 156 | } | ||||||||||||||
| 157 | else { # CODE | ||||||||||||||
| 158 | 1 | my @cache; | |||||||||||||
| 159 | 1 | my $calls = $self->{n}; | |||||||||||||
| 160 | 1 | foreach (1..$calls) { | |||||||||||||
| 161 | # get new data | ||||||||||||||
| 162 | 100 | push @cache, $data->(); | |||||||||||||
| 163 | 100 | ▶ | while (@cache) { | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 164 | 10000 | $numbers++; | |||||||||||||
| 165 | 10000 | my $this = shift @cache; | |||||||||||||
| 166 | 10000 | foreach my $ai (0..$#alpha) { | |||||||||||||
| 167 | 105598 | ▶ | if ($this < $alpha[$ai]) { | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 168 | 10000 | $bins[$_]++ for $ai..$#alpha; | |||||||||||||
| 169 | 10000 | last; | |||||||||||||
| 170 | } | ||||||||||||||
| 171 | } | ||||||||||||||
| 172 | } | ||||||||||||||
| 173 | } | ||||||||||||||
| 174 | } | ||||||||||||||
| 175 | |||||||||||||||
| 176 | 2 | my @expected_smaller = map Math::BigFloat->new($numbers)*$_/$rescale_factor, @alpha; | |||||||||||||
| 177 | |||||||||||||||
| 178 | return( | ||||||||||||||
| 179 | 2 | [map $_/$rescale_factor, @alpha], | |||||||||||||
| 180 | \@bins, | ||||||||||||||
| 181 | \@expected_smaller, | ||||||||||||||
| 182 | ); | ||||||||||||||
| 183 | } | ||||||||||||||
| 184 | |||||||||||||||
| 185 | =head2 data_to_report | ||||||||||||||
| 186 | |||||||||||||||
| 187 | From the data returned by the C<test()> method, this | ||||||||||||||
| 188 | method creates a textual report and returns it as a string. | ||||||||||||||
| 189 | |||||||||||||||
| 190 | Do not forget to pass in the data that was returned by C<test()> | ||||||||||||||
| 191 | or use the C<test_report()> method directly if you do not use | ||||||||||||||
| 192 | the data otherwise. | ||||||||||||||
| 193 | |||||||||||||||
| 194 | =cut | ||||||||||||||
| 195 | |||||||||||||||
| 196 | 2 | ▶ | sub data_to_report { | ||||||||||||
|
Subroutine
data_to_report: called CC=6 SCAR=18.3
Pod
documented
| |||||||||||||||
| 197 | 2 | my $self = shift; | |||||||||||||
| 198 | 2 | my $alpha = shift; | |||||||||||||
| 199 | 2 | my $got = shift; | |||||||||||||
| 200 | 2 | my $expected = shift; | |||||||||||||
| 201 | 2 | ▶ | if (grep {not _ARRAY($_)} ($alpha, $got, $expected)) { | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 202 | 0 | croak("Please pass the data returned from 'test' to the 'data_to_report' method."); | |||||||||||||
| 203 | } | ||||||||||||||
| 204 | |||||||||||||||
| 205 | 2 | my $max_a = _max_length($alpha); | |||||||||||||
| 206 | 2 | ▶ | $max_a = length('Quantile') if length('Quantile') > $max_a; | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 207 | 2 | my $max_g = _max_length($got); | |||||||||||||
| 208 | 2 | ▶ | $max_g = length('Got') if length('Got') > $max_g; | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 209 | 2 | my $max_e = _max_length($expected); | |||||||||||||
| 210 | 2 | ▶ | $max_e = length('Expected') if length('Expected') > $max_e; | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 211 | |||||||||||||||
| 212 | 2 | my $str = ''; | |||||||||||||
| 213 | |||||||||||||||
| 214 | 2 | $str .= sprintf( | |||||||||||||
| 215 | "\%${max_a}s | \%${max_g}s | \%${max_e}s\n", | ||||||||||||||
| 216 | qw/Quantile Got Expected/ | ||||||||||||||
| 217 | ); | ||||||||||||||
| 218 | 2 | $str .= ('-' x (length($str)-1))."\n"; | |||||||||||||
| 219 | 2 | foreach my $i (0..$#$alpha) { | |||||||||||||
| 220 | 30 | $str .= sprintf( | |||||||||||||
| 221 | "\%${max_a}f | \%${max_g}u | \%${max_e}u\n", | ||||||||||||||
| 222 | $alpha->[$i], $got->[$i], $expected->[$i] | ||||||||||||||
| 223 | ); | ||||||||||||||
| 224 | } | ||||||||||||||
| 225 | 2 | return $str; | |||||||||||||
| 226 | } | ||||||||||||||
| 227 | |||||||||||||||
| 228 | 6 | ▶ | sub _max_length { | ||||||||||||
|
Subroutine
_max_length: called CC=3 SCAR=11.0
| |||||||||||||||
| 229 | 6 | my $max = 0; | |||||||||||||
| 230 | 6 | foreach (@{$_[0]}) { | |||||||||||||
| 231 | 90 | ▶ | $max = length $_ if length($_) > $max; | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 232 | } | ||||||||||||||
| 233 | 6 | return $max; | |||||||||||||
| 234 | |||||||||||||||
| 235 | } | ||||||||||||||
| 236 | |||||||||||||||
| 237 | =head1 SUBROUTINES | ||||||||||||||
| 238 | |||||||||||||||
| 239 | =head2 n_over_k | ||||||||||||||
| 240 | |||||||||||||||
| 241 | Computes C<n> over C<k>. Uses Perl's big number support and | ||||||||||||||
| 242 | returns a L<Math::BigFloat> object. | ||||||||||||||
| 243 | |||||||||||||||
| 244 | This sub is memoized. | ||||||||||||||
| 245 | |||||||||||||||
| 246 | =cut | ||||||||||||||
| 247 | |||||||||||||||
| 248 | 3 | memoize('n_over_k'); | |||||||||||||
| 249 | 230 | ▶ | sub n_over_k { | ||||||||||||
|
Subroutine
n_over_k: called CC=4 SCAR=13.9
| |||||||||||||||
| 250 | 230 | my $n = shift; | |||||||||||||
| 251 | 230 | my $k = shift; | |||||||||||||
| 252 | 230 | my @bits = ((0) x $k, (1) x ($n-$k)); | |||||||||||||
| 253 | 230 | foreach my $x (1..($n-$k)) { | |||||||||||||
| 254 | 1540 | $bits[$x-1]--; | |||||||||||||
| 255 | } | ||||||||||||||
| 256 | |||||||||||||||
| 257 | 230 | my $o = Math::BigFloat->bone(); | |||||||||||||
| 258 | 230 | foreach my $i (0..$#bits) { | |||||||||||||
| 259 | 3080 | ▶ | $o *= Math::BigFloat->new($i+1)**$bits[$i] if $bits[$i] != 0; | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 260 | } | ||||||||||||||
| 261 | |||||||||||||||
| 262 | 230 | return $o->ffround(0); | |||||||||||||
| 263 | } | ||||||||||||||
| 264 | |||||||||||||||
| 265 | 3 | 1; | |||||||||||||
| 266 | |||||||||||||||
| 267 | __END__ | ||||||||||||||