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.     

Proving the deterministic period breaking of linear congruential generators using two tile quasicrystals

We describe the design of a family of aperiodic PRNGs (APRNGs). We show how a one-dimensional two tile cut and project quasicrystal (2TQC) used in conjunction with LCGs in an APRNG generates an infinite aperiodic pseudorandom sequence. In the suggested design, any 2TQC corresponding to unitary quadratic Pisot number combined with either one or two different LCGs can be used.

     

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.

     

Lattice computations for random numbers

We improve on a lattice algorithm of Tezuka for the computation of the -distribution of a class of random number generators based on finite fields. We show how this is applied to the problem of constructing, for such generators, an output mapping yielding optimal -distribution.

     

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.

     

Distribution Properties of Multiply-with-Carry Random Number Generators

We study the multiply-with-carry family of generators proposed by Marsaglia as a generalization of previous add-with-carry families. We define for them an infinite state space and focus our attention on the (finite) subset of recurrent states. This subset will, in turn, split into possibly several subgenerators. We discuss the uniformity of the -dimensional distribution of the output of these subgenerators over their full period. In order to improve this uniformity for higher dimensions, we propose a method for finding good parameters in terms of the spectral test. Our results are stated in a general context and are applied to a related complementary multiply-with-carry family of generators.

     

Efficient lattice assessment for LCG and GLP parameter searches

In the present paper we show how to speed up lattice parameter searches for Monte Carlo and quasi-Monte Carlo node sets. The classical measure for such parameter searches is the spectral test which is based on a calculation of the shortest nonzero vector in a lattice. Instead of the shortest vector we apply an approximation given by the LLL algorithm for lattice basis reduction. We empirically demonstrate the speed-up and the quality loss obtained by the LLL reduction, and we present important applications for parameter selections.

     

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.     

Successive minima profile,lattice profile,and joint linear complexity profile of pseudorandom multisequences

In this paper we use the successive minima profile to measure structural properties of pseudorandom multisequences. We show that both the lattice profile and the joint linear complexity profile of a multisequence can be expressed in terms of the successive minima profile.     

On the structure of digital explicit nonlinear and inversive pseudorandom number generators

We analyze the lattice structure and distribution of the digital explicit inversive pseudorandom number generator introduced by Niederreiter and Winterhof as well as of a general digital explicit nonlinear generator. In particular, we extend a lattice test designed for this class of pseudorandom number generators to parts of the period and arbitrary lags and prove that these generators pass this test up to very high dimensions. We also analyze the behavior of digital explicit inversive and nonlinear generators under another very strong lattice test which in its easiest form can be traced back to Marsaglia and provides a complexity measure essentially equivalent to linear complexity.     

Recent trends in random number and random vector generation

A survey of recent work in the areas of uniform pseudorandom number and uniform pseudorandom vector generation is presented. The emphasis is on methods for which a detailed theory is available. A progress report on the construction of quasirandom points for efficient multidimensional numerical integration is also given.     

Constructing efficient solutions structure of multiobjective linear programming

It is not a difficult task to find a weak Pareto or Pareto solution in a multiobjective linear programming (MOLP) problem. The difficulty lies in finding all these solutions and representing their structure. This paper develops an algorithm for solving this problem. We investigate the solutions and their relationships in the objective space. The algorithm determines finite number of weights, each of which corresponds to a weighted sum problems. By solving these problems, we further obtain all weak Pareto and Pareto solutions of the MOLP and their structure in the constraint space. The algorithm avoids the degeneration problem, which is a major hurdle of previous works, and presents an easy and clear solution structure.     

The topological structure of maximal lattice free convex bodies: The general case

Given a genericm × n matrixA, the simplicial complexK(A) is defined to be the collection of simplices representing maximal lattice point free convex bodies of the form {x : Ax b}. The main result of this paper is that the topological space associated withK(A) is homeomorphic withR ^m–1 . © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Supported by NSF grant SES-9121936 and the program in Discrete Mathematics at Yale University.Partially supported by the Hungarian NSF grant 1909 and the program in Discrete Mathematics at Yale University.     

KdV方程的延拓结构

利用外微分形式系统和Lie代数表示理论提出了求解非线性波方程Lax对的延拓结构理论,该方法是构造非线性波方程Lax对的系统最有效的方法.其关键在于如何给出延拓代数的具体表示,如微分算子表示或矩阵表示.如果一个非线性波方程具有非平凡的延拓代数,则称其延拓代数可积,本篇论文主要利用延拓结构理论,讨论KdV方程的解,同时给出...     

内生无限平面网格上基于策略互动的均衡网络结构及吸收集

在内生网络环境下,基于局中人的策略互动研究了均衡网络的结构特性,以及局中人策略选择的倾向性. 在动态进程的同一阶段,规定所有局中人同时进行策略更新,研究了网络生成的连接费用、互动支付等参数之间的相互关系及其对均衡结构或吸收集的影响. 主要贡献是将网络的内生性与无限网格上的策略互动联系在一起,得出不同连接费用水平之下的均衡结构、吸收集的准确特征.     

Sufficient conditions for the existence of global random attractors for stochastic lattice dynamical systems and applications

In this paper, we first present some sufficient conditions for the existence of a global random attractor for general stochastic lattice dynamical systems. These sufficient conditions provide a convenient approach to obtain an upper bound of Kolmogorov ε-entropy for the global random attractor. Then we apply the abstract result to the stochastic lattice sine-Gordon equation.     

Function algebras and the lattice of compactifications

We provide some conditions as to when for two locally compact spaces and (where is the lattice of all Hausdorff compactifications of ). More specifically, we prove that if and only if . Using this result, we prove several extensions to the case where is embedded as a sub-lattice of and to where and are not locally compact.

One major contribution is in the use of function algebra techniques. The use of these techniques makes the extensions simple and clean and brings new tools to the subject.

     

A potential of fuzzy relations with a linear structure: The contractive case

In this paper we develop a potential theory of fuzzy relations on the positive orthant in a Euclidean space. By introducing a linear structure for fuzzy relations, the existence of a potential and its characterization by fuzzy relational equation are derived under the assumption of contraction and compactness. In the one-dimensional unimodal case, a potential is given explicity. Also, a numerical example is shown to illustrate our approaches.