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 ;
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.