src/Tools/Metis/src/Random.sml
author wenzelm
Mon, 13 Apr 2020 22:08:14 +0200
changeset 71751 abf3e80bd815
parent 39429 126b879df319
permissions -rw-r--r--
tuned NEWS;
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
39348
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
     1
(*  Title:      Tools/random_word.ML
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
     2
    Author:     Makarius
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
     3
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
     4
Simple generator for pseudo-random numbers, using unboxed word
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
     5
arithmetic only.  Unprotected concurrency introduces some true
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
     6
randomness.
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
     7
*)
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
     8
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
     9
structure Random :> Random =
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    10
struct
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    11
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    12
(* random words: 0w0 <= result <= max_word *)
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    13
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    14
(*minimum length of unboxed words on all supported ML platforms*)
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    15
val _ = Word.wordSize >= 30
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    16
  orelse raise Fail ("Bad platform word size");
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    17
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    18
val max_word = 0wx3FFFFFFF;
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    19
val top_bit = 0wx20000000;
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    20
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    21
(*multiplier according to Borosh and Niederreiter (for modulus = 2^30),
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    22
  see http://random.mat.sbg.ac.at/~charly/server/server.html*)
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    23
val a = 0w777138309;
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    24
fun step x = Word.andb (a * x + 0w1, max_word);
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    25
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    26
fun change r f = r := f (!r);
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    27
local val rand = (*Unsynchronized.*)ref 0w1
39426
c551ce5f614a make "Unprotected concurrency introduces some true randomness." be true;
blanchet
parents: 39408
diff changeset
    28
in fun nextWord () = ((*Unsynchronized.*)change rand step; ! rand) end;
39348
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    29
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    30
(*NB: higher bits are more random than lower ones*)
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    31
fun nextBool () = Word.andb (nextWord (), top_bit) = 0w0;
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    32
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    33
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    34
(* random integers: 0 <= result < k *)
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    35
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    36
val max_int = Word.toInt max_word;
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    37
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    38
fun nextInt k =
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    39
  if k <= 0 orelse k > max_int then raise Fail ("next_int: out of range")
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    40
  else if k = max_int then Word.toInt (nextWord ())
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    41
  else Word.toInt (Word.mod (nextWord (), Word.fromInt k));
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    42
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    43
(* random reals: 0.0 <= result < 1.0 *)
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    44
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    45
val scaling = real max_int + 1.0;
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    46
fun nextReal () = real (Word.toInt (nextWord ())) / scaling;
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    47
6f9c9899f99f new version of the Metis files
blanchet
parents:
diff changeset
    48
end;