Trace:

notes_20on_20the_20use_20of_20rnd

This shows you the differences between two versions of the page.

notes_20on_20the_20use_20of_20rnd [2018/03/31 13:19] 127.0.0.1 external edit |
notes_20on_20the_20use_20of_20rnd [2018/04/17 17:50] (current) tbest3112 Added syntax highlighting |
||
---|---|---|---|

Line 8: | Line 8: | ||

==== RND(n) ==== | ==== RND(n) ==== | ||

\\ **RND(n)**, where n is a positive integer greater than 1, returns a pseudo-random integer value in the range 1 to n. RND(n) is equivalent to the following function:\\ | \\ **RND(n)**, where n is a positive integer greater than 1, returns a pseudo-random integer value in the range 1 to n. RND(n) is equivalent to the following function:\\ | ||

+ | <code bb4w> | ||

DEF FNrnd(n%) | DEF FNrnd(n%) | ||

LOCAL R | LOCAL R | ||

Line 13: | Line 14: | ||

IF R < 0 R += 2^32 | IF R < 0 R += 2^32 | ||

= R - n% * INT(R / n%) + 1 | = R - n% * INT(R / n%) + 1 | ||

+ | </code> | ||

Note that the statistical distribution of the returned values depends on the value of **n**. For small values of **n** the probabilities of each of the possible returned values (1 to n) are very nearly equal. For example if n=7 the likelihoods of the different values are as follows:\\ \\ 1: 1227133513 / 8589934591 = 0.142857142857\\ 2: 1227133514 / 8589934591 = 0.142857142974\\ 3: 1227133514 / 8589934591 = 0.142857142974\\ 4: 1227133514 / 8589934591 = 0.142857142974\\ 5: 1227133512 / 8589934591 = 0.142857142741\\ 6: 1227133512 / 8589934591 = 0.142857142741\\ 7: 1227133512 / 8589934591 = 0.142857142741\\ \\ So returned values **5**, **6** and **7** are very slightly less probable than values **2**, **3** and **4**, with returned value **1** between these two probabilities. Although this variation is unlikely to be significant, it should be borne in mind for critical applications.\\ \\ | Note that the statistical distribution of the returned values depends on the value of **n**. For small values of **n** the probabilities of each of the possible returned values (1 to n) are very nearly equal. For example if n=7 the likelihoods of the different values are as follows:\\ \\ 1: 1227133513 / 8589934591 = 0.142857142857\\ 2: 1227133514 / 8589934591 = 0.142857142974\\ 3: 1227133514 / 8589934591 = 0.142857142974\\ 4: 1227133514 / 8589934591 = 0.142857142974\\ 5: 1227133512 / 8589934591 = 0.142857142741\\ 6: 1227133512 / 8589934591 = 0.142857142741\\ 7: 1227133512 / 8589934591 = 0.142857142741\\ \\ So returned values **5**, **6** and **7** are very slightly less probable than values **2**, **3** and **4**, with returned value **1** between these two probabilities. Although this variation is unlikely to be significant, it should be borne in mind for critical applications.\\ \\ | ||

==== RND(1) ==== | ==== RND(1) ==== | ||

\\ **RND(1)** returns a floating-point value in the range 0 <= R < 1, that is the returned value is **greater than or equal to** zero but **less than** one. RND(1) is equivalent to the following function:\\ \\ | \\ **RND(1)** returns a floating-point value in the range 0 <= R < 1, that is the returned value is **greater than or equal to** zero but **less than** one. RND(1) is equivalent to the following function:\\ \\ | ||

+ | <code bb4w> | ||

DEF FNrnd1 | DEF FNrnd1 | ||

LOCAL R | LOCAL R | ||

Line 22: | Line 25: | ||

IF R < 0 R += 2^32 | IF R < 0 R += 2^32 | ||

= R/2^32 | = R/2^32 | ||

+ | </code> | ||

