Help / Release / J 5.03 / ? and ?. Improved

From J Wiki
Jump to navigation Jump to search


>> << Pri JfC LJ Phr Dic Voc !: Rel NuVoc wd Help Release



? and ?. Improved

initial writing: 2003-10-11
last updated: 2005-03-15


? (and ?.) have been improved in the following ways:


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



>> << Pri JfC LJ Phr Dic Voc !: Rel NuVoc wd Help Release