(** Power function implementations for built-in integers *)

open Builtin
open Basic_arithmetics;;

(* Naive and fast exponentiation ; already implemented in-class.
 *)

(** Naive power function. Linear complexity
    @param x base
    @param n exponent
 *)
let pow x n =
  let rec pow_rec x1 n =
    match n with
        0 -> x1
      | n -> pow_rec (x1*x) (n-1)
  in pow_rec 1 n;;

(** Fast integer exponentiation function. Logarithmic complexity.
    @param x base
    @param n exponent
 *)
let power x n =
  if n = 0 then 1 else
  let rec power_rec x1 n =
    match n with
        1 -> x1
      | n when modulo n 2 = 0 -> power_rec (x1 * x1) (n/2)
      | n -> x1 * power_rec (x1 * x1) ((n-1)/2)
  in power_rec x n;;

(* Modular expnonentiation ; modulo a given natural number smaller
   max_int we never have integer-overflows if implemented properly.
 *)

(** Fast modular exponentiation function. Logarithmic complexity.
    @param x base
    @param n exponent
    @param m modular base
 *)
let mod_power x n m =
  if n = 0 then
    1
  else
    let rec mod_power_rec c e =
      let c = modulo (x * c) m
      in if e < n then
          mod_power_rec c (e+1)
        else
          c
    in mod_power_rec 1 1;;

(* Making use of Fermat Little Theorem for very quick exponentation
   modulo prime number.
 *)

(** Fast modular exponentiation function mod prime. Logarithmic complexity.
    It makes use of the Little Fermat Theorem.
    @param x base
    @param n exponent
    @param p prime modular base
 *)
let prime_mod_power x n p =
  if x = 0 then
    0
  else
    mod_power x (modulo n (p - 1)) p;;