March 1964 - Vol. 7 No. 3
Features
A note on some compiling algorithms
Two compiling generators for arithmetic expressions are discussed: one presently in use in an experimental compiler, and an improvement suggested by K. Speierman of Burroughs.
Comments on “a continued operation notation”
This note is intended to clarify and correct several points in a recent paper describing some notations for symbol manipulation by M. P. Barnett [Comm. ACM 6(August, 1963)].
report on CCITT data communications study group meeting
Data communications was the subject of a two-week meeting held 24 September through 4 October 1963, in Geneva, Switzerland, by the International Telegraph and Telephone Consultative Committee (CCITT) Special Study Group A. Previous meetings of this group had been held in Geneva in April, 1960, and October, 1961. The CCITT has traditionally been responsible for all standardization activities involving the public telecommunications network of the world. Among the 150 participants, there were eleven USA representatives who represented the Government, various business machine companies and the common carriers.
FORTRAN subroutines for time series data reduction
For several years the author has been concerned with time series data reduction of guided missile data derived from tracking, telemetry and static test instrumentation. The data, which is acquired from many sources and comes in a great variety of formats and coding systems, must commonly be manipulated in a number of general ways before the calculation of functions specific to guided missile analysis is possible. The costs of programming many special purpose data reduction programs and the development time consumed in preparing and checking out these programs have strongly indicated the need for independent, general-purpose computer program modules or subroutines for data reduction. The philosophy arrived at by the author, is almost identical with that described in a recent publication by Healy and Bogert, and in a note by Bennet, but these individual module specifications are concerned with continuous functions, whereas the referenced article deals with spectral analysis.
Polyphase sorting with overlapped rewind
A variation of the polyphase merge technique of sorting is described which permits one tape at a time to be rewound while the merge is continued on the remaining tapes. The result is the overlapping of a major portion of the rewind time.
The technique should be considered whenever a sort is written to operate on five or more tapes that cannot be read backwards. The savings of the overlap method appear to increase as the number of available tapes is increased.
Tests on a computer method for constructing school timetables
A previously proposed computer method for constructing timetables, based on an iteration involving Boolean matrices, is described. In limited tests the method has successfully produced timetables on every trial. References are given which relate the timetable problem to theorems on matrices of zeros and ones, and to theorems on bipartite graphs. Some problems of applying the method to constructing timetables in real situations are noted.
Randomized binary searching with tree structures
A more efficient method of using tree structures is proposed, which utilizes both plus and minus branches in the search path. Very significant gains result when the search key includes alphabetic characters.
Generating a canonical prefix encoding
Computer programs for generating a minimum-redundancy exhaustive prefix encoding are described. One program generates a Huffman frequency tree, another determines the structure functions of an encoding, and a third program assigns codes.
Computer-made perspective movies as a scientific and communication tool
It is easy to program the basic transformation required for a perspective drawing. This fact plus the advent of high speed microfilm printers such as the General Dynamics Electronics S-C 4020 makes possible perspective movies as the direct output from a computer. The programming of such a movie is briefly described for studying the angular motions of a satellite containing an attitude control system. In the movie, a domino-shaped box represents the satellite and a sphere with circles of latitude and longitude represents the earth. The cost was approximately three to eight minutes of IBM 7090 time per one minute of movie.
A technique for computer detection and correction of spelling errors
The method described assumes that a word which cannot be found in a dictionary has at most one error, which might be a wrong, missing or extra letter or a single transposition. The unidentified input word is compared to the dictionary again, testing each time to see if the words match—assuming one of these errors occurred. During a test run on garbled text, correct identifications were made for over 95 percent of these error types.
A class of iterative techniques for the factorization of polynomials
A method of iteration is developed in terms of a function of somewhat arbitrary character. Sufficient conditions are given for convergence of the process, yielding factors of arbitrary degree for polynomials in one variable. Both Lin's method and Newton's method occur as special cases.
A Fourier series method is described which, when applied to a certain class of parabolic partial differential equations, reduces the problem to a system of ordinary differential equations. An application is given for which the method shows a considerable advantage over conventional finite difference methods.
Conversion of a power to a series of Chebyshev polynomials
Even slowly convergent power series can be rearranged as series in Chebyshev polynomials if appropriate sequence transformations are used in evaluating the coefficients. The method is illustrated by computing the coefficients for the expansion of the logarithm and dilogarithm.
Digital data processor for tracking the partially illuminated moon
A study of lunar tracking techniques and fabrication of a breadboard to assess the feasibility of the best technique selected was conducted to define a tracking system for observation of the sightline to the center of a partially illuminated moon. The data processing portion of the system is presented in detail and then described in general are the operation of the tracker head assembly for data readout, the operation of the entire system and the effect data processing considerations have on the design of the tracker system.
The system basically consists of an optical sensor, digital computer and tracker drive mechanism. The three system units, connected in cascade, comprise the control loop. For this application, an optical telescope with a radial mechanical scanning mechanism was used that read out lunar sightline measurement information. This information is sequentially read into a special purpose digital computer that extracts the measurements and computes the error signals that drive the tracker to the appropriate attitude.
