(* MT19937: the Mersenne Twister.
 *
 * Derived from v1.0 of Richard J. Wagner's implementation in C++.
 * Ported by Nick Lewycky, 2005.
 *) 
local
    val N = 624;
    val M = 397;
    val state = ref([ref(Word32.fromInt 0)]);
    val left = ref 0;

    fun private_initialize(seed, r, 0w0) = nil
    |   private_initialize(seed, r, i) =
        let
            val x = Word32.andb(Word32.+(Word32.fromInt(N)-i, Word32.*(Word32.xorb(r, Word32.>>(r, 0wx1e)), 0wx6C078965)), 0wxFFFFFFFF)
        in
            (ref x) :: private_initialize(seed, x, i - 0w1)
        end
    fun initialize(seed) =
        let
            val s = Word32.andb(seed, 0wxFFFFFFFF)
        in
            state := ((ref s) :: private_initialize(seed, s, Word32.fromInt(N-1)))
        end

    fun mixBits(u, v) = 
        (
            Word32.orb((Word32.andb(u, 0wx80000000)), (Word32.andb(v, 0wx7FFFFFFF)))
        )

    fun twist(m, s0, s1) =
        (
            Word32.xorb(m, Word32.xorb(Word32.>>(mixBits(s0, s1), 0w1), Word32.andb(0w0-Word32.andb(s1, 0w1), 0wx9908B0DF)))
        )

    fun reloadA(0, s) = ()
    |   reloadA(n, s) =
        let
            val nth = List.nth;
        in
            nth(s, 0) := twist(!(nth(s, M)), !(nth(s, 0)), !(nth(s, 1)));
            reloadA(n-1, tl(s))
        end
    fun reloadB(1, s, t) = ()
    |   reloadB(n, s, t) =
        let
            val nth = List.nth;
        in
            nth(s, 0) := twist(!(nth(t, 0)), !(nth(s, 0)), !(nth(s, 1)));
            reloadB(n-1, tl(s), tl(t))
        end
    fun reload() =
        (
            reloadA(N-M, !state);
            reloadB(M, List.drop(!state, N-M), !state);
            List.nth(!state, N-1) := twist(!(List.nth(!state, M-1)), !(List.nth(!state, N-1)), !(List.nth(!state, 0)));
            left := N;
            0
        )

    fun rand_int_noreload(x) =
        let
            val s1 = !(List.nth(!state, N - x));
            val s2 = Word32.xorb(s1, Word32.>>(s1, 0wxB));
            val s3 = Word32.xorb(s2, Word32.andb(Word32.<<(s2, 0wx7), 0wx9D2C5680));
            val s4 = Word32.xorb(s3, Word32.andb(Word32.<<(s3, 0wxF), 0wxEFC60000));
        in
            Word32.xorb(s4, Word32.>>(s4, 0wx12))
        end;

in
    fun seed(x) = 
        (
            initialize x;
            reload()
        )

    fun rand_int() =
        (
            if !left = 0 then reload() else (0);
            left := !left - 1;
            rand_int_noreload(!left + 1)
        )
end

(* What follows is an example of using the functions above. *)

fun ask_howmany() =
    (
        print "How many? ";
(* SML/NJ v110.52: *)
        Option.valOf(Int.fromString(Option.valOf(TextIO.inputLine TextIO.stdIn)))
(* SML/NJ v110.0.7:
        Option.valOf(Int.fromString(TextIO.inputLine TextIO.stdIn))
*)
    )

fun print_rand_ints(0) = ()
|   print_rand_ints(n) =
    (
        print(Word32.toString(rand_int()) ^ "\n");
        print_rand_ints(n-1)
    )

fun run() =
    (
(* SML v110.52: *)
        seed(Word32.fromInt((IntInf.toInt(Time.toSeconds(Time.now()) - 1100000000))));
(* SML v110.0.7:
        seed(Word32.fromLargeInt(Time.toSeconds(Time.now())));
*)
        print_rand_ints(ask_howmany())
    )