bluuebunny/crossref_metadata_2025 huggingface dataset:
An architecture for packet-striping protocols
Authors: Hari Adiseshu , Varghese George , Parulkar Guru
Published: July 2002

Link-striping algorithms are often used to overcome transmission bottlenecks in computer networks. Traditional striping algorithms suffer from two major disadvantages. They provide inadequate load sharing in the presence of variable-length packets, and may result in non-FIFO delivery of data. We describe a new family of link-striping algorithms that solves both problems. Our scheme applies to any layer that can provide multiple FIFO channels. We deal with variable-sized packets by showing how fair-queuing algorithms can be transformed into load-sharing algorithms. Our transformation results in practical load-sharing protocols, and shows a theoretical connection between two seemingly different problems. The same transformation can be applied to obtain load-sharing protocols for links with different capacities. We deal with the FIFO requirement for two separate cases. If a sequence number can be added to each packet, we show how to speed up packet processing by letting the receiver simulate the sender algorithm. If no header can be added, we show how to provide quasi FIFO delivery. Quasi FIFO is FIFO except during occasional periods of loss of synchronization. We argue that quasi FIFO is adequate for most applications. We also describe a simple technique for speedy restoration of synchronization in the event of loss. We develop an architectural framework for transparently embedding our protocol at the network level by striping IP packets across multiple physical interfaces. The resulting stripe protocol has been implemented within the NetBSD kernel. Our measurements and simulations show that the protocol offers scalable throughput even when striping is done over dissimilar links, and that the protocol synchronized quickly after packet loss. Measurements show performance improvements over conventional round-robin striping schemes and striping schemes that do not resequence packets. Some aspects of our solution have been implemented in Cisco's router operating system (IOS 11.3) in the context of Multilink PPP striping.
Computational astrophysics
Authors: Arnett W. D.
Published: July 2002

As computers become more powerful and sophisticated, computational astrophysicists will be able to find out more about stellar evolution and other astronomical phenomena.
The expressibility of languages and relations by word equations
Authors: Karhumäki Juhani , Mignosi Filippo , Plandowski Wojciech
Published: July 2002

Classically, several properties and relations of words, such as “being a power of the same word” can be expressed by using word equations. This paper is devoted to a general study of the expressive power of word equations. As main results we prove theorems which allow us to show that certain properties of words are not expressible as components of solutions of word equations. In particular, “the primitiveness” and “the equal length” are such properties, as well as being “any word over a proper subalphabet”.
Allocation of FIFO structures in RTL data paths
Authors: Balakrishnan M. , Khanna Heman
Published: July 2002

Along with functional units, storage and interconnects contribute significantly to data path costs. This paper addresses the issue of reducing the costs of storage and interconnect. In a post-datapath synthesis phase, one or more queues can be allocated and variables bound to it, with the goal of reducing storage and interconnect costs. Further, in contrast to earlier work, we support “irregular” cdfgs and multicycle functional units for queue synthesis. Initial results on HLS benchmark examples have been encouraging, and show the potential of using queue synthesis to reduce datapath cost. A novel feature of our work is the formulation of the problem for a variety of FIFO structures with their own “queueing” criteria.
Stochastic sequential machine synthesis with application to constrained sequence generation
Authors: Marculescu Diana , Marculescu Radu , Pedram Massoud
Published: July 2002

In power estimation, one is faced with two problems: (1) generating input vector sequences that satisfy a given statistical behavior (in terms of signal probabilities and correlations among bits); (2) making these sequences as short as possible so as to improve the efficiency of power simulators. Stochastic sequential machines (SSMs) can be used to solve both problems. In particular, this paper presents a general procedure for SSM synthesis and describes a new framework for sequence characterization to match designers' needs for sequence generation or compaction. Experimental results demonstrate that compaction ratios of 1–3 orders of magnitude can be obtained without much loss in accuracy of total power estimates.
An application of queueing theory to the design of a message-switching computer system
Authors: Gostl Jack , Greenberg Irwin
Published: July 2002

Inexact or real-world queueing techniques are used to determine that the number of buffers provided in system design is indeed adequate to guard against message loss.
Key management for encrypted broadcast
Authors: Wool Avishai
Published: July 2002

We consider broadcast applications where the transmissions need to be encrypted, such as direct broadcast digital TV networks or Internet multicast. In these applications the number of encrypted TV programs may be very large, but the secure memory capacity at the set-top terminals (STT) is severely limited due to the need to withstand pirate attacks and hardware tampering. Despite this, we would like to allow the service provider to offer different packages of programs to the users. A user who buys a package should be able to view every program belonging to that package, but nothing else. A flexible scheme should allow for packages of various sizes to be offered, from a single program up to all the programs. We suggest two novel schemes to manage the encryption keys for these applications. The schemes are highly flexible, and understandable to users, yet require very few keys to be stored in the STTs' secure memory. The computational power required of the STTs is very low. The security of these schems is as good or better than that offered by current technology.
Algorithm 425: generation of random correlated normal variables [G5]
Authors: Hurst Rex L. , Knop Robert E.
Published: July 2002