Note that the distribution of returned values reflects the distribution of the values returned by **RND**, so the likelihood of the value zero being returned is less than other values. Irrespective of the ***FLOAT** mode in use, RND(1) returns a 40-bit floating point number (32-bit mantissa).\\ \\ | Note that the distribution of returned values reflects the distribution of the values returned by **RND**, so the likelihood of the value zero being returned is less than other values. Irrespective of the ***FLOAT** mode in use, RND(1) returns a 40-bit floating point number (32-bit mantissa).\\ \\ | ||

==== RND(0) ==== | ==== RND(0) ==== | ||

Line 29: | Line 33: | ||

===== Seeding the random-number generator ===== | ===== Seeding the random-number generator ===== | ||

\\ As mentioned above, the sequence-length of BBC BASIC's pseudo-random number generator is 2^33-1 (8589934591), so unless your program calls RND at least that number of times (unlikely!) only part of the sequence will be utilised. Determining the starting point in the sequence is called **seeding** the generator.\\ \\ When //BBC BASIC for Windows// is executed the random number generator is seeded from the value of [[http://www.bbcbasic.co.uk/bbcwin/manual/bbcwin7.html#time|TIME]], but since this counts the number of centiseconds since the PC was last restarted it is likely to be quite small compared with the sequence length. Suppose for example the PC has been running for 24 hours, so TIME is approximately 8640000, this corresponds to only about one-thousandth of the overall sequence length! So relying on the automatic seeding will not make good use of the potential performance of RND.\\ \\ To improve the performance you should seed the generator yourself, using the **RND(-n)** option. To do better than the automatic seeding you need to choose a value which is highly variable, not predictable and can range over most or all of the available range (-2147483648 to -1). On a Windows PC a suitable source of such a seed is the Performance Counter: a 64-bit integer value which counts at a rate up to the clock speed of the CPU. The following code may be used:\\ | \\ As mentioned above, the sequence-length of BBC BASIC's pseudo-random number generator is 2^33-1 (8589934591), so unless your program calls RND at least that number of times (unlikely!) only part of the sequence will be utilised. Determining the starting point in the sequence is called **seeding** the generator.\\ \\ When //BBC BASIC for Windows// is executed the random number generator is seeded from the value of [[http://www.bbcbasic.co.uk/bbcwin/manual/bbcwin7.html#time|TIME]], but since this counts the number of centiseconds since the PC was last restarted it is likely to be quite small compared with the sequence length. Suppose for example the PC has been running for 24 hours, so TIME is approximately 8640000, this corresponds to only about one-thousandth of the overall sequence length! So relying on the automatic seeding will not make good use of the potential performance of RND.\\ \\ To improve the performance you should seed the generator yourself, using the **RND(-n)** option. To do better than the automatic seeding you need to choose a value which is highly variable, not predictable and can range over most or all of the available range (-2147483648 to -1). On a Windows PC a suitable source of such a seed is the Performance Counter: a 64-bit integer value which counts at a rate up to the clock speed of the CPU. The following code may be used:\\ | ||

+ | <code bb4w> | ||

DIM pc{l%,h%} | DIM pc{l%,h%} | ||

SYS "QueryPerformanceCounter", pc{} | SYS "QueryPerformanceCounter", pc{} | ||

seed% = RND(-ABS(pc.l%)) | seed% = RND(-ABS(pc.l%)) | ||

+ | </code> | ||

