(************************************************************
   random.ml		Created      : Wed Jul 31 15:07:54 2002
  			Last modified: Sat Aug 03 13:29:12 2002
  Compile: ocamlopt.opt random.ml -o random #
  Compile: ocamlc -g random.ml -o random #
************************************************************)

let random seed lambda p mu =
  let current = ref seed in
  (* result の初期値は1 *)
(*  let _ = Printf.printf "p = %d\n" p in*)
  fun () ->
    let result = !current in
    begin
      current := (lambda*result  + mu) mod p;
      result
    end

module ComparebleInt =
  struct
    type t = int
    let compare x y =
      if x < y then -1 else if x = y then 0 else 1
  end

module IntSet = (Set.Make(ComparebleInt) :
		   sig
		     type t
		     val add: int -> t -> t
		     val mem: int -> t -> bool
		     val empty: t
		   end)

let log2 v =
  let rec loop current result =
    if current = 1 then result else
    loop (current/2) (result+1)
  in loop v 0

let _ =
  let rec get_p e result =
    if e = 0 then
      result
    else
      get_p (e-1) (2*result) in
  let seed = 2 in
  let lambda = 3 in
  let mu = 0 in 
  List.iter 
  (fun lambda -> (
    Printf.printf "--- Result: lambda = %d\n" lambda;
    for e = 1 to 20 do
      let p = get_p e 1 in
      let r = random seed lambda p mu in
      let current = ref (r ()) in
      let s = ref IntSet.empty in
      let i = ref 0 in
      
      while not (IntSet.mem !current !s) do
	Printf.printf "%2d: %d\n" !i !current;    
	s := IntSet.add !current !s;
	current := r ();
(*    Printf.printf "NEXT %d\n" !current;    *)
	incr i;
      done;
      Printf.printf "--- Result: (e,p,T) = (%2d,%8d,%8d)\n" e p (log2 !i)
    done))
    (let rec make_list i = 
      if i = 6 then []
      else (8*i+3) :: (make_list (i+1))
    in make_list 0)