We have programmed and made timing comparisons for two algorithms which sample the multivariate normal density
N
(
μ
,
V
) = |
V
-1
|/(2π)

n
/2

·
exp
(- 1/2(
Y
-
μ
)

T

V
-1
(
Y
-
μ
)) (1) where
V
is an
n
X
n
covariance matrix,
μ
is an
n
component vector of means, and
Y
is an
n
component random vector [1].
Derived semantics for some programming language constructs
Authors: Henderson Peter
Published: July 2002

The constructs of a simple programming language are introduced and described informally in terms of values and side-effects. A translator is defined which translates the language into flowcharts for a simple machine. The action of the machine in executing a flowchart is defined. A proof is constructed that the effect of translating and executing any program can be expressed solely in terms of the value and side-effect of the program. During the course of constructing the proof, formal definitions of the concepts of value and side-effect are derived in order to make the proof rigorous. Correctness of the implementation involves checking that the definitions derived in the step above are an acceptable formalization of the informal description given in the first step.
A theorem-proving language for experimentation
Authors: Henschen L. , Overbeck Ross , Wos L.
Published: July 2002

Because of the large number of strategies and inference rules presently under consideration in automated theorem proving, there is a need for developing a language especially oriented toward automated theorem proving. This paper discusses some of the features and instructions of this language. The use of this language permits easy extension of automated theorem-proving programs to include new strategies and/or new inference rules. Such extendability will permit general experimentation with the various alternative systems.
A weighted buddy method for dynamic storage allocation
Authors: Shen Kenneth K. , Peterson James L.
Published: July 2002

An extension of the buddy method, called the weighted buddy method, for dynamic storage allocation is presented. The weighted buddy method allows block sizes of 2

k

and 3·2

k

, whereas the original buddy method allowed only block sizes of 2

k

. This extension is achieved at an additional cost of only two bits per block.

Simulation results are presented which compare this method with the buddy method. These results indicate that, for a uniform request distribution, the buddy system has less total memory fragmentation than the weighted buddy algorithm. However, the total fragmentation is smaller for the weighted buddy method when the requests are for exponentially distributed block sizes.
Experience with a space efficient way to store a dictionary
Authors: Nix Robert
Published: July 2002

The paper, “Computer Programs for Detecting and Correcting Spelling Errors” by James L. Peterson [3], listed methods for checking and correcting spelling errors. One significant method, however, was not included: a probabilistic technique suggested by Carter, Floyd, Gill, Markovsky, and Wegman [1]. The present note discusses aspects of these practical space efficient algorithms for testing set membership—a simple abstraction of looking a word up in a dictionary. An implementation of one of these algorithms uses only 20 percent of the space used by the Stanford SPELL program described by Peterson.
Polynomial manipulation with APL
Authors: Billard Brian
Published: July 2002

A simple but effective method for the manipulation of polynomials of several variables in APL is presented. The method is especially advantageous in situations where more sophisticated symbolic computing systems such as SAC-1 and MACSYMA are not available. The method is shown to successfully solve a problem not readily resolved by other means.
A hash code method for detecting and correcting spelling errors
Authors: Mor M. , Fraenkel A. S.
Published: July 2002

The most common spelling errors are one extra letter, one missing letter, one wrong letter, or the transposition of two letters. Deletion, exchange, and rotation operators are defined which detect and “mend” such spelling errors and thus permit retrieval despite the errors. These three operators essentially delete a letter of a word, exchange two adjacent letters, and rotate a word cyclically. Moreover, the operators can be used in conjunction with hashing, thus permitting very fast retrieval. Results of experiments run on large databases in Hebrew and in English are briefly indicated.
The structure of modular program
Authors: Turner Joshua
Published: July 2002

Choosing the right program structures can lead to better programs, says Joshua Turner. He advocates modular design to make large programs more manageable. Turner reviews the possible structural relationships between the modules of a program and generates a tentative morphology of program structure types. He concludes that, with some exceptions, the hypothetical pure tree structure is the best choice for most data processing applications.
Optimal storage allocation for serial files
Authors: Mendelson Haim , Pliskin Joseph S. , Yechiali Uri
Published: July 2002

A computer system uses several serial files. The files reside on a direct-access storage device in which storage space is limited. Records are added to the files either by jobs in batch processing mode, or by on-line transactions. Each transaction (or job) generates a demand vector which designates the space required in each file for record addition. Whenever one file runs out of space, the system must be reorganized. This paper considers several criteria for best allocating storage space to the files.
A record and file partitioning model
Authors: Babad Jair M.
Published: July 2002

