modular_exponentiation.ml

module V1 = struct (* runs in 2.36s *)
  let rec pow ~mod_ x = function
    | 0 -> 1
    | n when n mod 2 = 0 ->
        let x = pow ~mod_ x (n/2) in
        (x * x) mod mod_
    | n -> (pow ~mod_ x (n-1) * x) mod mod_
end

module V2 = struct (* runs in 2.02s *)
  let rec pow ~mod_ x = function
    | 0 -> 1
    | n when n mod 2 = 0 ->
        pow ~mod_ ((x*x) mod mod_) (n/2)
    | n -> (pow ~mod_ x (n-1) * x) mod mod_
end

module V3 = struct (* runs in 2.00s *)
  let rec pow ~mod_ x = function
    | 0 -> 1
    | n when n land 1 = 0 ->
        pow ~mod_ ((x*x) mod mod_) (n asr 1)
    | n -> (pow ~mod_ x (n-1) * x) mod mod_
end

module V4 = struct (* runs in 1.54s *)
  let pow ~mod_ x n =
    let x = ref x in
    let n = ref n in
    let res = ref 1 in
    while 0 <> !n do
      if !n land 1 = 1 then
        res := (!res * !x) mod mod_;
      n := !n asr 1;
      x := (!x * !x) mod mod_;
    done;
    !res
end

module V5 = struct (* runs in 1.55s *)
  let pow ~mod_ x n =
    let rec aux res x = function
      | 0 -> res
      | n ->
        let res =
          if n land 1 = 1 then (res * x) mod mod_
          else res
        in
        let x = (x * x) mod mod_ in
        aux res x (n asr 1)
    in
  aux 1 x n
end

let () =
  let r = ref 0 in
  for n = 1_000_000_000 to 1_000_000_000 + 1_000 do
    for x = 1_000_000 to 1_000_000 + 1_000 do
      r := !r + V5.pow ~mod_:1_000_000_009 x n
    done
  done;
  Printf.printf "%d\n" !r