source code
(* The Computer Language Benchmarks Game
* http://benchmarksgame.alioth.debian.org/
*
* contributed by Christophe TROESTLER
* modified by Matías Giovannini
*)
open Printf
open Big_int
let ( +$ ) = add_big_int
let ( *$ ) = mult_int_big_int
let ( /$ ) = div_big_int
(* Entier part of the linear fractional transform qrst of x *)
let ext (q,r,s,t) x = int_of_big_int ((x *$ q +$ r) /$ (x *$ s +$ t))
(* Multiply small int matrix qrst by big int matrix qrst' (small on left) *)
let mml (q,r,s,t) (q',r',s',t') =
q *$ q' +$ r *$ s', q *$ r' +$ r *$ t',
s *$ q' +$ t *$ s', s *$ r' +$ t *$ t'
(* Multiply big int matrix qrst by small int matrix qrst' (small on right) *)
let mmr (q,r,s,t) (q',r',s',t') =
q' *$ q +$ s' *$ r, r' *$ q +$ t' *$ r,
q' *$ s +$ s' *$ t, r' *$ s +$ t' *$ t
let unit = (unit_big_int,zero_big_int,zero_big_int,unit_big_int)
let next z = ext z 3
and safe z n = ext z 4 == n
and prod z n = mml (10, -10*n, 0, 1) z
and cons z k =
let den = 2*k + 1 in
mmr z (k, 2*den, 0, den)
let rec digit k z n row col =
if n == 0 then printf "%*s\t:%i\n" (10-col) "" (row+col) else
let d = next z in
if safe z d then
if col = 10 then begin
let row = row + 10 in
printf "\t:%i\n%i" row d;
digit k (prod z d) (n-1) row 1
end else begin
print_int d;
digit k (prod z d) (n-1) row (col+1)
end
else digit (k+1) (cons z k) n row col
let digits n = digit 1 unit n 0 0
let () = digits (try int_of_string (Array.get Sys.argv 1) with _ -> 27)