"Fibonacci number series using a recursive algorithm and an aproximation through
 the use of the Golden Ration"

" BEWARE: with double floating point format, used in Virtue in conventional
  computor architectures, the maximum Fibonacci number before FP Infinity
  is sligtly less then fib(1500)! "

'Welcome to the Fibonacci algorithms' PRINT.

MONADIC
		DUP 2 < @%a IF JUMP
		DUP 1 - fibonacci EXECUTE SWAP 2 - fibonacci EXECUTE + RETURN
	%a	DISCARD
		1
	;
@fibonacci SET.
'<number> fibonacci: a double recursive algorithm (fib(n) = fib(n-1) + fib(n-2)'
PRINT.


"With the OPERATOR and using RESULT:"
MONADIC
	MONADIC
		DUP 2 < @%a IF JUMP
		DUP 1 - fib SWAP 2 - fib + RETURN
	%a	DISCARD
		1;
	RESULT; OPERATOR
@fib SET.
'<number> fib: the same algorithm but as an OPERATOR using RESULT' PRINT.

" The recursive algorithm using AT/GET memoisation "

MONADIC
	DUP GET
	DUP RANK CHECK
	FUNCTION
			LEFT DUP
			MONADIC
				DUP 2 < @%a IF JUMP
				DUP 1 - memfib EXECUTE SWAP 2 - memfib EXECUTE + RETURN
			%a	DISCARD
				1; EXECUTE
			SWAP
			AT ASSIGN; IF_YES
	RIGHT IF_NO;
@memfib SET.
'<number> memfib: again the same algorithm, but memoised using AT/GET' PRINT.


" The recursive algorithm using RESULT "
MONADIC
	MONADIC
		DUP 2 < @%a IF JUMP
		DUP 1 - resfib EXECUTE SWAP 2 - resfib EXECUTE + RETURN
%a		DISCARD
		1;
	RESULT;
@resfib SET.
'<number> resfib: the recursive algorithm using RESULT, as a function' PRINT.


" Fibonacci numbers approximation using the golden ratio "

"Prepare the golden ratio - phi"
NILADIC
	5 SQRT 1 + 2 /;
DUP EXECUTE
					DUP 'phi is ' SWAP, PRINT
SWAP AT SET.

"We will use the golden ratio constant under the name of the function generating it"

VARS 1 MONADIC
	"F(n) = (phi^n - psi^n)/sqrt(5)"

	"n" 1 + @&1 SET

	NILADIC
		5 SQRT 1 + 2 /; GET

	DUP RECIPROCAL NEGATIVE "psi"

	&1 POWER
	SWAP &1 POWER
	SWAP SUBTRACT

	5 SQRT DIVIDE;

@fibon SET.
'<number> fibon: Fibonacci numbers approximation using the golden ratio, and
AT/GET memoisation' PRINT.


"Another way of writing the same:"

VARS 2 MONADIC
	"F(n) = (phi^n - psi^n)/sqrt(5)"

	"n" 1 + @&1 SET

	NILADIC 5 SQRT 1 + 2 /; RESULT @&2 ASSIGN "phi" &1 POWER

	&2 RECIPROCAL NEGATIVE "psi" &1 POWER 

	SUBTRACT

	5 SQRT DIVIDE;

@resfibon SET.
'<number> resfibon: The above algorithm written with RESULT' PRINT.