(* Calcul de Fib(n) avec l'exponentiation rapide *)

open Modulo (* exercice 10.7 *)
open Matrix (* Programme 83 page 333 + exercice 10.10 *)

(* on calcule modulo 10^7 *)
module M1 = Modulo(struct let m = 10_000_000 end)
module M2 = Matrix(M1)

let fib n =
  let mfib = [| [| M1.one; M1.one  |];
                [| M1.one; M1.zero |] |] in
  (M2.power mfib n).(0).(1)

let () =
  assert ((fib 0 :> int) = 0);
  assert ((fib 10 :> int) = 55);
  assert ((fib 1_000_000 :> int) = 2546875)

This document was generated using caml2html