One of the main objectives in the design of a file system is the reduction of storage and data transfer costs. This paper presents a model in which several requests access the file system, and each request requires information from one or more variable length data-items. The probabilities of access and the distribution of each data-item's length are assumed to be known, and to be mutually independent. The file system uses one or more storage devices, and each record may be partitioned into subrecords that are stored on different devices. One of the subrecords is designated as the primary record; when a request for a record is made, the primary record is first accessed, and other sub-records are accessed only if the pertinent information is not stored in the primary record. The model that is presented in this paper, both as a nonlinear programming model and a mixed integer programming model, is a very general one; several types of file systems may be derived from it by an appropriate selection of its parameters. This model has already been used in the optimization of library routines' storage at a large scale operating system.
Occurrences of cycling and other phenomena arising in a class of linear programming models
Authors: Kotiah Thoddi C. T. , Steinberg David I.
Published: July 2002

An investigation into the average queue size for a certain class of queues has resulted in the formulation of linear programming problems which are ill-conditioned in some cases. In attempting to solve these linear programming models, using IBM's MPS package, instances of cycling were encountered. Small perturbations in the input data resulted in problems which did not cycle. This fact, plus several other observed phenomena suggest that the primary reason that cycling is not known to occur more frequently is that round-off errors in the computations perturb the problem sufficiently to prevent cycling (or at least to prevent indefinite cycling). In one case maximizing and minimizing an objective function subject to the same constraint set was attempted, but MPS solved only one of these while giving an indication of infeasibility for the other.
Computer generation of gamma random variables—II
Authors: Tadikamalla Pandu R.
Published: July 2002

A rejection method is proposed for generating gamma variates with nonintegral shape parameter
α
,
α
> 1. This method is similar to other methods given by Fishman, Wallace, and Tadikamalla and is faster than these methods for
α
> 2. The core storage requirements and the programming effort for the proposed method are similar to those of Wallace's or Tadikamalla's methods. The computational times for the proposed method remain fairly constant for medium and large values of
α
and are superior to times obtained by Arhens and Dieter's method for all values of
α
. The proposed method is simpler than Ahrens and Dieter's method.
Power trees
Authors: Luccio Fabrizio , Pagli Linda
Published: July 2002

The new class of Pk trees is presented, where height balance is maintained for the nodes lying on particular paths. The number of nodes of a Pk tree asympotically grows as a power of the height, in the worst case. A procedure for node insertion is given, and the class of trees considered is restricted to IPk trees, which are buildable by such a procedure. The average behavior of such trees, studied by an extensive set of simulation runs, is close to that of AVL trees. In particular, the family of IP0 trees whose main advantage is the reduced number of restructurings required after node insertion, is analyzed.
Anomalous behavior of the fifty-percent rule in dynamic memory allocation
Authors: Shore John E.
Published: July 2002

This paper reports simulation data showing that, in dynamic memory allocation, the average free-to-allocated-block ratio can differ considerably and in both directions from the predictions of the 50 percent rule. A new derivation is given, and it is shown that previous derivations make an assumption that may be violated frequently. On the basis of the simulation data and the derivation, it is hypothesized that the anomalous behavior results from the combined effects of systematic placement and the statistics of the release process. Additional simulations support this hypothesis. Systematic placement, which refers to the natural convention of always allocating storage requests against the same end of the free block selected by the allocation strategy, tends to order blocks within contiguous groups according to their allocation time. The degree of anomalous behavior depends on the extent to which allocated blocks are released in the order of their allocation. For non-Markovian release processes, the extent of the correlation between allocation order and release order varies approximately inversely with the coefficient of variation of the memory residence time distribution. The simulations show that allocation efficiency depends strongly on the residence time distribution; efficiency decreases as the distribution's coefficient of variation increases. Some practical implications are briefly discussed.
A counterintuitive example of computer paging
Authors: Fagin Ronald
Published: July 2002

A counterexample is exhibited to a natural conjecture concerning the optimal way to group records into pages in the independent reference model of computer paging (an organization is said to be optimal if the “least recently used” miss ratio is minimized).
Homilies for humble standards
Authors: Ross Douglas T.
Published: July 2002

At every standards meeting, in clear view on the table there should be a small plaque engraved: “Do it once, do it right, do it internationally.” The many contributions of Douglas Ross exemplify this directive. If, for example, you look at the ASCII standard, ANSI-X3.4-1968, you will find that D.T. Ross represented ACM on the ANSI X3 Committee at that time. This paper is part of an argument that well-founded standards go hand in hand with an effective systems methodology.

When first submitted for refereeing, “Homilies for Humble Standards” was oriented toward Computer Aided Manufacturing (CAM) applications. As it is now published, the context is elevated to consider all applications. In a similar manner, we can broaden the scope to show that it is the concern of all ACM members. Manufacturing is the application of tools and processes on materials to create a product. Languages are our tools; algorithms and procedures are our processes; data is our material. The product is an enhancement of the power and span of control of the customer.

