Search

The article presents information on the publication of a book "Applied Statistics, Algorithms," relevant to statistics, by the Royal Statistical Society in cooperation with the Science Research Council's Working Party on Statistical Computing. A policy statement describing the editorial policy appears in "Applied Statistics," Vol. 1. No. 1 (1968). A support paper describing the expected contents of the external specification and making recommendation for the layout of algorithms and for programming strategy will appear in the following issue.

The paper describes a scheme for symbolic manipulation of index expressions which arise as a by-product of the symbolic manipulation of expressions in the matrix calculi described by the authors in a previous paper. This scheme attempts program optimization by transforming the original algorithm rather than the machine code. The goal is to automatically generate code for handling the tedious address calculations necessitated by complicated data structures. The paper is therefore preoccupied with "indexing by position." The relationship of "indexing by name" and "indexing by position" is discussed. [ABSTRACT FROM AUTHOR]

The article presents several research papers relating to algorithms. The paper "Greatest Common Divisor of n Integers and Multipliers" presents an algorithm which calculates the greatest common divisor, IGCD, of n integers. Details of the method and comparisons to other algorithms are also given. The algorithm is a new version of the Euclidean algorithm for n integers. The n-1 calculations of the greatest common divisor of two integers is accomplished by means of a modified version of the Blankinship algorithm. The paper "Exponential Integral Ei (x)" presents the results of one phase of research carried out at the Jet Propulsion Laboratory, California Institute of Technology, under Contract NAS7-100, sponsored by the National Aeronautics and Space Administration. It presents an algorithm which was compiled and executed without any modification on a UNIVAC 1108 computer. An unfortunate precedent has been set in several recent algorithms of using an illegal FORTRAN construction.

The QR iteration for the eigenvalues of a symmetric tridiagonal matrix can be accelerated by incorporating a sequence of origin shifts. The origin shift may be either subtracted directly from the diagonal elements of the matrix or incorporated by means of an implicit algorithm. Both methods have drawbacks: the direct method can unnecessarily degrade small eigen-values, while the implicit method can effectively loose the shift and thereby retard the convergence. This paper presents a new method which has neither drawback. [ABSTRACT FROM AUTHOR]

Describes a computer program for the implementation of graph algorithms which wins Shannon Switching Games. Difference in the goals between players of the game; Existence of a winning strategy between players; Effect of ease of communication between players on computer program demonstration.

Given the horizontal and vertical projections of a finite binary pattern f, can we reconstruct the original pattern f? In this paper we give a characterization of patterns that ore reconstructable from their projections. Three algorithms ore developed to reconstruct both unambiguous and ambiguous patterns, it is shown that an unambiguous pattern can be perfectly reconstructed in time m × n and that a pattern similar to an ambiguous pattern can also be constructed in time m × n, where m, n are the dimensions of the pattern frame. [ABSTRACT FROM AUTHOR]

This paper is concerned with a review and examination of several existing algorithms for the zero-one programming problem. Computational experience is summarized. The machine time and storage requirements of several of the algorithms are compared over several test problems of small and intermediate size. Computer experiments still provide little hope of solving problems with over 100 variables with a reasonable amount of machine time. [ABSTRACT FROM AUTHOR]

The article discusses the computation of rational approximations using existing algorithms. In a recent paper it is shown that minimax logarithmic approximations are optimal for square root calculations, making the minimax logarithmic problem of practical interest. The authors point out how rational approximations which are best with respect to maximum logarithmic error can be computed by existing algorithms. Suppose one wishes to approximate a positive continuous function "f" by a positive rational function R, then the logarithmic error at a point x is log (f(x))-- log (R(x)). The approximation problem is thus equivalent to ordinary approximation of continuous function g = log (f) by log {R).

