Fig. FIB-2. RTM system to compute the Nth Fibonacci number by a parallel process.
up according to the formula. The only concern is that all computations for F(1), F(2),... up to F(N) are being made, even though they are not themselves wanted. Having settled on a basic method does not determine fully the actual processing, as we show below by giving several designs.
SOLUTION I
Figure FIB-i shows a straightforward design for a Fibonacci number generator. F(0) and F(1) are generated at the beginning of the process and the normal exit is taken for N = 0,1; for N greater than I but small enough not to cause overflow, the loop is performed N-1 times yielding F(N), N is decremented by 1 on each pass through the loop, and the normal exit is taken when N = 0. For those N such that F(N) >2^16, overflow will occur and the overflow exit is taken.
100