November 1971 - Vol. 14 No. 11
Features
On ACM special interest groups and committees
This report has been written to explain the nature, purposes, and organization of the Special Interest Groups (SIGS) and Special Interest Committees (SICS) of ACM, and to summarize SIG/SIC activity during the period August 1, 1970, to August 1, 1971.
The composition of semantics in Algol 68
The main features of Algol 68 are explained from a semantic point of view. It is shown how the language permits the composition of values and actions, i.e. ultimately programs, from a minimum set of primitives with a few fundamental recursive rules of composition. The associated syntax is briefly reviewed. An attempt has been made to obtain a structured and simple introduction to both Algol 68 and its orthogonal desgn.
Using computers in higher education: past recommendations, status, and needs
Data from a survey conducted with National Science Foundation support, which was published in December 1970, is reviewed, and it is pointed out that, with regard to computers in higher education, national goals stated in the Rosser and Pierce Reports have not been attained. Quality was lacking in hardware or courses in nearly half of the associate and bachelor's degree programs in data processing, computer science, etc., offered in 1966-67. A plea is made for continuing studies on status and goals for computing in higher education, improvement of degree programs, and a national testing laboratory for educational technology.
Various dispersion algorithms for the polyphase sorting procedure are examined. The optimum algorithm based on minimizing the total number of unit strings read is displayed. The logic of this algorithm is rather complicated; hence, several other new dispersion algorithms with more straightforward logic are presented. Of the simple dispersion algorithms discussed, the Horizontal is best. It does approximately one-fourth to one and one-half percent less reading and writing than most algorithms in use today. An additional two and one-fourth to three percent improvement can be achieved by utilizing the Modified Optimum Algorithm. This algorithm is relatively straightforward, but it requires a fairly close estimate of the total number of unit strings before the dispersion begins.
Automation of etching-pattern layout
HELP (Heuristic Etching-Pattern Layout Program) is an application program developed to computerize the tedious and error-prone although vitally important wiring design of printed circuit boards. HELP helps automate a design stage one step closer to production than logical design. It can be used to design wiring patterns of two-layer circuit boards on which ICs in dual-in-line packages as well as discrete components such as transistors and resistors have been placed.
HELP employs two methods of wiring. One is the heuristic method, which simulates human approaches to wiring design, and the other is the theoretically interesting but time-consuming method of maze-running, based on the Lee's algorithm.
HELP performs more than 90 percent of required wiring by the heuristic method. The maze-running method finds an optimal path with respect to a performance function for each point-to-point, and point-to-line connection. It can bring the number of successful wiring connections very close to 100 percent.
On accurate floating-point summation
cumulation of floating-point sums is considered on a computer which performs t-digit base &bgr; floating-point addition with exponents in the range —m to M. An algorithm is given for accurately summing n t-digit floating-point numbers. Each of these n numbers is split into q parts, forming q·n t-digit floating-point numbers. Each of these is then added to the appropriate one of &eegr; auxiliary t-digit accumulators. Finally, the accumulators are added together to yield the computed sum. In all, q·n + &eegr; - 1 t-digit floating-point additions are performed. Let &ngr; = ⌈(M + m + 1)/(&eegr; + 1)⌉. If n ≤ (1/q)&bgr;⌈((q-1)/q)t⌈-&ngr;+1 (*), then the relative error in the computed sum is at most ⌈(t + 1)/&ngr;⌉&bgr;1-t. Further, with an additional q + &eegr; - 1 t-digit additions, the computed sum can be corrected to full t-digit accuracy.
For example, for the IBM/360 (&bgr; = 16, t = 14, M = 63, m = 64), typical values for q and &eegr; are q = 2 and &eegr; = 32. In this case, (*) becomes n ≤ 1/2 × 164 = 32,768, and we have ⌈(t + 1)/&ngr;⌉&bgr;1-t = 4 × 16-13.
Algorithm 414: Chebyshev approximation of continuous functions by a Chebyshev system of functions
The second algorithm of Remez can be used to compute the minimax approximation to a function, ƒ(x), by a linear combination of functions, {Qi(x)}n0, which form a Chebyshev system. The only restriction on the function to be approximated is that it be continuous on a finite interval [a,b]. An Algol 60 procedure is given, which will accomplish the approximation. This implementation of the second algorithm of Remez is quite general in that the continuity of ƒ(x) is all that is required whereas previous implementations have required differentiability, that the end points of the interval be “critical points,” and that the number of “critical points” be exactly n + 2. Discussion of the method used and of its numerical properties is given as well as some computational examples of the use of the algorithm. The use of orthogonal polynomials (which change at each iteration) as the Chebyshev system is also discussed.
