June 1975 - Vol. 18 No. 6
Features
Algorithm 492: Generation of all the cycles of a graph from a set of basic cycles [H]
The PL/I procedure CYCLE_GENERATOR is an implementation of Gibbs' algorithm [1] for finding all the cycles in a graph from a set of basic cycles.
Illumination for computer generated pictures
The quality of computer generated images of three-dimensional scenes depends on the shading technique used to paint the objects on the cathode-ray tube screen. The shading algorithm itself depends in part on the method for modeling the object, which also determines the hidden surface algorithm. The various methods of object modeling, shading, and hidden surface removal are thus strongly interconnected. Several shading techniques corresponding to different methods of object modeling and the related hidden surface algorithms are presented here. Human visual perception and the fundamental laws of optics are considered in the development of a shading rule that provides better quality and increased realism in generated images.
A cost oriented algorithm for data set allocation in storage hierarchies
Data set allocation in today's multilevel storage systems is usually based on qualitative, ad hoc decisions. While it would be desirable to obtain an optimal solution to this allocation problem, it is clear that the number of parameters involved makes it intractable to straight-forward solution. In such a situation, we must find a set of assumptions which simplify the problem greatly, but which still provide a basis for considering all significant cost elements. This paper presents such a first, quantitative allocation step. It considers many of the significant detailed costs of system utilization, data storage, data staging, and data migration. Although many avenues of further improvement are available, the present algorithm seems to be usefully accurate. As such, it can aid in quantifying the problems of data set allocation, storage system configuration, and new device designs.
This paper compares a new method of simulation organization, called the significant event method, with an old one, called the clock pulse method, using as examples two automobile traffic models. The significant event method is found to be more efficient than the clock pulse method at low levels of system interaction and less efficient at high levels. A simple mathematical model for the trade-off in the relative running time of the two methods is developed. The model aids in choosing between the two simulation methods for a particular experiment. It is concluded that the significant event method can be of value in the simulation of some systems when computational efficiency is of sufficient importance.
An efficient arrangement for interpretive code is described. It is related to Bell's notion of threaded code but requires less space and is more amenable to machine independent implementations.
A simplified recombination scheme for the Fibonacci buddy system
A simplified recombination scheme for the Fibonacci buddy system which requires neither tables nor repetitive calculations and uses only two additional bits per buffer is presented.
Efficient string matching: an aid to bibliographic search
This paper describes a simple, efficient algorithm to locate all occurrences of any of a finite number of keywords in a string of text. The algorithm consists of constructing a finite state pattern matching machine from the keywords and then using the pattern matching machine to process the text string in a single pass. Construction of the pattern matching machine takes time proportional to the sum of the lengths of the keywords. The number of state transitions made by the pattern matching machine in processing the text string is independent of the number of keywords. The algorithm has been used to improve the speed of a library bibliographic search program by a factor of 5 to 10.
A linear space algorithm for computing maximal common subsequences
The problem of finding a longest common subsequence of two strings has been solved in quadratic time and space. An algorithm is presented which will solve this problem in quadratic time and in linear space.
Addition in an arbitrary base without radix conversion
hnique; using it, one may add and subtract numbers represented in any radix, including a mixed radix, and stored one digit per byte in bytes of sufficient size. Radix conversion is unnecessary, no looping is required, and numbers may even be stored in a display (I/O) format. Applications to Cobol, MIX, and hexadecimal sums are discussed.
Improved event-scanning mechanisms for discrete event simulation
Simulation models of large, complex “real-world” applications have occasionally earned the reputation of eating up hours of computer time. This problem may be attributed in part to difficulties such as slow stochastic convergence. However, an additional problem lies in the fact that a significant amount of bookkeeping time is required to keep future events in their proper sequence. This paper presents a method for significantly reducing the time spent scanning future events lists in discrete event simulations. Three models are presented, all of which improve in effectiveness as the events-list scan problem becomes more burdensome.
