Help / Release / J 5.03 / ? and ?. Improved
>> << Pri JfC LJ Phr Dic Voc !: Rel NuVoc wd Help Release
|
? and ?. Improved |
initial writing: 2003-10-11 |
? (and ?.) have been improved in the following ways:
- A new random number generator is used
- ?0 selects from the uniform 0-1 distribution
- The dyad ?@$ is now implemented by special code
1. A New Random Number Generator
? (and ?.) now use the GB_FLIP random number generator in Donald Knuth’s GraphBase library. GB_FLIP, a subtractive method, replaces the linear congruential method developed by D.H. Lehmer in 1951. It is better in the following ways:
- The period length of the generated numbers is as least _1+2^55 , and is plausibly conjectured to be -/2^85 30 for all but at most one choice of the seed value. The period length of the old method is _1+2^31 .
- The new method is faster and leaner than the old method. See the benchmarks below.
As before, the foreigns 9!:0 and 9!:1 inquire and set the random number seed. However, now the seed is unchanged by using ? (or ?.). That is, the result of 9!:0 is the value of the seed the last time it was set by 9!:1 .
Random numbers generated using the old method are available through the verbs roll and deal in section 4 below.
2. Uniform 0-1 Random Numbers
?0 , previously a domain error, has been changed to produce a random floating point number from the uniform distribution [0,1) (greater than or equal to 0 and less than 1). Thus to generate one million such numbers one could say ?1e6$0 or, more efficiently (by exploiting special code), 1e6 ?@$ 0 .
? 2 5$0 0.228966 0.322778 0.83538 0.527181 0.994417 0.586394 0.80113 0.545236 0.0584635 0.427982 ? 0 10 20 0.257946 9 5
Random 0-1 numbers can be generated nearly as efficiently as -- within a factor of 2 -- random integers, as the following benchmarks demonstrate:
ts=: 6!:2 , 7!:2@] NB. time and space ts '+/i.1e6' NB. calibration 0.0400596 4.19546e6 ts '?1e6$0' NB. random floats 0.127696 9.43795e6 ts '1e6 ?@$ 0' NB. special code 0.114351 8.38944e6 ts '?1e6$2e9' NB. random integers 0.164644 8.38931e6 ts '1e6 ?@$ 2e9' NB. special code 0.0680324 4.19526e6
The resolution of random floating point numbers so generated depends on the underlying hardware; the resolution is one part in 2^53 on the PC with 64-bit IEEE floating point numbers. The generation of these numbers can be modelled thus:
U=: 3 : '(2^53) %~ (2^30) #. ?(y.,2)$2^23 30' U 2 5 0.627997 0.254797 0.339676 0.995029 0.617055 0.641366 0.212932 0.958605 0.75816 0.229028 2 ^. +./ 1e6 ?@$ 0 _53
3. Special Code
The following dyads are now supported by special code:
| ? @$ | ? @:$ | [: ? $ | |||
| ?.@$ | ?.@:$ | [: ?. $ | |||
| ? @# | ? @:# | [: ? # | |||
| ?.@# | ?.@:# | [: ?. # |
The following benchmarks demonstrate the improvement, which is due to using the GB_FLIP random number generator and to that the special code for ?@$ does not explictly
compute x$y
b=: 1e6$2 i=: 1e6$1e7 ts=: 6!:2 , 7!:2@] NB. time and space ts 'Expression'
| Expression | J 5.03 | J 5.02 | Ratio | |||||||||
| ?b | 0.015900 | 1049152 | 0.323943 | 5243520 | 20.37 | 5.00 | ||||||
| ?i | 0.144913 | 4194880 | 0.667152 | 4194944 | 4.60 | 1.00 | ||||||
| ?1e6$2 | 0.045027 | 5243520 | 0.347825 | 9437888 | 7.72 | 1.80 | ||||||
| ?1e6$1e7 | 0.170378 | 8389312 | 0.692795 | 8389376 | 4.07 | 1.00 | ||||||
| 1e6 ?@$ 2 | 0.006729 | 1049344 | 0.352622 | 9438016 | 52.41 | 8.99 | ||||||
| 1e6 ?@$ 1e7 | 0.074965 | 4195264 | 0.691673 | 8389632 | 9.23 | 2.00 | ||||||
4. Model of Roll and Deal
Random numbers generated using the old linear congruential method are available through the verbs roll and deal , from P.C. Berry, Sharp APL Reference Manual, 1979. bigdeal is by E.E. McDonnell circa 1966, for small x and large y .
qrl =: 7^5 NB. initial random seed value
tick =: [ <.@%~ (* 3 : 'qrl=:(<:2^31)|(7^5)*qrl')@]
roll =: (<:2^31)&tick"0
rix =: i.@[ ([ ,. [ + roll@:-~) ]
deal1=: [ {. <@~."1@|.@rix C. i.@-@]
deal =: deal1 ` bigdeal @. (< 0.01&*) " 0
bigdeal=: 4 : 0
t=. 0 $ v=. y. $~ <.1.11*x.
while. x. > #t do. t=. ~. roll v end.
x. {. t
)
test=: 3 : 0 NB. run this in pre J 5.03 version
9!:1 ] qrl=: 7^5
assert. (? -: roll) 100$1e6
assert. (? -: roll) 100$2
assert. qrl -: 9!:0 ''
assert. 100 (? -: deal) 100
assert. 100 (? -: deal) 1000
assert. 100 (? -: deal) 10000
assert. 100 (? -: deal) 10001
assert. qrl -: 9!:0 ''
1
)
roll 10$100
13 75 45 53 21 4 67 67 93 38
0j0 ": qrl
823564440
10 deal 100
48 16 94 91 45 31 93 57 85 53
0j0 ": qrl
896544303