I commend this paper for your reading as one of the relatively few in ACM publications which tell why ACM and its members should be “involved”; it discusses an unsolved problem, rather than a solution looking for a problem.
Positivity and norms
Authors: Bauer F. L.
Published: July 2002

Following some lines of joint work with A.S. Householder, the character and use of algebraic methods in the theory of norms is demonstrated. New results concerning norms with values in an Archimedian vector lattice (not necessarily being totally ordered) are given, in particular for the generalization of order unit norms, L-norms and M-norms. An example of application to operator norms is given concerning contraction properties of positive operators.
The quadratic hash method when the table size is not a prime number
Authors: Batagelj Vladimir
Published: July 2002

Previous work on quadratic hash methods is limited mainly to the case where the table size is a prime number. Here, certain results are derived for composite numbers. It is shown that all composite numbers containing at least the square of one of the component primes have full-period integer-coefficient quadratic hash functions.
Dynamic memory repacking
Authors: Balkovich E. , Chiu W. , Presser L. , Wood R.
Published: July 2002

A probabilistic model of a multiprogramming system is exercised in order to determine the conditions under which the dynamic repacking of main memory is beneficial. An expression is derived for the maximum interference that a repacking process may introduce before the original performance of the system is degraded. Alternative approaches to repacking are discussed, and the operating conditions that lead to improved system throughput through repacking are delineated.
Execution characteristics of programs in a page-on-demand system
Authors: Boyse John W.
Published: July 2002

h show the execution characteristics of two types of commonly used programs in a large-scale, time-shared computer system. A software monitoring facility built into the supervisor was used for data collection during normal system operation. These data were analyzed, and results of this analysis are presented for a Fortran compiler and an interactive line file editor.

Probability distribution functions and other data are given for such things as CPU intervals, I/O intervals, and the number of such intervals during execution. Empirical distributions are compared with simple theoretical distributions (exponential, hyperexponential, and geometric). Other data show paging characteristics of tasks as a function of the number of pages those tasks have in core.
Parallelism in tape-sorting
Authors: Even Shimon
Published: July 2002

Two methods for employing parallelism in tape-sorting are presented. Method A is the natural way to use parallelism. Method B is new. Both approximately achieve the goal of reducing the processing time by a divisor which is the number of processors.
The implementation of temporal intervals in qualitative simulation graphs
Authors: Ingalls Ricki G. , Morrice Douglas J. , Whinston Andrew B.
Published: July 2002

In this paper we develop and implement a simulation modeling methodology that combines discrete event simulation with qualitive simulation. Our main reason for doing so is to extend the application of discrete event simulation to systems found in business for which precise quantitative information is lacking. The approach discussed in this paper is the implementation of temporal interval specifications in the discrete event model and the construction of a temporal interval clock for the qualitative simulation model.
Execution time requirements for encipherment programs
Authors: Friedman Theodore D. , Hoffman Lance J.
Published: July 2002

Although encipherment has often been discussed as a means to protect computer data, its costs are not well established. Five experiments were conducted to measure the cpu time on a CDC 6400 required by additive ciphers programmed both in assembly language and in Fortran: a “null transformation” to measure the time to move data without encipherment; encipherment with a one-word key; encipherment with a 125-word key; double key encipherment; and encipherment using a pseudo random key. The results were analyzed for consistency over 100 runs, and the effects of constant and intermittent errors were considered.

Timing rates for assembly language encipherment ranged from 498,800 characters per second for a pseudo random key cipher to 2,092,000 characters per second for a constant one-word key cipher. The latter is almost equivalent to the rate required simply to move data without encipherment. Fortran tests required over four times as much cpu time. This paper introduces the idea of
enciphering time coefficient
the ratio of enciphering time to the time taken to fetch and store data without encipherment.
On the conversion of programs to decision tables
Authors: Cavouras John C.
Published: July 2002

The problems of converting programs to decision tables are investigated. Objectives of these conversions are mainly program debugging and optimization in practice. Extensions to the theory of computation and computability are suggested.
On the present and future of scientific computation
Authors: Rice John R.
Published: July 2002

A pessimistic forecast is given of what can be expected to happen in the application of computers to the physical sciences.
A new approach to automatic scanning of contour maps
Authors: Mor M. , Lamdan T.
Published: July 2002

The problem of automatic digitizing of contour maps is discussed. The structure of a general contour map is analyzed, and its topological properties are utilized in developing a new scanning algorithm. The problem of detection and recognition of contour lines is solved by a two color labeling method. It is shown that for maps containing normal contour lines only, it suffices to distinguish between so-called “even” and “odd” lines. The “tangency problem” involved in practical scanning is discussed, and a solution based on minimizing computer memory space and simplifying control program is suggested.
Dynamic partitioning for array languages
Authors: Phillips J. Richard , Adams H. C.
Published: July 2002

