Fig. FIB-3. RTM system to compute the Nth Fibonacci number by a table look-up process.

SOLUTION 2

This scheme employs a two-Bus structure and is shown in Figure FIB-2. This design uses the same preloop structure as that in the design of solution 1. The generation of the numbers in the sequence and the indexing on N are performed in parallel. K(parallel merge) modules provide the necessary synchronization of the two operations. The upper section of the loop generates the even-indexed terms of the sequence and the lower section generates the odd-indexed terms. Both sections of the loop decrement N, and the normal exit is taken when N = 0. As in solution 1, the detection of overflow passes control out the overflow exit. More parallel (concurrent) processes will be given in Chapter 4, and in subsequent design examples.

SOLUTION 3

The fastest method for computing F(N) uses a table-lookup process and is illustrated in Figure FIB-3. Those values of F(N) less than 2^16 may be stored and retrieved from a memory; the value for F(J) is stored in the jth word of the memory. The check for N < 0 is made initially to prevent an illegal memory reference. A constant, NMAX, contains that value of N such that F(N) > (2^16)-1 and the overflow check is made against this value. With known N, this is just 2 Kevoke's.

101