November 1970 - Vol. 13 No. 11
Features
An interactive display for approximation by linear programming
An interactive program with a graphical display has been developed for the approximation of data by means of a linear combination of functions (including splines) selected by the user. The coffiecients of the approximation are determined by linear programming so as to minimize the error in either the L1 or L∞ norm. Auxiliary conditions such as monotonicity or convexity of the approximation can also be imposed. This interactive system is described and several examples of its use are given.
Multi-attribute retrieval with combined indexes
In this paper a file organization scheme designed to replace the use of the popular secondary index filing scheme (or inverted files on secondary key fields) is described. Through the use of redundancy and storing keys (or access numbers of the records) that satisfy different combinations of secondary index values in “buckets,” it is possible to retrieve all keys satisfying any input query derived from a subset of fields by a single access to an index file, although each bucket may be used for many combinations of values and a combination of buckets may be required for a given query.
The method which, in its degenerate case, becomes the conventional secondary index filing scheme works similarly but has the following advantages: (1) the elimination of multiple accesses in many cases; (2) the elimination of false drops; (3) the elimination of computer time to perform intersection of key sets each qualified for one secondary index field only; and (4) the avoidance of long strings of keys when an index field appearing in a query has very few possible values. Redundancy, in some cases, is the same as the secondary indexing method. In the general case, trade-off between the number of accesses for query and redundancy exists.
A multiple-precision division algorithm
A generalized division algorithm for use with positive integral operands is presented. Depending upon the algebraic relationship of the first two ciphers of the divisor, one or at most two adjustments to the original divisor and dividend must be performed before the division operation can be initiated. The uniqueness of this method will cause each trial cipher in the quotient to be either equal to or one greater than its final replacement.
NEATER2: a PL/I source statement reformatter
NEATER2 accepts a PL/I source program and operates on it to produce a reformatted version. When in the LOGICAL mode, NEATER2 indicates the logical structure of the source program in the indentation pattern of its output. Logic errors discovered through NEATER2 logical analysis are discovered much more economically than is possible through compilation and trial runs. A number of options are available to give the user full control over the output format and to maximize the utility of NEATER2 as an aid during the early stages of development of a PL/I source deck. One option, USAGE, causes NEATER2 to insert into each logical unit of coding a statement which will cause the number of times each one is executed to be recorded during execution. This feature is expected to provide a major aid in optimization of PL/I programs.
A new method of hash coding is presented and is shown to possess desirable attributes. Specifically, the algorithm is simple, efficient, and exhaustive, while needing little time per probe and using few probes per lookup. Performance data and implementation hints are also given.
A nonrecursive list compacting algorithm
A simple nonrecursive list structure compacting scheme or garbage collector suitable for both compact and LISP-like list structures is presented. The algorithm avoids the need for recursion by using the partial structure as it is built up to keep track of those lists that have been copied.
Recorded magnetic tape for information interchange (1600 CPI, phase encoded)
This proposed American National Standard has been accepted for publication by American National Standards Committee X3, Computers and Information Processing. In order that the final version of the proposed standard reflect the largest public consensus, X3 authorized publication of this document to elicit comment and general public reaction, with the understanding that such a working document is an intermediate result in the standardization process and is subject to change, modification, or withdrawal in part or in whole. Comments should be directed to the X3 Secretary, Business Equipment Manufacturers Association, 1828 L Street, NW, Washington, DC 20036.—C.K.
This proposed American National Standard has been accepted for publication by American National Standards Committee X3, Computers and Information Processing. In order that the final version of the proposed standard reflect the largest public consensus, X3 authorized publication of this document to elicit comment and general public reaction, with the understanding that such a working document is an intermediate result in the standardization process and is subject to change, modification, or withdrawal in part or in whole. Comments should be directed to the X3 Secretary, Business Equipment Manufacturers Association, 1828 L Street, NW, Washington, DC 20036.—C.K.
A generalized method for generating argument/function values
For any finite set of argument/function pairs, an algorithm can be automatically constructed which, on presentation of any argument, will generate its proper function value. Arguments are necessarily unique although functions may be duplicated; i.e. a many-to-one relationship is permitted. For purposes of illustration here, function and argument values are each assumed to occupy a single computer word.
Correction to “logical” arithmetric on computers with two’s complement binary arithmetic
In reference [1] algorithms for performing arithmetic with unsigned two's complement operands were described. The scheme for division was implemented in a set of multiple-precision floating-point arithmetic routines [2]. User experience with those routines showed that there is one case where the algorithm fails [3]. We give here a modification to the algorithm which eliminates the error condition. Equations are numbered beginning with (20), so that we may refer to equations in the original paper as well.
Comment on the working set model for program behavior
In the paper “The Working Set Model for Program Behavior” by Peter Denning [Comm. ACM 11, 5 (May 1968), 323-333], an algorithm is described for the management of a paged memory under demand paging. In the process of analyzing this model, the author presents what appears to be an incorrect expression for &PHgr;(&tgr;), the real-time rate at which page faults occur in the system [eq. (13)]. Under the assumptions made in the article it appears that the best one can do in this area is to place an upper and lower bound on &PHgr;(&tgr;). These bounds are given below.