The classical process of partitioning an array into subarrays is extended to a more useful array language operation. Various modes of partitioning are defined for different types of arrays, so that subarrays may vary over the original array in a nearly arbitrary manner. These definitions are motivated with several realistic examples to illustrate the value of partitioning for array languages.

Of general interest is the data structure for partitioning. This consists of dynamic tree structures which are used to derive and maintain the array control information. These are described in sufficient detail to be of value in the design of other array languages. The description presented in this paper is implemented in a new array language, OL/2, currently under development at the University of Illinois.
Gray code and the ± sign sequence when ±
f(±f(±f(•••±f(x)•••)))
is ordered
Authors: Salzer Herbert E.
Published: July 2002

A previous note gives a rule for determining the sequence of + and - signs to obtain the
i
th largest value of +ƒ(±ƒ(±ƒ(··· ±ƒ(
x
)···))) when ƒ(
x
) is positive and monotonic [1, p. 46, §2]. Shortly after publication the writer received a letter dated March 9, 1972, from John Murchland, of the Planning & Transport Research & Computation Co. Ltd., London, in which he mentioned that the conversion scheme for obtaining the ± sign sequence from
i
- 1 happens to be also the standard way of going from a binary number to its Gray code equivalent, when after the conversion every plus sign is replaced by 0 and every minus sign by 1.
A region coloring technique for scene analysis
Authors: Strong James P. , Rosenfeld Azriel
Published: July 2002

A method of converting a picture into a “cartoon” or “map” whose regions correspond to differently textured regions is described. Texture edges in the picture are detected, and solid regions surrounded by these (usually broken) edges are “colored in” using a propagation process. The resulting map is cleaned by comparing the region colors with the textures of the corresponding regions in the picture, and also by merging some regions with others according to criteria based on topology and size. The method has been applied to the construction of cloud cover maps from cloud cover pictures obtained by satellites.
Remark on Algorithm 386 [A1]: Greatest Common Divisor of $n$ Integers and Multipliers
Authors: Ragland Larry C. , Good Donald I.
Published: July 2002

Subroutine
GCDN
, Algorithm 386 as described in [1, 2], computes the greatest common divisor,
IGCD
, of
n
integers
A
(1), … ,
A
(
n
) by using the Euclidean algorithm to compute first
gcd
(
A
(1),
A
(2)), then
gcd
(
gcd
(
A
(1),
A
(2)),
A
(3)), etc. It also computes integer multipliers
Z
(1), … ,
Z
(
n
) such that
IGCD
= ∑

n

i
=1

A
(
i
)
Z
(
i
).
Computer education in a graduate school of management
Authors: Ness D. N. , Green R. S. , Martin W. A.
Published: July 2002

Several years of experience have led to the belief that the creative design and evaluation of management information systems requires a thorough understanding of the related computer technology. Concepts such as paging and priority interrupt systems can best be explained at the machine language level. Any machine used for exposition should fulfill several criteria. It should: (1) raise as few spurious issues as possible; (2) allow, without undue effort, the solution of interesting problems; (3) be capable of exposing all outstanding issues of significance, within the chosen machine; (4) be useful for pursuing issues in great depth when appropriate; (5) not be committed to the equipment provided by any manufacturer; (6) be able to provide the student with diagnostic aids to a great depth; (7) allow the student ready access to the machine; (8) be capable of extension to expose new issues as they come along.

We have constructed a simulated machine and its associated software which meets these criteria. This system, called the PRISM system, is documented by a primer and a reference manual.
COKO III
Authors: Kozdrowicki Edward W. , Cooper Dennis W.
Published: July 2002

OKO III is a chess player written entirely in Fortran. On the IBM 360-65, COKO III plays a minimal chess game at the rate of .2 sec cpu time per move, with a level close to lower chess club play. A selective tree searching procedure controlled by tactical chess logistics allows a deployment of multiple minimal game calculations to achieve some optimal move selection. The tree searching algorithms are the heart of COKO's effectiveness, yet they are conceptually simple. In addition, an interesting phenomenon called a tree searching catastrophe has plagued COKO's entire development just as it troubles a human player. Standard exponential growth is curbed to a large extent by the definition and trimming of the Fisher set. A clear distinction between tree pruning and selective tree searching is also made. Representation of the chess environment is described along with a strategical preanalysis procedure that maps the Lasker regions. Specific chess algorithms are described which could be used as a command structure by anyone desiring to do some chess program experimentation. A comparison is made of some mysterious actions of human players and COKO III.
Sard kernels for certain bivariate cubatures
Authors: Barnhill Robert E. , Pilcher David T.
Published: July 2002

