% Fibonacci numbers by fast doubling.
%
% The public fibonacci/2 relation is bounded by fib_case/1 facts, while fib_pair/3
% computes F(N) and F(N+1) together.  This exposes a logarithmic recursive
% algorithm in a small relational program instead of enumerating all predecessors.
%
% Memoization is important for the large cases: several requested Fibonacci
% numbers reuse the same half-size fib_pair/3 subproblems.
query(fibonacci(X0, X1)).

% fib_case/1 bounds the public queries, while fib_pair/3 implements the
% fast-doubling recurrence F(2n), F(2n+1) over arbitrary-size integers.

% BigInt Fibonacci via fast doubling, implemented in Prolog using generic
% decimal add/sub/mul built-ins.  The result predicate follows Eyeling's
% fibonacci.n3 output shape: N fibonacci Value.
fib_case(0).
fib_case(1).
fib_case(10).
fib_case(100).
fib_case(1000).
fib_case(10000).

% The even and odd fib_pair/3 clauses share the same half-size recursive call;
% memoization makes repeated large cases reuse those subproblems.
fib(N, Value) :- fib_pair(N, Value, _next).

fib_pair(0, 0, 1).
fib_pair(N, F, G) :-
  gt(N, 0),
  div(N, 2, Half),
  fib_pair(Half, A, B),
  mul(B, 2, Twob),
  sub(Twob, A, Twobminusa),
  mul(A, Twobminusa, C),
  mul(A, A, Aa),
  mul(B, B, Bb),
  add(Aa, Bb, D),
  mod(N, 2, 0),
  eq(F, C),
  eq(G, D).
fib_pair(N, F, G) :-
  gt(N, 0),
  div(N, 2, Half),
  fib_pair(Half, A, B),
  mul(B, 2, Twob),
  sub(Twob, A, Twobminusa),
  mul(A, Twobminusa, C),
  mul(A, A, Aa),
  mul(B, B, Bb),
  add(Aa, Bb, D),
  mod(N, 2, 1),
  add(C, D, Next),
  eq(F, D),
  eq(G, Next).

fibonacci(N, Value) :-
  fib_case(N),
  fib(N, Value).