July 1969 - Vol. 12 No. 7
Features
Polynomial and spline approximation by quadratic programming
The problem of approximation to a given function, or of fitting a given set of data, where the approximating function is required to have certain of its derivatives of specified sign over the whole range of approximation, is studied. Two approaches are presented, in each of which quadratic programming is used to provide both the constraints on the derivatives and the selection of the function which yields the best fit. The first is a modified Berstein polynomial scheme, and the second is a spline fit.
Generating pseudorandom numbers on a two’s complement machine such as the IBM 360
The familiar multiplicative congruential generator is examined in the context of the type of two's complement arithmetic used in the IBM 360 series. Different sequences of residues are considered and relationships established among them. It is shown that a sequence of positive and negative residues may be produced more simply and econimically than with the conventional approach and yet have twice the period of the latter without loss of desirable statistical properties. Another easily generated sequence involving absolute values is also shown to have twice the period but with the less attractive statistical properties. The statistical properties of these sequences are given and related to previously established criteria.
It is shown how a novel method for computing (related) inner products can accelerate the pricing phase of LP algorithms. Other LP applications are indicated.
Some methods for contour mapping by means of a digital plotter are dicussed, and a new method is presented that is simple enough to be implemented by programs with a rather small number of instructions (about 120 FORTRAN IV instructions are required). Comparisons with some methods proposed by other authors are also performed.
A FORTRAN IV program implementing the proposed method is availabel at the Istituto di Elettrotecnica ed Elettronica, Politecnico di Milano.
Some techniques for using pseudorandom numbers in computer simulation
An alogorithm is described by which uniform pseudorandom integers may be used to construct binary “numbers” in which the probability that each bit in the word is a 1-bit and can assume any desired parameter value.
Techniques for making use of such “numbers” in simulation programming are described.
Block structures, indirect addressing, and garbage collection
Programming languages have included explicit or implicit block structures to provide a naming convenience for the programmer. However, when indirect addressing is used, as in SNOBOL, naming constraints may be introduced. Two modifications to SNOBOL are described, resulting in two desirable consequences: (1) naming constraints disappear even when there is indirect addressing within function definitions; and (2) there is a significant saving in the number of calls to the garbage collector, because some garbage is collected, at little expense, each time a function returns to its calling program. These modifications have been implemented as an extension to a SNOBOL dialect.
On the expected lengths of sequences generated in sorting by replacement selecting
In the replacement-selecting technique of sorting, one is interested in the ratio Lj of the expected length of the jth sequence generated by the technique to the number of memory cells used. Using complex-variable theory, it is shown that Lj → 2 and that, asymtotically, the average interval between sign changes of Lj — 2 is 2.6662.