Pollack has proposed on algorithm for converting decision tables into flowcharts which minimize subsequent execution time when compiled into a computer program. Two modifications a this algorithm are proposed. The first relies on Shannon's noiseless coding theorem and the communications concept of entropy but does not completely test the ELSE Rule. The second modification completely tests the ELSE Rule but results in more executions than the first modification. Both modifications result in lower execution time than Pollack's algorithm. However, neither modification guarantees a globally optimal solution. [ABSTRACT FROM AUTHOR]

An algorithm for Filon quadrature is described. Considerable attention has been devoted to an analysis of the round-off and truncation errors. The algorithm includes an automatic error control feature. [ABSTRACT FROM AUTHOR]

The article focuses on key-to-address transformation techniques and the results of a performance study on large existing formatted files. The experimental results comparing six commonly used key-to-address transformation techniques were presented by the researchers. One transformation in the study referred to as "generalized radix transformation method" is an elaborate technique based on radix transformation. This method of transformation consists of a radix transformation algorithm as well as hardware implementation to carry out the steps of this transformation in an efficient manner. The intricacy of the generalized radix transformation method has motivated researchers to conduct further studies of the technique. The additional results are presented after a brief description of the basic algorithm used in this generalized radix transformation method. Additional experiments on the files showed that the distribution of the keys was particularly sensitive to the arbitrary selection of an 8-bit grouping.

The article provides an analysis of key-to-address transformation techniques and the results of a performance study on large existing formatted files. The experimental results comparing six commonly used key-to-address transformation techniques were presented by the researchers. One transformation in the study referred to as "generalized radix transformation method" is an elaborate technique based on radix transformation. This method of transformation consists of a radix transformation algorithm as well as hardware implementation to carry out the steps of this transformation in an efficient manner. The intricacy of the generalized radix transformation method has motivated researchers to conduct further studies of the technique. The additional results are presented after a brief description of the basic algorithm used in this generalized radix transformation method. Additional experiments on the files showed that the distribution of the keys was particularly sensitive to the arbitrary selection of an 8-bit grouping.

Comments on articles published in earlier issues of the journal "Communications of the ACM." Discussion on techniques used in automatic segmentation of cyclic program structures;Focus on diverse techniques to assure the integrity of a data base;Information on algorithms to be followed by primitives in order to maximize the amount of parallel activity in a data base.

The article focuses on a paper indicating the error of algorithmic language ALGOL 60 pointed up by the Algorithm 355 construct in the October 1969 issue of the periodical "Communications of the Automation for Computing Machinery." The procedure statement "p" occurs in the body of this procedure, showing "p" to be a procedure without parameters. As originally submitted, the algorithm contained several procedure statements in which p was replaced by a procedure statement. It is possible that the authors of ALGOL 60 intended to permit this but they did not do so. The author's original form may have been more in the sprit of the ALGOL 60 report but the published form confirms to the syntax of ALGOL 60 as described in the report.

The article discusses algorithm 446 with regard to ten subroutines for the manipulation of Chebyshev series. The operations performed in the article are the construction of the Chebyshev approximation of functions, the evaluation of the series or their derivative, the integration or differentiation and the construction of negative or fractional powers of such a series. The subroutines are written in ANSI Fortran. They have been used without modification on such computers as the IBM-7094, IBM-360/93 and Univac 1108. The ten subroutines are considered as a single set, principally because they all use the same storage philosophy. All information is transmitted through the CALL-sequence rather than through the use of COMMON statements. Therefore, the user must provide storage for all the series in his main program, taking into account that all operations are performed in double precision. The coefficients of each series occupy a one-dimensional double-precision array according to the rules of ANSI Fortran. When several Chebyshev series are being manipulated, it is convenient to store all the series in a matrix.

Items can be retrieved from binary trees grown with a form of the Algorithm Quicksort in an average time proportional to log n, where n is the number of items in the tree. The binary trees grown by this algorithm sometimes have some branches longer than others; therefore, it is possible to reduce the average retrieval time by restructuring the tree to make the branches as uniform in length as possible. An algorithm to do this is presented. The use of this algorithm is discussed, and it is compared with another which restructures the tree after each new item is added. [ABSTRACT FROM AUTHOR]

