28 lines
614 B
OCaml
28 lines
614 B
OCaml
open List
|
|
;;
|
|
let rec bin n =
|
|
if n < 2 then [n mod 2 = 1]
|
|
else bin (n/2) @ [n mod 2 = 1]
|
|
;;
|
|
let cut = function
|
|
| [] -> []
|
|
| _ :: x -> x
|
|
;;
|
|
let multiply a b =
|
|
let ((p, q), (r, s)) = a in
|
|
let ((t, u), (v, w)) = b in
|
|
((p*t+q*v, p*u+q*w), (r*t+s*v, r*u+s*w))
|
|
;;
|
|
let fib n =
|
|
let rec f p q r =
|
|
if length r = 1 then
|
|
if nth r 0 then (multiply p q, q)
|
|
else (p, q)
|
|
else
|
|
let (pp, qq) = f p q (cut r) in
|
|
let qqq = multiply qq qq in
|
|
if nth r 0 then (multiply pp qqq, qqq)
|
|
else (pp, qqq) in
|
|
f ((1L, 0L), (0L, 1L)) ((1L, 1L), (1L, 0L)) (bin n) |> fst |> fst |> snd
|
|
;;
|