Fig. FIB-3. RTM system to compute the Nth Fibonacci number by a table look-up process.
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.
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.