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