1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
/*
* randomrun - perform a run test on random()
*
* Copyright (C) 1999 Landon Curt Noll
*
* Calc is open software; you can redistribute it and/or modify it under
* the terms of the version 2.1 of the GNU Lesser General Public License
* as published by the Free Software Foundation.
*
* Calc is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
* Public License for more details.
*
* A copy of version 2.1 of the GNU Lesser General Public License is
* distributed with calc under the filename COPYING-LGPL. You should have
* received a copy with calc; if not, write to Free Software Foundation, Inc.
* 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*
* Under source code control: 1997/02/19 03:35:59
* File existed as early as: 1997
*
* chongo <was here> /\oo/\ http://www.isthe.com/chongo/
* Share and enjoy! :-) http://www.isthe.com/chongo/tech/comp/calc/
*/
/*
* If X(j) < X(j+1) < ... X(j+k) >= X(j+k+1), then we have a run of 'k'.
* We ignore the run breaker, X(j+k+1), and start with X(j+k+2) when
* considering a new run in order to make our runs chi independent.
*
* See Knuth's "Art of Computer Programming - 2nd edition",
* Volume 2 ("Seminumerical Algorithms"), Section 3.3.2.
* "G. Run test", pp. 65-68,
* "problem #14", pp. 74, 536.
*
* We use the suggestion in problem #14 to allow an application of the
* chi-square test and to make estimating the run length probs easy.
*/
define randomrun(run_cnt)
{
local i; /* index */
local max_run; /* longest run */
local long_run_cnt; /* number of runs longer than MAX_RUN */
local run; /* current run length */
local tally_sum; /* sum of all tally values */
local last; /* last random number */
local current; /* current random number */
local MAX_RUN = 9; /* max run we will keep track of */
local mat tally[1:MAX_RUN]; /* tally of length of a rise run of 'x' */
local mat prob[1:MAX_RUN]; /* prob[x] = probability of 'x' length run */
/*
* parse args
*/
if (param(0) == 0) {
run_cnt = 65536;
}
/*
* run setup
*/
max_run = 0; /* no runs yet */
long_run_cnt = 0; /* no long runs set */
current = random(); /* our first number */
run = 1;
/*
* compute the run length probabilities
*
* A run length of 'r' occurs with a probability of:
*
* 1/r! - 1/(r+1)!
*/
for (i=1; i <= MAX_RUN; ++i) {
prob[i] = 1.0/fact(i) - 1.0/fact(i+1);
}
/*
* look at a number of random number trials
*/
for (i=0; i < run_cnt; ++i) {
/* get our current number */
last = current;
current = random();
/* look for a run break */
if (current < last) {
/* record the stats */
if (run > max_run) {
max_run = run;
}
if (run > MAX_RUN) {
++long_run_cnt;
} else {
++tally[run];
}
/* start a new run */
current = random();
run = 1;
/* note the continuing run */
} else {
++run;
}
}
/* determine the number of runs found */
tally_sum = matsum(tally) + long_run_cnt;
/*
* print the stats
*/
printf("random run test used %d values to produce %d runs\n",
run_cnt, tally_sum);
for (i=1; i <= MAX_RUN; ++i) {
printf("length=%d\tprob=%9.7f\texpect=%d \tcount=%d \terr=%9.7f\n",
i, prob[i], round(tally_sum*prob[i]), tally[i],
(tally[i] - round(tally_sum*prob[i]))/tally_sum);
}
printf("length>%d\t\t\t\t\tcount=%d\n", MAX_RUN, long_run_cnt);
printf("max length=%d\n", max_run);
}
|