An error analysis for some bivariate cubatures is given. The remainders are obtained by the use of Sard kernels. Numerical results and computer graphs are given for some of the kernel functions.
Automated algebraic manipulation in celestial mechanics
Authors: Jefferys William H.
Published: July 2002

In this paper we consider some of the applications of automated algebraic manipulation which have been made in celestial mechanics. Particular attention is paid to the use of Poisson series, and a typical problem in perturbation theory is described. The requirements of processors for use in celestial mechanics are considered and compared with those for general manipulation packages. Some future directions for research using these systems are briefly outlined.

To illustrate the relative simplicity of the algorithms required in celestial mechanics, a typical integration problem is considered in an appendix.
Retrieval—Update speed tradeoffs using combined indices
Authors: Mullin James K.
Published: July 2002

In a paper in the November 1970 Communications of the ACM, V.Y. Lum introduced a technique of file indexing named combined indices. This technique permitted decreased retrieval time at the cost of increased storage space. This paper examines combined indices under conditions of file usage with different fractions of retrieval and update. Tradeoff curves are developed to show minimal cost of file usage by grouping various partially combined indices.
New LISP techniques for a paging environment
Authors: Rochfeld Arnold
Published: July 2002

The system described herein employs the block concept, and that of global and local variables, in addition to the methods applied in most LISP systems. Also, a new means of list representation is used: “local sequential” for lists created during compilation, and “block level sequential” for those created dynamically. A new garbage collection algorithm has been introduced to make lists as compact as possible; partial garbage collection is performed after each block exit instead of total garbage collection when storage is exhausted. The algorithm does not use the customary flagging procedure. This combination of features has eliminated the need for a free list, and effectively minimizes the number of pages used at any moment.
Algorithm 416: Rapid computation of coefficients of interpolation formulas
Authors: Gustafson Sven-Åke
Published: July 2002

This algorithm is a companion to [1] where the theoretical background is described
Generating pseudorandom numbers on a two's complement machine such as the IBM 360
Authors: Hemmerle W. J.
Published: July 2002

The familiar multiplicative congruential generator is examined in the context of the type of two's complement arithmetic used in the IBM 360 series. Different sequences of residues are considered and relationships established among them. It is shown that a sequence of positive and negative residues may be produced more simply and econimically than with the conventional approach and yet have twice the period of the latter without loss of desirable statistical properties. Another easily generated sequence involving absolute values is also shown to have twice the period but with the less attractive statistical properties. The statistical properties of these sequences are given and related to previously established criteria.
President's letter to the ACM membership
Authors: Oettinger A. G.
Published: July 2002

Computer programming deals with an enormous variety of activities and is carried on by people with a great variety of backgrounds. It seems clear that part but not all of this activity is evolving toward a distinct professional field, but that the scope of this emerging profession, and some of its economic, social, and educational characteristics are as yet by no means well defined. In this paper, these issues are examined and some opinions about them are expressed.
An efficient procedure for the generation of closed subsets
Authors: Waite William M.
Published: July 2002

An efficient algorithm is described for generating subsets of a set
S
which satisfy constraints of the form: “If

s
i

is a member of the subset, then

s
j

must also be a member of the subset.” The algorithm has been programmed in the WISP language and successfully run on the IBM 7094 in connection with a routine to detect feedback in multidimensional iterative networks.
An ambiguity in the description of ALGOL 60
Authors: Herriot John G.
Published: July 2002

When Algorithm 355 [
Comm. ACM 12
(Oct. 1969), 562] was originally submitted to the Algorithms Department it contained a construct which pointed up an ambiguity in the description of ALGOL 60 [Revised Report on the Algorithmic Language ALGOL 60,
Comm. ACM 6
(Jan. 1963), 1-17]. This ambiguity was not mentioned by Donald Knuth [The Remaining Trouble Spots in ALGOL 60,
Comm. ACM 10
(Oct. 1967), 611-618].
Minimax logarithmic error
Authors: Dunham Charles B.
Published: July 2002

In this note we point out how rational approximations which are best with respect to maximum logarithmic error can be computed by existing algorithms. Let
y
be a quantity that we wish to approximate and
y
be an approximation, then the logarithmic error is defined to be log (
y
/
y
). In a recent paper [3] it is shown that minimax logarithmic approximations are optimal for square root calculations, making the minimax logarithmic problem of practical interest. Suppose we wish to approximate a positive continuous function ƒ by a positive rational function
R
, then the logarithmic error at a point
x
is log (ƒ(
x
)) - log (
R
(
x
)). Our approximation problem is thus equivalent to ordinary approximation of a continuous function
g
= log (ƒ) by log (
R
). This is contained in the more general theory of approximation by
φ
(
R
),
φ
monotonic which appears in [1]. Computational procedures (based on the Remez algorithm) for the general problem are given in [2, 5]. These are easily adapted to the special case of logarithmic approximation and can readily be coded by modification of a standard rational Remez algorithm.
Still another use for FORTRAN II chaining
Authors: Arnold P. H.
Published: July 2002

