(* * * * * * * * * * *
 * Resource Aware ML *
 * * * * * * * * * * *
 *
 * File:
 *   bigints.raml
 *
 * Author:
 *   Jan Hoffmann (2017)
 *
 * Description:
 *   Implementation of arbitrary precision integers.
 *
*)


type bigint = int list

let word_size = 10 (* use 2147483648 = 2^31 for OCaml's '32 bit' ints *)

(* The bigint [n_0,...,n_k] represents the sum \sum_i n_i * w^i
 * where w = word_size.
*)

(* We count the number of integer additions and multiplications in the code
 * by using the tick metric
 *)

let iplus n m = let () = Raml.tick 1.0 in n+m

let imult n m = let () = Raml.tick 1.0 in n*m

let split n = (n mod word_size, n/word_size)


let of_int n = [n]


let is_int b =
  match b with
  | [] -> true
  | n::ns ->
    match ns with
    | []   -> true
    | _::_ -> false


let to_int_opt b =
  match b with
  | [] -> Some 0
  | n::ns ->
    match ns with
    | []   -> Some n
    | _::_ -> None


(*adding an int to a bigint*)
let rec add_int b n =
  if n = 0 then
    b
  else
    match b with
    | [] -> [n]
    | m::ms ->
      let (r,d) = split (iplus n m) in
      r::(add_int ms d)


(*adding two bigints*)
let add b c =

  let rec add b c carry =
      match b with
      | [] -> add_int c carry
      | n::ns ->
        match c with
        | [] -> add_int b carry
        | m::ms ->
          let sum = iplus (iplus n m) carry in
          let (r,d) = split sum in
          r::(add ns ms d)
  in
  add b c 0

;;

(*test*)

()