Fibonacci number example

This is a Fibonacci element computation from one of the regression tests. It’s something of an odd mix, dating to when CALL and RETURN weren’t implemented yet.

This program takes an input x, which the program does not modify, and eventually produces an output answer containing the xth Fibonacci number. If x is too large, overflow will eventually be detected during addition, the R(ange) flag will be set, and answer will come back all ones.

Sample code

    ; Compute 'x'th Fibonacci number, 0 <= x <= 53

    unsigned x              ; input to fib subroutine
    x = 53                  ; seeking 53rd Fibonacci number
    jump fib                ; go compute it
back:                       ; call and return were not tested
    halt                    ; answer in last stored register

fib:
    unsigned answer         ; output from fib subroutine
    unsigned i              ; highest computed x
    unsigned next           ; temporary new answer
    unsigned prev           ; previous answer

    i = 1                   ; special case when x <= 1
    cmp x - i
    jump <= small

    prev = 0                ; fib(0)
    answer = 1              ; fib(1)

loop:
    next = prev + answer    ; fib(x+1) = fib(x) + fib(x-1)
    jump +t toobig          ; arithmetic overflow?
    i = i + 1               ; computed one more term
    prev = answer           ; keep previous two terms
    answer = next
    cmp x - i               ; have xth term yet?
    jump != loop            ; no, keep going
    jump back               ; yes, done

small:
    answer = x              ; fib(x) = x when x <= 1
    jump back               ; done

toobig:
    answer = 0 - 1          ; out of range indication for test
    jump back               ; done