This is to report a further use of the FORTRAN II Chain System. We, at Sandia, have modified the Chain subroutine to allow for picking up chains from the disk instead of a chain tape. The major change was the addition of a job identification to each chain system, thus allowing for different chain jobs with the same chain number to be available from the disk at any time.
A programming package for some general modes of arithmetic
Authors: Brooker R. A.
Published: July 2002

An interpretive programming package is described for computation with operands which may be real, complex, single or double precision, or real multiple precision. It also performs operations on matrices formed from these elements. A simple language structure is used to describe the computation.
Summary remarks
Authors: Gorn S.
Published: July 2002

The topics began with discussion of almost exclusively syntactic analysis and methods. Beginning with context-free phrase-structure languages, we considered limitations thereof to remove generative syntactic ambiguities (Floyd), and extensions thereto to introduce more context-dependence (Rose). As the conference proceeded we ran through a spectrum of considerations in which the expressions in the languages considered were examined less and less as meaningless objects (the formal, or purely syntactic approach, as in the paper by Steel) and required more and more meaningful interpretations. In other words, we became more and more involved with semantic considerations. It is clear, then, that applications of the study of mechanical languages to programming must involve semantic questions; ADD must mean something more than the concatenation of three (not two) characters. The papers beyond Session 1 were therefore discussing the mechanization of semantics, but in only one case did we hear about the formalization (and hence mechanization) of the
specification
of the semantics of a language (McCarthy).
Information Retrieval: Easy English, a language for information retrieval through a remote typewriter console
Authors: Rubinoff M. , Bergman S. , Rapp F. , Cautin H.
Published: July 2002

Easy English is a natural command language designed to simplify communication between man and machine through remote typewriter console. It has been developed for retrieval of documents from a computerized data base, the Moore School Information Systems Laboratory files. Requests are formulated in a standardized syntactical form (examples of which are presented), and this form is then transformed into an equivalent query expressed in the retrieval system's original Symbolic Command Language, which is briefly described.

Operation of Easy English is detailed by illustration of the transformations performed upon a sample request up to the point at which the request string is sent to the system. A macro flowchart of Easy English is included, and an Appendix provides the printout of a retrieval demonstration.
Scheduling meetings with a computer
Authors: Schultz Claire K. , Brooks Alan , Schwartz Phyllis
Published: July 2002

Computer scheduling of papers as it was developed for the 1960 meeting of the Federation of American Societies for Experimental Biology (FASEB) is described. The FASEB meeting is the largest scientific meeting held in the United States each year. The technique developed for FASEB can be applied to schedule any meeting with parallel sessions.
Computer patent disclosures
Authors: Kates Joseph P.
Published: July 2002

Suppose a potentially very valuable experimental multi-computer system is being designed by you and your group. You feel you have made at least a system invention. In your Company scientists and engineers are responsible for initiating invention disclosures.
Joint inventorship of computers
Authors: Hauptman Gunter A.
Published: July 2002

The term
joint inventorship
asks but does not necessarily answer the question, “Who is the true inventor of a computer?” I will try to show how “wrong” inventors are joined, how such improper joinder can be avoided, and its dangers. While the law permits the addition or subtraction of improperly joined inventors, it does not permit the substitution of one set of inventors for another set of inventors. Thus, despite corrective weapons, there are some pitfalls which must be avoided.
Estimation of heart parameters using skin potential measurements
Authors: Bellman R. , Collier C. , Kagiwada H. , Kalaba R. , Selvester R.
Published: July 2002

A fundamental problem of vectorcardiography is the estimation of the state of the heart on the basis of skin potential measurements.

A mathematical model relating ventricular dipoles to surface potentials is sketched. Then it is shown that the inverse problem—that of determining electrical heart parameters on the basis of skin potential measurements—may be viewed as a nonlinear multipoint boundary value problem.

A feasible solution, employing quasilinearization and high-speed digital computers, is given.
Time sharing in a traffic control program
Authors: Green L. E. S.
Published: July 2002

The Toronto traffic-signal control system consists of a variety of logically distinct computer programs, all competing for machine time. To satisfy these demands, a time-sharing program has been written whose purpose is to execute, in the order of a predefined priority, the various subprograms within the real-time system. In this paper the more interesting aspects of the time-sharing program are outlined.
Description of a high capacity, fast turnaround university computing center
Authors: Lynch W. C.
Published: July 2002

The operating system for the UNIVAC 1107 at Case Institute is reviewed. The system is of interest because of the low turn-around times achieved, the high throughput achieved and the lack of an operating staff. Turnaround times below 5 minutes and job volume above 75,000 per quarter year are reported.
A method for finding the least squares estimate of the intersection point of two Helices in space
Authors: Royston R. J. , Gregory J.
Published: July 2002

