Search

This article discusses various issues related to the three-dimensional plot programming and algorithm 483. PLOT3D will accept three-dimensional data in various forms, rotate it in three-space, and plot the projection of the resulting figure onto the x-y plane. Those lines or portions of lines that should be hidden by previous lines are masked. Each call to PLOT3D causes one line to be plotted. A line consists of a sequence of points in three-space that will be connected using linear interpolation between adjacent points. This sequence of points is specified by three sequences of real numbers, the x, y, and z components of each point. Each of these sequences of real numbers can be specified either as being equally spaced, and therefore denoted by an initial value and an increment, or as being contained in a real array. PLOT3D attempts to minimize plotter movement by beginning at the alternate end of successive lines. A more detailed description of the parameters is contained in the comments at the beginning of the program listing. This routine was developed at the Applied Research Laboratories on their Control Data Corp. 3200 computer system.

Detailed performance evaluations are presented for six ACM algorithms : quicksort (No. 64), Shellsort (No. 201), stringsort (No. 207), "TREESORTS" (No. 245), quickersort (No. 271), and qsort (No. 402). algorithms 271 and 402 are refinements of algorithm 64, and all three are discussed in some detail. The evidence given here demonstrates that its author claims. Of all these algorithms, quickersort requires the fewest comparison to sort random arrays. [ABSTRACT FROM AUTHOR]

The article presents information about visible surface plotting program in computer graphics. This package of three routines produces a perspective picture of an arbitrary object or group of objects with the hidden parts not drawn. The objects are assumed to be stored in the format described in the article, a format which was chosen to facilitate the display of functions of three variables or output from three-dimensional computer simulations. The algorithm leaves out the hidden parts of the contours by suppressing lines enclosed within lines produced while processing preceding cuts. There are three subroutines in the package. Although this package was developed using National Center for Atmospheric Research's CDC machines with locally written systems and compilers, implementation on different machines or systems should not be too difficult regardless of the plotter. The algorithm has been tested on the Minnesota Fortran compiler.

The article discusses an algorithmic method of bivariate interpolation and smooth surface fitting based on local procedures. The method interpolates values of a single-valued smooth bivariate function and fits a smooth surface to a set of values of the function given at grid points in an x-y plane. It is an extension of the method of univariate interpolation designed to avoid excessive undulations between grid points. The method is based on a piecewise function composed of a set of bicubic polynomials, each of which is applicable to a rectangle in the x-y plane.

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.

The article discusses a study on the two subroutines of user information and Fortran listings namely INTRPL and CRVFIT, which implement the method of interpolation and smooth curve fitting based on local procedures. This method of interpolation is designed in such a way that the resulting curve will pass through all the given data points and appear smooth and natural. The INTRPL subroutine interpolates the values of a single-valued function y = y(x). The CRVFIT subroutine interpolates points in each interval between a pair of data points and generates a set of output points consisting of the input data points and the interpolated points.

The article presents certification of algorithm. The error function for complex in the algorithm was calculated using Salzer's formula. This formula requires the computation of error function, which was done with the help of a library program based on approximation by Cody. Algorithm 370 was translated into Algol and run on an ICL 1907 computer. Test revealed that, in several instances, the subroutine RANDGI generated incorrect values for the vector.

The article presents information on linear equations using residue arithmetic. The subroutine EXACT solves the matrix equation AX = B for X, where A is an N by N integer matrix, B is an N by M integer matrix, and X is an N by M real matrix. Residue arithmetic is used to obtain the exact solution, consisting of the rational components of X, i.e. det(A) and the rounded solution, computed as the quotient of the rational components and stored in the array X. The subroutine can be used to solve systems of linear algebraic equations, to invert matrices, and to compute determinants and adjoint matrices. In the concept of residue modulo m refers to the least non-negative remainder of the integer x after division by m. The computation is performed by means of Gaussian elimination for residue arithmetic using the residue system. Subroutine EXACT was tested on a CDC 6600 computer on which the maximum size of integer variables which can be used in arithmetic operations is 48 bits. The maximum size of real variables is 48 bits with an 11-bit exponent.

The article presents various mathematical analysis regarding algorithms. Algorithm 401 procedure generates complex prime numbers while Algorithm 402 procedure sorts mathematical elements into nondescending order. Algorithm 343 contains certain failures during its application to pathological matrices which include incorrect computed eigenvalues resulting to 2 or more percent maximum error. Remarks about Algorithm 372 and 401 are also discussed. Diagrams of the algorithm procedures are also presented.

This section provides summaries of papers on algorithms. The paper "Function Minimization and Linear Search," by K. Fielding discusses a procedure that minimizes a function using the method of Broyden. The parameters of the procedure include iterations, maxiters, and tolerance. In his paper "Binary Ordered Walsh Functions," H. Hübner explains the procedure binwal which computes the binary ordered Walsh function. The paper "Simpson's Rule for Multiple Integration" states that an algorithm can be marginally improved by replacing each integer constant to its equivalent decimal number.

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.

This article focuses on various abstracts and keywords related to algorithms.

