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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s