Fibonacci in gforth

Working through some FORTH exercises from the gforth tutorial, here is a function which generates the nth Fibonacci number:

``````: fib ( n1 n2 n3 -- n.
compute n3'th fib number, index starting at zero
first two args are starting nums, 0 1 for normal fib seq )
begin
dup 2 >
while
-rot ( n3 n1 n2 )
dup ( n3 n1 n2 n2 )
>r ( n3 n1 n2 )
+ ( n3 n4 )
r> ( n3 n4 n2 )
swap ( n3 n2 n4 )
rot ( n2 n4 n3 )
1 -
repeat
dup 0 = if
drop drop
else
dup 1 = if
drop swap drop
else
drop +
then
then
;``````

Execution:

``````christopher@nightshade ~/Repos/forth-learning\$ ./fib.fi
Gforth 0.7.3, Copyright (C) 1995-2008 Free Software Foundation, Inc.
Gforth comes with ABSOLUTELY NO WARRANTY; for details type `license'
Type `bye' to exit
0 1 0 fib . 0  ok
0 1 1 fib . 1  ok
0 1 2 fib . 1  ok
0 1 3 fib . 2  ok
0 1 4 fib . 3  ok
0 1 10 fib . 55  ok
0 1 50 fib . 12586269025  ok
0 1 70 fib . 190392490709135  ok``````

I can do, say, the 1000000th number and get a near instant result. But the integers start wrapping around long before that, so the result is not useful.

The above code can be done in a more recursive style with the RECURSE keyword, but there is not an automatic tall-call optimization, so that crashes the stack on large numbers.

A feature of the above code is use of the return stack, with the >R and R> words, to briefly save a value, so I don’t have to move the stack around so much.