Presents a notation for describing the semantics of data structures. Implementation facility which could be a part of a programming language; Expression of the semantics of an algorithm; Efficiency of the structures.

Reports on developments concerning the legal protection of computer programming. Patentability of algorithms; Summary of the vacillation in court and administrative rulings in computer programming; Proposals made for the legislation in the said area.

An integral equation is derived for the generating function for binary tree values, the values reflecting sorting effort. The analysis does not assume uniformly distributed branching ratios, and therefore is applicable to a family of sorting algorithms discussed by Hoare, Singleton, and van Emden. The solution to the integral equation indicates that using more advanced algorithms in the family makes only minor reductions in the expected sorting effort, but substantially reduces the variance in sorting effort. Statistical tests of the values of several thousand trees containing up to 10,000 points have given first, second, and third moments of the value distribution function in satisfactory agreement with the moments computed from the generating function. The empirical tests, as well as the analytical results, are in agreement with previously published results for the first moment in the cases of uniform and nonuniform distribution of branching ratio, and for the second moment in the case of uniform distribution of branching ratio. [ABSTRACT FROM AUTHOR]

A proof is given of the correctness of the algorithm "Find." First, an informal description is given of the purpose of the program and the method used. A systematic technique is described for constucting the program proof during the process of coding it, in such a way as to prevent the intrusion of logical errors. The proof of termination is treated as a separate exercise. Finally, some conclusions relating to general programming methodology are drawn. [ABSTRACT FROM AUTHOR]

This article discusses several algorithms applicable to computer programming. In programs for special series summation, the algorithm requires only integer arithmetic and can be implemented in algebraic languages. Changes in Coulomb wave functions that will not completely eliminate the overflow problems encountered in the generation of intermediate arrays are presented.

This article presents information on a procedure that is a part of a large program which produces the card stunts for the Stanford University football game half-times. The initial development was done by L. Breed, L. Tesler, and J. Sauter. The author made many further developments on this program which included producing an algorithm for coloring in polygonal regions. Prior to the development of this algorithm, there were many cases which did not work. The larger program takes as input an English description of the stunts and produces as output an image of each flip, as a rectangle that has 45 rows with 77 seats in each row. The main program, which will be considered the driver program for the purpose of the procedure drawarea, does all of the handling of the definition of regions and also the printing of the images. It should be mentioned that the procedure drawarea in the actual program is just part of a larger procedure and that all of the parameters are global in order to increase efficiency.

The downhill method is a numerical method for solving complex equations f(z) = 0 on which the only restriction is that the function w = f(z) must be analytical. An introduction to this method is given and a critical review of relating literature is presented. Although in theory the method always converges, it is shown that a fundamental dilemma exists which may cause o breakdown in practical applications. To avoid this difficulty and to improve the rate of convergence toward a root, some modifications of the original method are proposed and a program (FORTRAN) based on the modified method is given in Algorithm 365. Some numerical examples are included. [ABSTRACT FROM AUTHOR]

Given a set of expressions which are to be compiled, methods are presented for increasing the efficiency of the object code produced by first factoring the expressions, i.e. finding a set of subexpressions each of which occurs in two or more other expressions or subexpressions. Once all the factors have been ascertained, a sequencing procedure is applied which orders the factors and expressions such that all information is computed in the correct sequence and factors need be retained in memory a minimal amount of time. An assignment algorithm is then executed in order to minimize the total number of temporary storage cells required to hold the results of evaluating the factors. In order to make these techniques computationally feasible, heuristic procedures are applied, and hence global optimal results are not necessarily generated. The factorization algorithms are also applicable to the problem of factoring Boolean switching expressions and of factoring polynomials encountered in symbol manipulating systems. [ABSTRACT FROM AUTHOR]