It should be noted, however, that the rate at which the Performance Counter increments is extremely variable between systems, and indeed one isn't guaranteed to exist at all. Therefore if you are lucky enough to have a better source of seed available you should use that instead.\\ \\ However good your source of seed, since RND(-n) can only take a maximum of 2^31 different values (compared with the total sequence length of 2^33-1) only about **one quarter** of the overall sequence is likely to be exploited. If this is important to you, the pseudo-random number generator can alternatively be seeded by writing values directly to its memory locations, see [[/Interpreter%20internal%20variables|Interpreter internal variables]]:\\ | It should be noted, however, that the rate at which the Performance Counter increments is extremely variable between systems, and indeed one isn't guaranteed to exist at all. Therefore if you are lucky enough to have a better source of seed available you should use that instead.\\ \\ However good your source of seed, since RND(-n) can only take a maximum of 2^31 different values (compared with the total sequence length of 2^33-1) only about **one quarter** of the overall sequence is likely to be exploited. If this is important to you, the pseudo-random number generator can alternatively be seeded by writing values directly to its memory locations, see [[/Interpreter%20internal%20variables|Interpreter internal variables]]:\\ | ||

+ | <code bb4w> | ||

!412 = seedl% | !412 = seedl% | ||

?416 = seedh% | ?416 = seedh% | ||

+ | </code> | ||

Here **seedl%** is a 32-bit value (&00000000 to &FFFFFFFF) and **seedh%** is a 1-bit value (0 or 1). Note that they **must not both be zero**. Using this technique you can initialise RND to any point in its sequence.\\ \\ | Here **seedl%** is a 32-bit value (&00000000 to &FFFFFFFF) and **seedh%** is a 1-bit value (0 or 1). Note that they **must not both be zero**. Using this technique you can initialise RND to any point in its sequence.\\ \\ | ||

===== Is RND good enough? ===== | ===== Is RND good enough? ===== | ||

Line 40: | Line 48: | ||

===== How to do better than RND ===== | ===== How to do better than RND ===== | ||

