Orbits and Lattices for Linear Random Number Generators with Composite Moduli

In order to analyze certain types of combinations of multiple recursive linear congruential generators (MRGs), we introduce a generalized spectral test. We show how to apply the test in large dimensions by a recursive procedure based on the fact that such combinations are subgenerators of other MRGs with composite moduli. We illustrate this with the well-known RANMAR generator. We also design an algorithm generalizing the procedure to arbitrary random number generators.

     

A Method of Systematic Search for Optimal Multipliers in Congruential Random Number Generators

This paper presents a method of systematic search for optimal multipliers for congruential random number generators. The word-size of computers is a limiting factor for development of random numbers. The generators for computers up to 32 bit word-size are already investigated in detail by several authors. Some partial works are also carried out for moduli of 2⁴⁸ and higher sizes. Rapid advances in computer technology introduced recently 64 bit architecture in computers. There are considerable efforts to provide appropriate parameters for 64 and 128 bit moduli. Although combined generators are equivalent to huge modulus linear congruential generators, for computational efficiency, it is still advisable to choose the maximum moduli for the component generators. Due to enormous computational price of present algorithms, there is a great need for guidelines and rules for systematic search techniques. Here we propose a search method which provides ‘fertile’ areas of multipliers of perfect quality for spectral test in two dimensions. The method may be generalized to higher dimensions. Since figures of merit are extremely variable in dimensions higher than two, it is possible to find similar intervals if the modulus is very large. This revised version was published online in July 2006 with corrections to the Cover Date.     

Tables of maximally equidistributed combined LFSR generators

We give the results of a computer search for maximally equidistri-
buted combined linear feedback shift register (or Tausworthe) random number generators, whose components are trinomials of degrees slightly less than 32 or 64. These generators are fast and have good statistical properties.

     

Maximally Equidistributed Combined Tausworthe Generators

Tausworthe random number generators based on a primitive trinomial allow an easy and fast implementation when their parameters obey certain restrictions. However, such generators, with those restrictions, have bad statistical properties unless we combine them. A generator is called maximally equidistributed if its vectors of successive values have the best possible equidistribution in all dimensions. This paper shows how to find maximally equidistributed combinations in an efficient manner, and gives a list of generators with that property. Such generators have a strong theoretical support and lend themselves to very fast software implementations.

     

Theoretical analyses of forward and backward heuristics of multiple recursive random number generators

This article focuses on heuristic algorithms that are capable of finding multiple recursive generators (MRGs) with maximum spectral value criterion in a short period of time. Two promising algorithms, provided by Kao and Tang, are the forward and backward heuristics. Here we provide a deep understanding of the forward and backward heuristics for an MRG. The forward heuristic finds a sequence of partial sets of multipliers that lead toward a better spectral value. For the second-order MRGs, the performance of the backward heuristic theoretically outperforms that of the forward heuristic. The effectiveness of the backward heuristic is numerically confirmed by the experiments we present.     

An analysis of linear congruential random number generators when multiplier restrictions exist

This research conducts an exhaustive search for the best spectral test performance in a full period linear congruential generator (LCG) with the largest prime modulus smaller than 2^b, for bit sizes b = 8, 9, … , 31. Three types of restrictions on multipliers are presented and some full period LCGs are presented for use in three different spectral test dimensions. According to the exhaustive searches we perform, the results indicate differences exist among the numbers of possible multipliers for the three types of multiplier restrictions. We demonstrate that these differences can affect the performance of spectral tests for different dimensions.     

Generators of some Ramanujan formulas

In this paper we prove some Ramanujan type formulas for 1/π but without using the theory of modular forms. Instead we use the WZ—method created by H. Wilf and D. Zeilberger and find some hypergeometric functions in two variables which are second components of WZ—pairs than can be certified using Zeilberger's EKHAD package. These certificates have an additional property which allows us to get generalized Ramanujan's type series which are routinely proven by computer. We call these second hypergeometric components of the WZ—pairs generators. Finding generators seems a hard task but using a kind of experimental research (explained below), we have succeeded in finding some of them. Unfortunately we have not found yet generators for the most impressive Ramanujan's formulas. We also prove some interesting binomial sums for the constant 1/π². Finally we rewrite many of the obtained series using pochhammer symbols and study the rate of convergence. 2000 Mathematics Subject Classification Primary—33C20     

Using hydropower to smooth intermittent and unreliable sources of generation

This work describes, in part, the extent to which the large hydropower system on the Snake and Columbia rivers, and tributaries, could be used to ‘smooth’ or level the intermittent contributions of large numbers of wind generators, so that the sum of these contributions becomes reliable. Data for wind generators on site is given, the methods by which the ‘smoothing’ would occur is described, and a computer simulation model of the Pacific Northwest hydropower system is used to develop several case studies. The several constraints imposed on the flexibility of the hydropower system are defined by streamflow restrictions at the hydropower projects.     

Bases and Ideal Generators for Projective Monomial Curves

In this article we study bases for projective monomial curves and the relationship between the basis and the set of generators for the defining ideal of the curve. We understand this relationship best for curves in ?³ and for curves defined by an arithmetic progression. We are able to prove that the latter are set theoretic complete intersections.     

Modified Alternating $$\vec{k}$$–generators

