The suggestions in this paper are part of the terminology used in work for the University of Pennsylvania's Office of Computer Research and Education. The work is jointly supported by the National Science Foundation* and the Air Force Office of Scientific Research.†

# August 1961 - Vol. 4 No. 8

## Features

A generalized polyphase merge algorithm

The k-generalized Fibonacci numbers are defined as in [1]. A polyphase merge (merging an equal number of sequences from k tapes onto a single unused tape) using k+1 tapes is defined in terms of linear combinations of these numbers. A method is described to output sequences onto k of k+1 tapes after the internal sorting of elements to form sequences. This method will permit a polyphase merge of sequences of sorted elements provided that enough sequences are generated internally to place the proper numbers of sequences on each of the k tapes. For each value of k, there is a set of permissible numbers that can represent the total number of sequences generated during the original output process. If one of these numbers is met exactly and if there is a specific distribution of sequences on the k tapes, then a polyphase merge may proceed. If these conditions are not met, an algorithm is necessary to adjust the numbers of sequences to permit a polyphase merge. This paper describes such an algorithm.

A 48-bit pseudo-random generator

A new 48-bit pseudo-random number generator, suitable for several computers, was tested statistically for randomness to determine its adequacy for use in Monte Carlo programs. Frequency tests, distributions of certain low-order moments, runs up and down, and runs above and below the mean were applied to one-half million generated numbers lying within the interval (0, 1) and to three sets of integers obtained from specified bits within the generated numbers. These tests substantiated the randomness of all numbers except for the set of integers coming from the least significant bits.

A note on multiple precision arithmetic

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 = a0 + a1t + ··· + antn where ai 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 = (a0 ± b0) + (a1 ± b1)t + ··· + (an ± bn)tn. Here ai ± bi may exceed the storage capacity of one word or may have a sign different from c.