January 1973 - Vol. 16 No. 1
Features
A queuing model of a multiprogrammed computer with a two-level storage system
The results are presented of an analysis of a probabilistic model of a multiprogrammed computer system with a two-level storage system in which there is sequential dependency of accesses between the devices. Expressions are obtained for the long-run probability that both the CPU and each of the storage devices are busy. Some numerical results are given which quantify the gains in CPU utilization obtainable by multiprogramming in the presence of this type of storage system.
The reallocation of hash-coded tables
When the space allocation for a hash-coded table is altered, the table entries must be rescattered over the new space. A technique for accomplishing this rescattering is presented. The technique is independent of both the length of the table and the hashing function used, and can be utilized in conjunction with a linear reallocation of the table being rescattered. Moreover, it can be used to eliminate previously flagged deletions from any hash-coded table, or to change from one hashing method to another. The efficiency of the technique is discussed and theoretical statistics are given.
Adaptive correction of program statements
A method of analyzing statements in a programming language which can tolerate a considerable inaccuracy in their specification is proposed. This method involves principles at present mainly confined to studies in the area of artificial intelligence such as feature extraction, approximate tree matching, and strategy improvement by feedback from the matching process. A pilot program incorporating the principles is described and preliminary operating results are presented. A final section surveys further principles which are currently being investigated.
Variable-precision exponentiation
A previous paper presented an efficient algorithm, called the Recomputation Algorithm, for evaluating a rational expression to within any desired tolerance on a computer which performs variable-precision arithmetic operations. The Recomputation Algorithm can be applied to expressions involving any variable-precision operations having O(10-p + ∑ | &egr;i |) error bounds, where p denotes the operation's precision and &egr;i denotes the error in the operation's ith argument.
This paper presents an efficient variable-precision exponential operation with an error bound of the above order. Other operations, such as log, sin, and cos, which have simple series expansions, can be handled similarly.
Reduction of a band-symmetric generalized eigenvalue problem
An algorithm is described for reducing the generalized eigenvalue problem Ax = &lgr;Bx to an ordinary problem, in case A and B are symmetric band matrices with B positive definite. If n is the order of the matrix and m the bandwidth, the matrices A and B are partitioned into m-by-m blocks; and the algorithm is described in terms of these blocks. The algorithm reduces the generalized problem to an ordinary eigenvalue problem for a symmetric band matrix C whose bandwidth is the same as A and B. The algorithm is similar to those of Rutishauser and Schwartz for the reduction of symmetric matrices to band form. The calculation of C requires order n2m operation. The round-off error in the calculation of C is of the same order as the sum of the errors at each of the n/m steps of the algorithm, the latter errors being largely determined by the condition of B with respect to inversion.
A note on when to chain overflow items within a direct-access table
This note supplements the paper by V.Y. Lum [2] and elaborates on Table II in McIlroy [3].
Mutual recursion in Algol 60 using restricted compilers
The Elliott (I.C.L.) Algol 60 compiler contains a restriction on the sequence of declarations such that no identifier may be used before it is declared. This means that direct mutual recursion between procedures declared in the same blockhead is not possible.
