previous | contents | next

least four variable locations is needed with a data operations part, a DMgpa, to carry out the updating of <v1>. The control part is shown on the left. In this implementation we have placed an additional data operations part to carry out the computation of (v 1 -v4) * sign (v3). This operation could have been carried out in the DMgpa however, Thus, we have defined the meaning (or semantics) of the Algol loop in terms of RTM primitives, although we have made the simplifying assumption that the variables are the two's complement 16-bit integers represented by the RTM system. The control part is somewhat like a K(subroutine), together with a number of implicit connections to the DM part to manipulate the controlling loop variables.

APPLICATION

Figure FL-3 shows an implementation of the sum-of-integers problem, Chapter 2, using the K(for loop). Note that in this case only one control step has been saved. There is also an implicit assumption that the variable <v4> has been loaded into the DM part of the for loop module. Hopefully this implementation is somewhat easier to understand as it separates the control of the algorithm from the part of the algorithm performing the calculation.

PROBLEMS

1. Redesign the K(for loop), Figure FL-2, using sequential Ke's to carry out the (vi -v4)*sign (v3) > 0 computation.

2. Since there is a problem with the K(for loop) having access to variables which are used in the rest of the system (do part), as a practical matter almost all K(for loops) would have to be tailored to the particular application. But the customizing process variables would not have to be duplicated as they can be taken from other parts of the system. Show a special K(for-loop) for the sum- of-integers problem, Figure FL-3.

3. Use the K(for-loop) and K(conditional-execute) to solve the ones count problem.

KEYWORDS: Functions, generation, overflow, underflow

• The Fibonacci sequence is defined by the relations:

• F(N+1) = F(N) + F(N-1) with F(0) = 0 and F(1) - 1

The first few values of the sequence are: 0,1,1,2,3,5,8,... The Fibonacci sequence has a fascinating history, showing up in many odd guises. For our purposes, they can illustrate the task of function generation where some implicit relationships are given, rather than a direct explicit formula.

PROBLEM STATEMENT

Design a Fibonacci number generator that takes N as input and computes F(N).

DESIGN CONSIDERATIONS

The first design question is to ask about the interface between the system (the number generator) and the external world: what information is to be provided as input and output and in what representation? The matter appears quite simple here: the input is a 16-bit number held in a 16-bit word; similarly the output is a 16-bit number representing F(N).

98

previous | contents | next