\\ There is no shortage of pseudo-random number generator algorithms with a longer sequence length than RND. For example the assembler-code algorithm [[/Alternative%20pseudo-random%20numbers|here]] has a sequence length of 2^64-1 (1.8E19), which although far longer than RND is still hugely less than the number of permutations of a pack of 52 cards. The [[http://groups.yahoo.com/group/bb4w/files/Mathematics/mersenne.bbc|Mersenne Twister]] has a mind-boggling sequence length of 2^19937−1 (about 10^6000), although the BBC BASIC code at that link can only take a 32-bit seed which somewhat defeats the object. Two modern, high-performance algorithms are listed at [[/High%20Quality%20Random%20Number%20Generation|High Quality Random Number Generation]].\\ \\ One thing not to attempt is to write your own algorithm, unless you're a top-notch mathematician! An algorithm with an unintentional bias is only too easy to create and the consequences could be serious.\\ \\ Using an improved algorithm is only part of the solution. Even if the sequence length is adequate for the task in hand, you must be able to seed it so that a big enough portion of this length is exploited. For example, in the card shuffling case you need to be able to generate a seed with around 230 bits to ensure all possible permutations of cards could, in principle, be generated. Finding an external source of 'randomness' with that number of bits is by no means easy. For example the Performance Counter, as suggested above, is woefully inadequate with only 64 bits of precision.\\ \\ The Windows API function [[http://en.wikipedia.org/wiki/CryptGenRandom|CryptGenRandom]] (available on Windows 2000 and later) provides a //cryptographically secure// random number of a specified length, in bytes. The function below returns a random 32-bit integer using this method:\\ | \\ There is no shortage of pseudo-random number generator algorithms with a longer sequence length than RND. For example the assembler-code algorithm [[/Alternative%20pseudo-random%20numbers|here]] has a sequence length of 2^64-1 (1.8E19), which although far longer than RND is still hugely less than the number of permutations of a pack of 52 cards. The [[http://groups.yahoo.com/group/bb4w/files/Mathematics/mersenne.bbc|Mersenne Twister]] has a mind-boggling sequence length of 2^19937−1 (about 10^6000), although the BBC BASIC code at that link can only take a 32-bit seed which somewhat defeats the object. Two modern, high-performance algorithms are listed at [[/High%20Quality%20Random%20Number%20Generation|High Quality Random Number Generation]].\\ \\ One thing not to attempt is to write your own algorithm, unless you're a top-notch mathematician! An algorithm with an unintentional bias is only too easy to create and the consequences could be serious.\\ \\ Using an improved algorithm is only part of the solution. Even if the sequence length is adequate for the task in hand, you must be able to seed it so that a big enough portion of this length is exploited. For example, in the card shuffling case you need to be able to generate a seed with around 230 bits to ensure all possible permutations of cards could, in principle, be generated. Finding an external source of 'randomness' with that number of bits is by no means easy. For example the Performance Counter, as suggested above, is woefully inadequate with only 64 bits of precision.\\ \\ The Windows API function [[http://en.wikipedia.org/wiki/CryptGenRandom|CryptGenRandom]] (available on Windows 2000 and later) provides a //cryptographically secure// random number of a specified length, in bytes. The function below returns a random 32-bit integer using this method:\\ | ||

+ | <code bb4w> | ||

DEF FN_RndSecure | DEF FN_RndSecure | ||

LOCAL R%, P% | LOCAL R%, P% | ||

Line 46: | Line 55: | ||

SYS "CryptReleaseContext", P% | SYS "CryptReleaseContext", P% | ||

= R% | = R% | ||

+ | </code> | ||

CryptGenRandom uses various sources of //entropy// to seed the generator, for example the tick-count since boot time, the current clock time and the Performance Counter.\\ \\ | CryptGenRandom uses various sources of //entropy// to seed the generator, for example the tick-count since boot time, the current clock time and the Performance Counter.\\ \\ | ||

===== Code examples ===== | ===== Code examples ===== | ||

Line 51: | Line 61: | ||

==== Lottery numbers ==== | ==== Lottery numbers ==== | ||

\\ The following routine selects and prints six lottery numbers, each in the range 1 to 49:\\ | \\ The following routine selects and prints six lottery numbers, each in the range 1 to 49:\\ | ||

+ | <code bb4w> | ||

max = 49 | max = 49 | ||

num = 6 | num = 6 | ||

Line 63: | Line 74: | ||

max = max-1 | max = max-1 | ||

NEXT choice | NEXT choice | ||

+ | </code> | ||

If you want to display the selection in ascending sequence, you can put the numbers in a second array and sort it:\\ | If you want to display the selection in ascending sequence, you can put the numbers in a second array and sort it:\\ | ||

+ | <code bb4w> | ||

INSTALL @lib$+"SORTLIB" | INSTALL @lib$+"SORTLIB" | ||

sort% = FN_sortinit(0,0) | sort% = FN_sortinit(0,0) | ||

Line 83: | Line 96: | ||

PRINT choices(choice) | PRINT choices(choice) | ||

NEXT | NEXT | ||

+ | </code> | ||

\\ | \\ | ||

==== Shuffling a pack of cards ==== | ==== Shuffling a pack of cards ==== | ||

\\ Notwithstanding the comments made above, this routine uses RND for the convenience of the example. In practice a better random number generator ought to be used:\\ | \\ Notwithstanding the comments made above, this routine uses RND for the convenience of the example. In practice a better random number generator ought to be used:\\ | ||

+ | <code bb4w> | ||

cards = 52 | cards = 52 | ||

DIM pack(cards) | DIM pack(cards) | ||

Line 98: | Line 113: | ||

NEXT I | NEXT I | ||

+ | </code> | ||

This uses Durstenfeld's algorithm for the [[http://en.wikipedia.org/wiki/Fisher-Yates_shuffle|Fisher–Yates shuffle]]. | This uses Durstenfeld's algorithm for the [[http://en.wikipedia.org/wiki/Fisher-Yates_shuffle|Fisher–Yates shuffle]]. |

notes_20on_20the_20use_20of_20rnd.txt · Last modified: 2018/04/17 17:50 by tbest3112

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International