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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
|
<!--startcut ==============================================-->
<!-- *** BEGIN HTML header *** -->
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML><HEAD>
<title>Taming rand() and random() LG #63</title>
</HEAD>
<BODY BGCOLOR="#FFFFFF" TEXT="#000000" LINK="#0000FF" VLINK="#0000AF"
ALINK="#FF0000">
<!-- *** END HTML header *** -->
<CENTER>
<A HREF="http://www.linuxgazette.com/">
<H1><IMG ALT="LINUX GAZETTE" SRC="../gx/lglogo.png"
WIDTH="600" HEIGHT="124" border="0"></H1></A>
<!-- *** BEGIN navbar *** -->
<IMG ALT="" SRC="../gx/navbar/left.jpg" WIDTH="14" HEIGHT="45" BORDER="0" ALIGN="bottom"><A HREF="andreiana.html"><IMG ALT="[ Prev ]" SRC="../gx/navbar/prev.jpg" WIDTH="16" HEIGHT="45" BORDER="0" ALIGN="bottom"></A><A HREF="index.html"><IMG ALT="[ Table of Contents ]" SRC="../gx/navbar/toc.jpg" WIDTH="220" HEIGHT="45" BORDER="0" ALIGN="bottom" ></A><A HREF="../index.html"><IMG ALT="[ Front Page ]" SRC="../gx/navbar/frontpage.jpg" WIDTH="137" HEIGHT="45" BORDER="0" ALIGN="bottom"></A><A HREF="http://www.linuxgazette.com/cgi-bin/talkback/all.py?site=LG&article=http://www.linuxgazette.com/issue63/burtch.html"><IMG ALT="[ Talkback ]" SRC="../gx/navbar/talkback.jpg" WIDTH="121" HEIGHT="45" BORDER="0" ALIGN="bottom" ></A><A HREF="../faq/index.html"><IMG ALT="[ FAQ ]" SRC="./../gx/navbar/faq.jpg"WIDTH="62" HEIGHT="45" BORDER="0" ALIGN="bottom"></A><A HREF="brunton.html"><IMG ALT="[ Next ]" SRC="../gx/navbar/next.jpg" WIDTH="15" HEIGHT="45" BORDER="0" ALIGN="bottom" ></A><IMG ALT="" SRC="../gx/navbar/right.jpg" WIDTH="15" HEIGHT="45" ALIGN="bottom">
<!-- *** END navbar *** -->
<P>
</CENTER>
<!--endcut ============================================================-->
<H4 ALIGN="center">
"Linux Gazette...<I>making Linux just a little more fun!</I>"
</H4>
<P> <HR> <P>
<!--===================================================================-->
<center>
<H1><font color="maroon">Taming rand() and random()</font></H1>
<H4>By <a href="mailto:kburtch@mackenziefinancial.com">Ken O. Burtch</a></H4>
</center>
<P> <HR> <P>
<!-- END header -->
<p>In the lower levels of the Ontario Science Center in Toronto, Canada,
there is a wide circular device made of thin rods of steel. Curious bystanders
can take billiard balls, put there for that purpose, and let them loose
on the machine. The balls whiz along their rails, richocheting off
pins, clanging through wind chimes, grabbed by
counterweighted arms and lifted towards the ceiling. At several
places the balls chose one rail or another purely at random. How
is it that a construct not powered in any way, laid out in a rigid pattern,
still produces unexpected results?
<p>Writing programs that use random numbers requires an understanding of
error estimation, probability theory, statistics and other advanced numeric
disciplines.
<p>Bunk.
<p>Random numbers are about getting your programs to do the unexpected
without a core dump being involved. They're about having fun.
<center>
<h1>
Random But Not Really Random</h1></center>
<p><br>Computers do not use "real world" random numbers. Like the
billiard-ball machine, computers are rigid, constrained by rules and logical
behaviour. For a computer to generate truly random numbers, it would
have to choose numbers by examining real world events. In the early
days, people might roll some 10-sided dice and compose a list of digits
for a program to use.
<p>Unfortunately real-world random numbers can be unexpectedly biased.
As the old saying goes, "the real world
is a special case." Instead, computers rely on mathematics to
generate uniformly distributed (that is, random but not too random) numbers.
They are "pseudo-random", generated by mathematic functions which create
a seemingly non-repeating sequence. Over time, the numbers in the
sequence will reliably occur equally often, with no one number being favoured
over another.
<p>The Linux standard C library (stdlib.h) has two built-in random number
functions. The first, rand(), returns a random integer between 0
and RAND_MAX. If we type
<p><tt> printf( " rand() is %d\n", rand() );</tt>
<br><tt> printf( " rand() is %d\n", rand() );</tt>
<br><tt> printf( " rand() is %d\n", rand() );</tt>
<p>rand() will return values like
<p><tt> rand() is 1750354891</tt>
<br><tt> rand() is 2140807809</tt>
<br><tt> rand() is 1844326400</tt>
<p>Each invocation will return a new, randomly chosen positive integer
number.
<p>The other standard library function, random(), returns a positive long
integer. On Linux, both integer and long integer numbers are the
same size. random() has some other properties that are discussed
below.
<p>There are also older, obsolete functions to produce random numbers
<p> * drand48/erand48 return a random double between 0..1.
<br> * lrand48/nrand48 return a random long between 0 and 2^31.
<br> * mrand48/jrand48 return a signed random long.
<p>These are provided for backward compatibility with other flavours of
UNIX.
<p>rand() and random() are, of course, totally useless as they appear and
are rarely called directly. It's not often we're looking for a number
number between 0 and a really big number: the numbers need to apply to
actually problems with specific ranges of alternatives. To tame rand(),
its value must be scaled to a more useful range such as between 1 and some
specific maximum. The modulus (%) operator works well: when a number
is divided, the remainder is between 0 and 1 less than the original number.
Adding 1 to the modulus result gives the range we're looking for.
<p><tt> <b>int</b> rnd( <b>int</b> max ) {</tt>
<br><tt> <b>return</b> (rand() % max) + 1;</tt>
<br><tt> }</tt>
<p>This one line function will return numbers between 1 and a specified
maximum. rnd(10) will return numbers between 1 and 10, rnd(50) will
return numbers between 1 and 50. Real life events can be simulated
by assigning numbers for different outcomes. Flipping a coin
is rnd(2)==1 for heads, rnd(2)==2 for tails. Rolling a pair of dice
is rnd(6)+rnd(6).
<p>The rand() discussion in the Linux manual recommends that you take the
"upper bits" (that is, use division instead of modulus) because they tend
to be more random. However, the rnd() function above is suitably
random for most applications.
<p>The following test program generates 100 numbers between 1 and 10, counting
how often each number comes up in the sequence. If the numbers were
perfectly uniform, they would appear 10 times each.
<p><tt> <b>int</b> graph[11];</tt>
<br><tt> <b>int</b> i;</tt><tt></tt>
<p><tt> <b>for</b> (i=1; i<=10; i++)</tt>
<br><tt> graph[i] = 0;</tt>
<br><tt> <b>for</b> (i=1; i<=100; i++)</tt>
<br><tt> graph[ rnd(10) ]++;</tt>
<br><tt> printf( "for rnd(), graph[1..10] is " );</tt>
<br><tt> <b>for</b> (i=1; i<=10; i++)</tt>
<br><tt> printf( "%d " , graph[i] );</tt>
<br><tt> printf( "\n" );</tt>
<p>When we run this routine, we get the following:
<p><tt> for rnd(), graph[1..10] is 7 12 9 8 14 9 16 5 11 9</tt>
<p>Linux's rand() function goes to great efforts to generate high-quality
random numbers and therefore uses a significant amount of CPU time. If
you need to generate a lot mediocre quality random numbers quickly, you can use
a function like this:
<p><tt><b>unsigned</b> <b>int</b> seed = 0;</tt><tt></tt>
<p><tt><b>int</b> fast_rnd( <b>int</b> max ) {</tt>
<br><tt> <b>unsigned</b> <b>int</b> offset = 12923;</tt>
<br><tt> <b>unsigned</b> <b>int</b> multiplier = 4079;</tt><tt></tt>
<p><tt> seed = seed * multiplier + offset;</tt>
<br><tt> <b>return</b> (<b>int</b>)(seed % max) + 1;</tt>
<br><tt>}</tt>
<p>This function sacrifices accuracy for speed: it will produce random
numbers not quite as mathematically uniform as rnd(), but it uses only
a few short calculations. Ideally, the offset and multiplier should
be prime numbers so that fewer numbers will be favoured over others.
<p>Replacing rnd with fast_rnd() in the test functions still gives a reasonable
approximation of rand() with
<p><tt> for fast_rnd(), graph[1..10] is 11 4 4 1 8 8 5 7 6 5</tt>
<center>
<h1>
Controlling the Sequence</h1></center>
<p><br>A <i>seed</i> is the initial value given to a random number generator
to produce the first random number. If you set
the seed to a certain value, the sequence of numbers will always repeat,
starting with the same number. If you are writing a game, for example,
you can set the seed to a specific value and use the fast_rnd() to position
enemies in the same place each time without actually having to save any
location information.
<p><tt> seed = room_number;</tt>
<br><tt> num_enemy = fast_rnd( 5 );</tt>
<br><tt> <b>for</b> ( enemy=1; enemy<=num_enemy; enemy++ ) {</tt>
<br><tt> enemy_type[enemy] = fast_rnd( 6
);</tt>
<br><tt> enemy_horizontal[enemy] = fast_rnd(
1024 );</tt>
<br><tt> enemy_vertical[enemy] = fast_rnd(
768 );</tt>
<br><tt> }</tt>
<p>The seed for the Linux rand() function is set by srand(). For example,
<p><tt> srand( 4 );</tt>
<p>will set the rand() seed to 4.
<p>There are two ways to control the sequence with the other Linux
function, random(). First, srandom(), like srand(), will set a seed
for random().
<p>Second, if you need greater precision, Linux provides two functions
to control the speed and precision of random(). With initstate(),
you can give random() both a seed and a buffer for keeping the intermediate
function result. The buffer can be 8, 32, 64, 128 or 256 bytes in
size. Larger buffers will give better random numbers but will take
longer to calculate as a result.
<p><tt> <b>char</b> state[256];
/* 256 byte buffer */</tt>
<br><tt> <b>unsigned</b> <b>int</b> seed = 1;
/* initial seed of 1 */</tt><tt></tt>
<p><tt> initstate( seed, state, 256 );</tt>
<br><tt> printf( "using a 256 byte state, we get %d\n", random()
);</tt>
<br><tt> printf( "using a 256 byte state, we get %d\n", random()
);</tt>
<br><tt> initstate( seed, state, 256 );</tt>
<br><tt> printf( "resetting the state, we get %d\n", random() );</tt>
<p>gives
<p><tt> using a 256 byte state, we get 510644794</tt>
<br><tt> using a 256 byte state, we get 625058908</tt>
<br><tt> resetting the state, we get 510644794</tt>
<p>You can switch random() states with setstate(), followed by srandom()
to initialize the seed to a specific value.
<br>setstate() always returns a pointer to the previous state.
<p><tt> oldstate = setstate( newstate );</tt>
<p>Unless you change the seed when your program starts, your random numbers
will always be the same. To create changing random sequences, the
seed should be set to some value outside of the program or users control.
Using the time code returned by time.h's time() is a good choice.
<p><tt> srand( time( NULL ) );</tt>
<p>Since the time is always changing, this will give your program a new
sequence of random numbers each
time it begins execution.
<center>
<h1>
Randomizing Lists</h1></center>
<p><br>One of the classic gaming problems that seems to stump many people
is shuffling, changing the order of items in a list. While I was
at university, the Computer Center there faced the task of sorting a list
of names. Their solution was to print out the names on paper, cut
the paper with scissors, and pull the slips of paper from a bucket and
retype them into the computer.
<p>So what is the best approach to shuffling a list? Cutting up a
print out? Dubious. Exchanging random items a few thousand
times? Effective, but slow and it doesn't guarantee that all items
will have a chance to be moved. Instead, take each item in the list
and exchange it with some other item. For example, suppose we have
a list of 52 playing cards represented by the numbers 0 to 51. To
shuffle the cards, we'd do the following:
<p><tt> <b>int</b> deck[ 52 ];</tt>
<br><tt> <b>int</b> newpos;</tt>
<br><tt> <b>int</b> savecard;</tt>
<br><tt> <b>int</b> i;</tt><tt></tt>
<p><tt> <b>for</b> ( i=0; i<52; i++ )</tt>
<br><tt> deck[i] = i;</tt>
<br><tt> printf( "Deck was " );</tt>
<br><tt> <b>for</b> ( i=0; i<52; i++ )</tt>
<br><tt> printf( "%d ", deck[i] );</tt>
<br><tt> printf( "\n" );</tt>
<br><tt> <b>for</b> ( i=0; i<52; i++ ) {</tt>
<br><tt> newpos = rnd(52)-1;</tt>
<br><tt> savecard = deck[i];</tt>
<br><tt> deck[i] = deck[newpos];</tt>
<br><tt> deck[newpos] = savecard;</tt>
<br><tt> }</tt>
<br><tt> printf( "Deck is " );</tt>
<br><tt> <b>for</b> ( i=0; i<52; i++ )</tt>
<br><tt> printf( "%d ", deck[i] );</tt>
<br><tt> printf( "\n" );</tt>
<p>The results give us a before and after picture of the deck:
<p><tt> Deck was 0 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</tt>
<br><tt> Deck is 35 48 34 13 6 11 49 41 1 32 23 3 16 43 42 18 28
26 25 15 7 27 5 29 44 2 47 38 39 50 31 17 8 14 22 36 12 30 33 10 45 21
46 19 24 9 51 20 4 37 0 40</tt>
<center>
<h1>
Different Types of Randomness</h1></center>
<p><br>People acquainted with statistics know that many of real life events
do not happen with a uniform pattern. The first major repair for
a car, for example, might happen between 5 and 9 years of after purchase,
but it might be most common around the 7th year. Any year in the
range is likely, but its most likely to be in the middle of the range.
<p>Small unexpected events like these occur in a bell curve shape (called
a normal distribution in statistics). Creating random numbers that
conform to such a complex shape may seem like a duanting task, but it really
isn't. Since our rnd() function already produces nicely uniform "unexpected"
events, we don't need a statistics textbook formula to generate normally
distributed random numbers. All we need to do is call rnd() a few
times and take the average, simulating a normal distribution.
<p><tt><b>int</b> normal_rnd( <b>int</b> max ) {</tt>
<br><tt> <b>return</b> (rnd( max ) + rnd( max ) + rnd( max ) + rnd(
max ) +</tt>
<br><tt> rnd( max ) + rnd(
max ) + rnd( max ) + rnd( max ) ) / 8;</tt><tt></tt>
<p><tt>}</tt>
<p>Using normal_rnd() in the test function, we get values that are clustered
at the mid-point between 1 and max:
<p><tt> for normal_rnd(), graph[1..10] is 0 0 4 26 37 23 10 0 0 0</tt>
<p>Normal random numbers can be used to make a game more life-like, making
enemy behaviour less erratic.
<p>For numbers skewed toward the low end of the range, we can create a
low_rnd() which favours numbers near 1.
<p><tt> <b>int</b> low_rnd( <b>int</b> max ) {</tt>
<br><tt> <b>int</b> candidate;</tt><tt></tt>
<p><tt> candidate = rnd( max );</tt>
<br><tt> <b>if</b> ( rnd( 2 ) == 1 )</tt>
<br><tt> <b>return</b> candidate;</tt>
<br><tt> <b>else</b> <b>if</b> ( max > 1 )</tt>
<br><tt> <b>return</b> low_rnd( max
/ 2 );</tt>
<br><tt> <b>else</b></tt>
<br><tt> <b>return</b> 1;</tt>
<br><tt> }</tt>
<p>In each recursion, low_rnd() splits the range in half, favoring the
lower half of the range. By deducting a low random number from the
top of the range, we could write a corresponding high_rnd() favoring numbers
near the max:
<p><tt> <b>int</b> high_rnd( <b>int</b> max ) {</tt>
<br><tt> <b>return</b> max - low_rnd( max ) + 1;</tt>
<br><tt> }</tt>
<p>The skewing is easily seen when using the test program:
<p><tt> for low_rnd(), graph[1..10] is 36 15 11 8 9 3 4 3 3 8</tt>
<br><tt> for high_rnd(), graph[1..10] is 4 5 8 5 4 10 6 10 14 34</tt>
<center>
<h1>
Random If Statements</h1></center>
<p><br>Arbitrary branches in logic can be done with a odds() function.
<p><tt> <b>int</b> odds( <b>int</b> percent ) {</tt>
<br><tt> <b>if</b> ( percent <=
0 )</tt>
<br><tt> <b>return</b>
0;</tt>
<br><tt> <b>else</b> <b>if</b> ( percent
> 100 )</tt>
<br><tt> <b>return</b>
1;</tt>
<br><tt> <b>else</b> <b>if</b> ( rnd(
100 ) <= percent )</tt>
<br><tt> <b>return</b>
1;</tt>
<br><tt> <b>return</b> 0;</tt>
<br><tt> }</tt>
<p>This function is true the specified percentage of the time making it
easy to incorporate into an if statement.
<p> <tt> <b>if</b> ( odds( 50 ) )</tt>
<br><tt> printf( "The cave did not collapse!\n" )</tt>
<br><tt> <b>else</b></tt>
<br><tt> printf( "Ouch! You are squashed beneath a mountain
of boulders.\n" );</tt>
<p>The standard C library rand() and random() functions provide a program
with uniformly distributed random numbers. The sequence and precision
can be controlled by other library functions and the distribution of numbers
can be altered by simple functions. Random numbers can add unpredictability
to a program and are, of course, the backbone to exciting play in computer
games.
<!-- *** BEGIN copyright *** -->
<P> <hr> <!-- P -->
<H5 ALIGN=center>
Copyright © 2001, Ken O. Burtch.<BR>
Copying license <A HREF="../copying.html">http://www.linuxgazette.com/copying.html</A><BR>
Published in Issue 63 of <i>Linux Gazette</i>, Mid-February (EXTRA) 2001</H5>
<!-- *** END copyright *** -->
<!--startcut ==========================================================-->
<HR><P>
<CENTER>
<!-- *** BEGIN navbar *** -->
<IMG ALT="" SRC="../gx/navbar/left.jpg" WIDTH="14" HEIGHT="45" BORDER="0" ALIGN="bottom"><A HREF="andreiana.html"><IMG ALT="[ Prev ]" SRC="../gx/navbar/prev.jpg" WIDTH="16" HEIGHT="45" BORDER="0" ALIGN="bottom"></A><A HREF="index.html"><IMG ALT="[ Table of Contents ]" SRC="../gx/navbar/toc.jpg" WIDTH="220" HEIGHT="45" BORDER="0" ALIGN="bottom" ></A><A HREF="../index.html"><IMG ALT="[ Front Page ]" SRC="../gx/navbar/frontpage.jpg" WIDTH="137" HEIGHT="45" BORDER="0" ALIGN="bottom"></A><A HREF="http://www.linuxgazette.com/cgi-bin/talkback/all.py?site=LG&article=http://www.linuxgazette.com/issue63/burtch.html"><IMG ALT="[ Talkback ]" SRC="../gx/navbar/talkback.jpg" WIDTH="121" HEIGHT="45" BORDER="0" ALIGN="bottom" ></A><A HREF="../faq/index.html"><IMG ALT="[ FAQ ]" SRC="./../gx/navbar/faq.jpg"WIDTH="62" HEIGHT="45" BORDER="0" ALIGN="bottom"></A><A HREF="brunton.html"><IMG ALT="[ Next ]" SRC="../gx/navbar/next.jpg" WIDTH="15" HEIGHT="45" BORDER="0" ALIGN="bottom" ></A><IMG ALT="" SRC="../gx/navbar/right.jpg" WIDTH="15" HEIGHT="45" ALIGN="bottom">
<!-- *** END navbar *** -->
</CENTER>
</BODY></HTML>
<!--endcut ============================================================-->
|