This paper deals with a class of pseudorandom bit generators – modified alternating –generators. This class is constructed similarly to the class of alternating step generators. Three subclasses of are distinguished, namely linear, mixed and nonlinear generators. The main attention is devoted to the subclass of linear and mixed generators generating periodic sequences with maximal period lengths. A necessary and sufficient condition for all sequences generated by the linear generators of to be with maximal period lengths is formulated. Such sequences have good statistical properties, such as distribution of zeroes and ones, and large linear complexity. Two methods of cryptanalysis of the proposed generators are given. Finally, three new classes of modified alternating –generators, designed especially to be more secure, are presented.     

Uniform random number generation

In typical stochastic simulations, randomness is produced by generating a sequence of independent uniform variates (usually real-valued between 0 and 1, or integer-valued in some interval) and transforming them in an appropriate way. In this paper, we examine practical ways of generating (deterministic approximations to) such uniform variates on a computer. We compare them in terms of ease of implementation, efficiency, theoretical support, and statistical robustness. We look in particular at several classes of generators, such as linear congruential, multiple recursive, digital multistep, Tausworthe, lagged-Fibonacci, generalized feedback shift register, matrix, linear congruential over fields of formal series, and combined generators, and show how all of them can be analyzed in terms of their lattice structure. We also mention other classes of generators, like non-linear generators, discuss other kinds of theoretical and empirical statistical tests, and give a bibliographic survey of recent papers on the subject.     

Theoretical and empirical convergence results for additive congruential random number generators

Additive Congruential Random Number (ACORN) generators represent an approach to generating uniformly distributed pseudo-random numbers that is straightforward to implement efficiently for arbitrarily large order and modulus; if it is implemented using integer arithmetic, it becomes possible to generate identical sequences on any machine.This paper briefly reviews existing results concerning ACORN generators and relevant theory concerning sequences that are well distributed mod 1 in k dimensions. It then demonstrates some new theoretical results for ACORN generators implemented in integer arithmetic with modulus M=2^μ showing that they are a family of generators that converge (in a sense that is defined in the paper) to being well distributed mod 1 in k dimensions, as μ=log₂M tends to infinity. By increasing k, it is possible to increase without limit the number of dimensions in which the resulting sequences approximate to well distributed.The paper concludes by applying the standard TestU01 test suite to ACORN generators for selected values of the modulus (between 2⁶⁰ and 2¹⁵⁰), the order (between 4 and 30) and various odd seed values. On the basis of these and earlier results, it is recommended that an order of at least 9 be used together with an odd seed and modulus equal to 2^30p, for a small integer value of p. While a choice of p=2 should be adequate for most typical applications, increasing p to 3 or 4 gives a sequence that will consistently pass all the tests in the TestU01 test suite, giving additional confidence in more demanding applications.The results demonstrate that the ACORN generators are a reliable source of uniformly distributed pseudo-random numbers, and that in practice (as suggested by the theoretical convergence results) the quality of the ACORN sequences increases with increasing modulus and order.     

Directed graph representation of half-rate additive codes over GF(4)

We show that (n, 2 ⁿ ) additive codes over GF(4) can be represented as directed graphs. This generalizes earlier results on self-dual additive codes over GF(4), which correspond to undirected graphs. Graph representation reduces the complexity of code classification, and enables us to classify additive (n, 2 ⁿ ) codes over GF(4) of length up to 7. From this we also derive classifications of isodual and formally self-dual codes. We introduce new constructions of circulant and bordered circulant directed graph codes, and show that these codes will always be isodual. A computer search of all such codes of length up to 26 reveals that these constructions produce many codes of high minimum distance. In particular, we find new near-extremal formally self-dual codes of length 11 and 13, and isodual codes of length 24, 25, and 26 with better minimum distance than the best known self-dual codes.     

Mutation of Auslander Generators for Selfinjective Algebras

Let Λ be an artin algebra with representation dimension equal to three and M an Auslander generator of Λ. We show how, under certain assumptions, we can mutate M to get a new Auslander generator whose endomorphism ring is derived equivalent to the endomorphism ring of M. We apply our results to selfinjective algebras with radical cube zero of infinite representation type, where we construct an infinite set of Auslander generators.     

On the number of generators of Cohen-Macaulay ideals

Several bounds on the number of generators of Cohen-Macaulay ideals known in the literature follow from a simple inequality which bounds the number of generators of such ideals in terms of mixed multiplicities. Results of Cohen and Akizuki, Abhyankar, Sally, Rees and Boratynski-Eisenbud-Rees are deduced very easily from this inequality.

     

A Random-number Generator for Microcomputers

A very efficient and statistically sound random-number generator of the prime modulus multiplicative congruential method is devised for 16-bit microcomputers (8-bit machines have to be double-precisioned). This generator combines several generators, and cycles every (2¹⁵-20)² numbers with 2¹⁵-20 different numbers in one cycle. When precision is relatively unimportant, this generator is demonstrated to be a good random-number generator.     

Modelling nonlinear sequence generators in terms of linear cellular automata

In this work, a wide family of LFSR-based sequence generators, the so-called clock-controlled shrinking generators (CCSGs), has been analyzed and identified with a subset of linear cellular automata (CA). In fact, a pair of linear models describing the behavior of the CCSGs can be derived. The algorithm that converts a given CCSG into a CA-based linear model is very simple and can be applied to CCSGs in a range of practical interest. The linearity of these cellular models can be advantageously used in two different ways: (a) for the analysis and/or cryptanalysis of the CCSGs and (b) for the reconstruction of the output sequence obtained from this kind of generators.