This article presents algorithmic solutions to several mathematical problems. One of the problems is based on the numerical inversion of the laplace transforms. Another problem is based on the generator of random numbers satisfying the poisson distribution. Further, an algorithm is presented which generates random numbers from any probability density function, whether it be analytical, hypothetical, or experimentally acquired. Although there are in existence some fast and some general routines, the fast ones are for specific densities whereas the general algorithms are slow.

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 article presents information on the Clenshaw-Curtis quadrature [D-1]. Clenshaw-Curtis quadrature is one of the most effective automatic quadrature schemes available, particularly for integrands with some continuous derivatives. It can also be used for any piecewise continuous integrand, although it is not recommended for integrands with discontinuities. The automatic scheme consists of evaluating the N + 1 point Clenshaw-Curtis quadrature formula, together with some error estimate, for a sequence of Ns until the estimated absolute error ESTERR is less than the product of the tolerated relative error TOLERR and the absolute value of the current estimate of the integral, or until the permitted number of function evaluations would be exceeded. Earlier implementations of this quadrature scheme computed the cosine transform by a recursive method which was slow and suffered from rounding error, but CCQUAD uses a variant of the fast Fourier transform and is very fast and very resistant to rounding errors.

The article presents the algorithm of a FORTRAN program, CPOLY, to find all the zeros of a complex polynomial by the three stage complex algorithm. The program finds the zeros one at a time in roughly increasing order of modulus and deflates the polynomial to one of lower degree. The program is extremely fast and the timing is quite insensitive to the distribution of zeros. Extensive testing of an Algol version of the program has shown the program to be very reliable. The program is written in a portable subset of ANSI Fortran. It has been successfully used on the IBM 360.65, the GE 635 and the CDC 6600. The program is a translation of the Algol 60 procedure cpolzerofinder. MCON, the final subroutine of the program, sets four variables which describe the precision and range of the floating point arithmetic being used. The algorithm will accept polynomials of maximal degree 49.

The article presents information about a method for computing Fourier integrals by using algorithm 418. The most commonly used formula for calculating Fourier integrals is Filon's formula. The formula is based on the approximation of the function by a quadratic equation in each double interval. In order to obtain a better approximation, the cube spline fit is used. The obtained formulas do not need the explicit calculation of the spline fit. However, in addition to the function values, at all intermediate points, the values of the first and second derivatives at the boundary points are required. However, these values are often obtained from symmetry conditions. If the derivatives at the end points are unknown, they may be calculated from a cubic spline fit, for example by using some exterior points or by using two extra interior conditions for the spline fit. It can also be noted that in certain periodic cases the terms containing the derivatives will cancel and their vales will be superfluous.

The article discusses three computer algorithms. The first algorithm is related to circular integer partitioning. The partition, when expresses as a K-tuple may be thought of as a K-digit number in the base V number system. However, since all K-digit numbers do not correspond to circular partitions, it is possible to have the procedure generate only a set of K-tuplets for consideration. Since the numbers are sequentially increasing, a given number is a cyclic permutation of a previously generated number if a cyclic rotation of its digits produces a number with a smaller value. Therefore, the procedure efficiently generates the totality of circular partitions since it can greatly restrict the number of K-tuples that must be considered. The second algorithm is related to complex gamma functions. It evaluates in single precision the gamma function for complex arguments. First the real part of the argument of the gamma function is increased by some integer so that Stirling's asymptotic series for the logarithm of the gamma function may be used with high precisions and a small number of terms.

The article presents an algorithm of Student's t-statistic distribution function. The procedure provides results accurate to 11 decimal places and 8 significant digits for integer values of "n," with approximate continuation of the function through non-integer values of n. The procedure normal (x) returns the area under the standard normal frequency curve to the left of x, so that a negative argument yields the lower-tail area. The user-supplied procedure, error (n), should produce a diagnostic warning and may go to a label, terminate, or return a distinctive value (zero or -1.0) as a signal of error to the calling program. Student's series expansion of the probability integral is supplemented by a faster asymptotic approximation for large values of n and by a more precise "tail" series expansion for large values of t.

The article presents information on a multidimensional Monte Carlo quadrature with adaptive stratified sampling. This procedure evaluates the n-dimensional integral by the Monte Carlo method. In the procedure, a set of samples is taken uniformly stratified throughout the entire volume. Based on the variance in these samples, a decision is made as to whether more samples are needed. If more samples are needed, the volume is cut in half and the entire procedure is repeated on each half, the halvings being repeated as required. The choice for axis for the halving is based on samples of the gradient. The result of this process is that the overall stratification is not uniform, but approaches optimum as more and more samples are taken, since more halvings are taken in the regions of high variance.

The article focuses on the computer algorithm 434, related to exact probabilities for contingency tables. The researchers derive a general method for computing exact probabilities for contingency tables that result if a sample is subjected to k different and independent classifications. The algorithm is limited to the case where k is equal to 2. The algorithm was tested on a CDC 6400 (60 bit word). Results for the tables of order 2 by 3, were verified against values separately computed.

The article comments on algorithms that offer symbolic expansion of algebraic expressions and prime number generator. The first algorithm expands arbitrarily parenthesized expressions into monomials and has direct distribution without intermediate expansion of lower level expressions. It has also been used as part of algebra programs in theoretical physics. The second algorithm has the intention of giving only the number of primes less than or equal to m. The algorithm has been tested for a large range of values including m =5, 10, 501 and 2000.

The article presents a computation of the Legendre series coefficients. The formula for the truncated Chebyshev series is described. It is based on the orthogonal propert of summation of the Chebyshev polynomials. There is a comparison between the exact Legendre series coefficients of the function and the computed values.

The article focuses on algorithm 415 used for an assignment problem in rectangular matrices. The algorithm related differential equation has been given. This procedure is based on that of researcher R. Silver, which uses the assignment algorithm of researcher J. Munkres.

The article presents several examples of the generalized eigenvalues problem and how the Pencil procedure processed these examples for input into user-supplied eigenvalue routine. It presents examples with matrix roots, pencil roots and computer algorithms.