When the helical trajectories of two charged particles moving away from a common point in a magnetic field are reconstructed from measurements on the tracks, the reconstructed tracks are perturbed by measurement and other errors and do not, in general, intersect. A method is given for adjusting the reconstructed tracks in a least squares manner so that they do intersect.
Character structure and character parity sense for serial-by-bit data communication in the American Standard Code for information interchange
Authors: Lohse E. , Smith R. V. , Traub J. F. , Gorn S.
Published: July 2002

ACM proposes to republish contents of
Communications
Algorithms section is useable looseleaf format, with bimonthly updating service, provided there is sufficient demand. For details, see News item on page 583.
Corrigendum: Algorithm 806
Authors: Mascagni Michael , Srinivasan Ashok
Published: July 2002

In this article we present background, rationale, and a description of the Scalable Parallel Random Number Generators (SPRNG) library. We begin by presenting some methods for parallel pseudorandom number generation. We will focus on methods based on parameterization, meaning that we will not consider splitting methods such as the leap-frog or blocking methods. We describe, in detail, parameterized versions of the following pseudorandom number generators: (1) linear congruential generators, (ii) shift-register generators, and (iii) lagged-Fibonacci generators. We briefly describe the methods, detail some advantages and disadvantages of each method, and recount results from number theory that impact our understanding of their quality of parallel applications. SPRNG was designed around the uniform implementation of different families of parameterized random number generators. We then present a short description of SPRNG. The description contained within this document is meant only to outline the rationale behind and the capabilities of SPRNG. Much more information, including examples and detailed documentation aimed at helping users with putting and using SPRNG on scalable systems is available at http://sprng.cs.fsu.edu. In this description of SPRNG we discuss the random-number generator library as well as the suite of tests of randomness that is an integral part of SPRNG. Random-number tools for parallel Monte Carlo applications must be subjected to classical as well as new types of empirical tests of randomness to eliminate generators that show defects when used in scalable environments.
A general method of systematic interval computation for numerical integration of initial value problems
Authors: Martin W. C. , Paulson K. C. , Sashkin L.
Published: July 2002

A procedure is given for continuously computing and monitoring the step size to be used by a self-starting,
p
th-order numerical integration method to solve an initial value problem. The procedure uses an estimate of the truncation error to calculate the step size.
Addressing an array

Y
i

in
k
-dimensions by Fortran for analysis of variance
Authors: Garber M. J.
Published: July 2002

In analysis of variance and covariance of data in factorial designs, multidimensional arrays are the rule rather than the exception. The 1620 FORTRAN language is severely limited in its DIMENSION statements in that subscripting may be done for a maximum of only three dimensions. In the technique described, a one-dimensional ordered array may be entered into storage and without additional identification treated as multidimensional. The conceptual technique illustrated below for summation may be expanded to handle any number of factors and is limited only by the storage capacity of the computer.
Everyman's information retrieval system
Authors: Whitley V. W.
Published: July 2002

The information retrieval problem whose solution is presented here was posed by a technical library with limited budget and personnel. The solution, however, is quite general and is applicable to many different types of retrieval problems. Further, the method of solution makes it possible for many groups who have previously dismissed an information retrieval program s expensive and difficult (from a programming standpoint) to reconsider their position, for the present solution makes it possible to install an information retrieval program in less than three months, and with relatively little equipment.
Logic-structure tables
Authors: Cantrell H. N. , King J. , King F. E. H.
Published: July 2002

Logic tables are an excellent way of developing and expressing the logic required in procedures, operations, systems and circuits. A set of rules for writing and using logic tables is explained by means of some simple examples. Then the logic structure of a vending machine is given in which two logic tables are used. Logic tables are two-dimensional in nature, enabling us to fully express and consider both the sequential and parallel aspects of logic. They can be compiled directly into a computer program and so eliminate the need for flow charting and hand coding.
A penny-matching program
Authors: Wall Elizabeth , Brown Richard M.
Published: July 2002

The logic of a penny-matching program written for the CSX-1 is described.
A note on multiple precision arithmetic
Authors: Cox Albert G. , Luther H. A.
Published: July 2002

Since computers have means to detect overflow on addition or subtraction, this can be used in a multiple precision addition-subtraction subroutine to obviate a sign analysis. Consider all integers in the computer to be expressed “radix
t
”, that is, in the form
a
=
a
0
+
a
1
t
+ ··· +

a
n
t
n

where

a
i

are of like sign and have magnitudes less than
t
.
t
is a positive integer determined by the word length of the computer. Consider the expression
c
=
a
±
b
= (
a
0
±
b
0
) + (
a
1
±
b
1
)
t
+ ··· + (

a
n

±

b
n

)

t
n

. Here

a
i

±

b
i

may exceed the storage capacity of one word or may have a sign different from
c
.