Fig. FIB-I. RTM system to compute the Nth Fibonacci number by a sequential process.
The second question to ask is about the various limits of the computation. The natural representation for F(N) is in a single 16-bit word, which means that F(N) cannot be greater than 2^16-1. How fast does F(N) grow? We can answer that question by finding a simple upper bound for F(N). For example:
F(N +1) = F(N) + F(N-l)
F(N+1) > F(N-1) + F(N-l) = 2*F(N-l)
We simply ignore the additional contribution from F(N) being greater than F(N-l). The above formula shows that F(N) grows by at least a factor of 2 for each increment of 2 in N; thus by the time N = 32, F(N) > 2^16 and has overflowed the word. Thus, the design specifications must include an overflow return as an additional part of the output representation. In addition a check should be made to insure that N > 0; an underflow exit should be included for the condition that N <0.
The third question is to decide on a basic method of computation. The simplicity of the recurrence relation suggests computing F(N) simply by adding it
99