/*..
	
=================================== 
Fast Fibonacci and Lucas Algorithms
===================================
	
:Source:
:http://code.google.com/p/pure-lang/source/browse/pure/examples/fibonacci.pure 
:Author: Libor Spacek (C) <libors@gmail.com\> 
:License: GPL V3
:Date: March 2011
	
Example usage:
> map f (-10..10);
[-55L,34L,-21L,13L,-8L,5L,-3L,2L,-1L,1L,0,1L,1L,2L,3L,5L,8L,13L,21L,34L,55L]
> map fibonacci (-10..10);
[-55L,34L,-21L,13L,-8L,5L,-3L,2L,-1L,1L,0L,1L,1L,2L,3L,5L,8L,13L,21L,34L,55L]
> map fastfib (-10..10);
[-55L,34L,-21L,13L,-8L,5L,-3L,2L,-1L,1L,0L,1L,1L,2L,3L,5L,8L,13L,21L,34L,55L]
> map lucas (-10..10);
[123L,-76L,47L,-29L,18L,-11L,7L,-4L,3L,-1L,2L,1L,3L,4L,7L,11L,18L,29L,47L,76L,123L]
>stats on
>(fib 987654321) $$ 0;
68.11s
>(fastfib 987654321) $$ 0;
45.42s
*/

/* Naive Fibonacci, using just the basic definition, n can be negative */
f 0 	  = 0;
f n::int  = if n < 0 then (if n and 1 then fl 0L 1L (-n) else (-(fl 0L 1L (-n))))
	    else fl 0L 1L n
	    with 
	      fl _::bigint b::bigint 1 = b; 
	      fl a::bigint b::bigint ncount::int = fl b (a+b) (pred ncount)
	    end;

/* fib: computes two successive members F(n),F(n+1) of the
   Fibonacci sequence (0,1,1,2,3,..), using the equivalences:
   F(n+1)=F(n+2)-F(n), F(2n)=(2F(n+1)-F(n))*F(n), F(2n+2)=(2F(n)+F(n+1))*F(n+1) */

fib 0 = 0L,1L; 
fib 1 = 1L,1L;
fib n::int = if n and 1 then fn2-fn,fn2 else fn,fn2-fn
when a,b = fib (n>>1); fn = ((b<<1)-a)*a; fn2 = ((a<<1)+b)*b end;

/* fibonacci: computes nth member of the Fibonacci sequence, using fib above.
   Extended to negative arguments */

fibonacci 0 = 0L;
fibonacci n::int  = if (n and 1) then fib (pred (-n)) ! 1 
		    else (-(fib (pred (-n)) ! 1)) if n<0; 
		  = fib (pred n) ! 1;

/* luc: L(n),L(n+1) terms of the Lucas sequence (2,1,3,4,..)
   computes just two bigint squares for each bit of n 
   L(n+1) is obtained from: L(n+2)-L(n), as bigint squares are
   faster than comparable general products and the pure code is cleaner as well */

luc 0 = 2L,1L; luc 1 = 1L,3L;
luc n::int = if (1 and n) then b2-a2,b2 else a2,b2-a2 // n is odd,even
     when 
       sig = if (2 and n) then 2 else -2; //  n is odd,even multiple of 2
       a,b = luc (n>>1); a2 = a*a+sig; b2 = b*b-sig // L(2n)=L(n)^2 -+2
     end;

// lucas: computes nth member of Lucas sequence using luc, extended to negative ns. 

lucas 0 = 2L;
lucas n::int 
	= if (n and 1) then (-(luc (pred (-n)) ! 1)) 
	  else luc (pred (-n)) ! 1 if n<0;
	= luc (pred n) ! 1;
 
/* fastfib: using F(2n+1) = (L(n)^2+L(n+1)^2)/5, F(2n) = L(n)*(2L(n-1)+L(n))/5
   n.b. we call luc as it is faster than fib. */

fastfib 0 = 0L; fastfib 1 = 1L;
fastfib n::int  
	= if (n and 1) then fastfib (-n) else (-(fastfib (-n))) if n<0;
	= if (n and 1) then (a*a+b*b) div 5 
	  else ( a*((z<<1)+a) div 5 when z = b-a end ) when a,b = luc (n>>1) end;