Browsing by Author "Deng, Lih-Yuan"

Now showing 1 - 9 of 9

64-Bit and 128-bit DX random number generators
(2010-08-01)
Deng, Lih-Yuan
;
Lu, Henry Horng-Shing
;
Chen, Tai-Been
;
統計學研究所
;
Institute of Statistics
Extending 32-bit DX generators introduced by Deng and Xu (ACM Trans Model Comput Simul 13:299-309, 2003), we perform an extensive computer search for classes of 64-bit and 128-bit DX generators of large orders. The period lengths of these high resolution DX generators are ranging from 10(1915) to 10(58221). The software implementation of these generators can be developed for 64-bit or 128-bit hardware. The great empirical performances of DX generators have been confirmed by an extensive battery of tests in the TestU01 package. These high resolution DX generators can be useful to perform large scale simulations in scientific investigations for various computer systems.
Design and implementation of efficient and portable Multiple Recursive Generators with few zero coefficients
(2008)
Deng, Lih-Yuan
;
Li, Huajiang
;
Shiau, Jyh-Jen Horng
;
Tsai, Gwei-Hung
;
統計學研究所
DX-k, proposed by Deng and Xu [2003], is a special class of Multiple Recursive Generators (MRGs) where all nonzero coefficients of the k-th order recurrence are equal. In particular, a DX-k generator requires only up to four nonzero coefficients in its recurrence equation, hence is very efficient in computation. However, a random number generator with few nonzero coefficients has a drawback that, when the k-dimensional state vector is close to the zero vector, the subsequent numbers generated may stay within a neighborhood of zero for quite many of them before they can break away from this near-zero land, a property apparently not desirable in the sense of randomness. Consequently, two generated sequences using the same DX generator with nearly identical initial state vectors may not depart from each other quickly enough. To avoid the above potential problem, we consider MRGs with very few zero coefficients. To make such generators efficient and portable, we propose selecting the same nonzero value for all coefficients (with at most one exception) in the recurrence equation. With this feature, the proposed generators can be implemented efficiently via a higher-order recurrence of few zero coefficients. Note that the new class of generators is an opposite of the DX generators in terms of the number of nonzero coefficients. Several such generators with the maximum period have been found via computer search and presented in the paper for ready implementation.
Efficient computer search of large-order multiple recursive pseudo-random number generators
(2012-07-01)
Deng, Lih-Yuan
;
Shiau, Jyh-Jen Horng
;
Lu, Henry Horng-Shing
;
統計學研究所
;
Institute of Statistics
Utilizing some results in number theory, we propose an efficient method to speed up the computer search of large-order maximum-period Multiple Recursive Generators (MRGs). We conduct the computer search and identify many efficient and portable MRGs of order up to 25,013, which have the equi-distribution property in up to 25,013 dimensions and the period lengths up to 10(233,361) approximately. In addition, a theoretical test is adopted to further evaluate and compare these generators. An extensive empirical study shows that these generators behave well when tested with the stringent Crush battery of the test package TestU01. (C) 2012 Elsevier B.V. All rights reserved.
Large-Order Multiple Recursive Generators with Modulus 2(31)-1
(2012-09-01)
Deng, Lih-Yuan
;
Shiau, Jyh-Jen Horng
;
Lu, Henry Horng-Shing
;
統計學研究所
;
Institute of Statistics
The performance of a maximum-period multiple recursive generator (MRG) depends on the choices of the recurrence order k, the prime modulus p, and the multipliers used. For a maximum-period MRG, a large-order k not only means a large period length (i.e., p(k) - 1) but, more importantly, also guarantees the equidistribution property in high dimensions (i. e., up to k dimensions), a desirable feature for a good random-number generator. As to generating efficiency, in addition to the multipliers, some special choices of the prime modulus p can significantly speed up the generation of pseudo-random numbers by replacing the expensive modulo operation with efficient logical operations. To construct efficient maximum-period MRGs of a large order, we consider the prime modulus p = 2(31) - 1 and, via extensive computer search, find two large values of k, 7 1 499 and 20,897, for which p(k) - 1 can be completely factorized. The successful search is achieved with the help of some results in number theory as well as some modern factorization methods. A general class of MRGs is introduced, which includes several existing classes of efficient generators. With the factorization results, we are able to identify via computer search within this class many portable and efficient maximum-period MRGs of order 7,499 or 20,897 with prime modulus 2(31) - 1 and multipliers of powers-of-two decomposition. These MRGs all pass the stringent TestU01 test suite empirically.
Non-linear Pseudo-Random Number Generators via Coupling DX Generators with the Logistic Map
(2012)
Li, Chung-Yi
;
Chou, Hwai-Pwu
;
Deng, Lih-Yuan
;
Shiau, Jyh-Jen Horng
;
Lu, Henry Horng-Shing
This brief proposes a class of nonlinear pseudo-random number generators (PRNGs) based on coupling linear generators (DX generators) with a nonlinear generator (digitized Logistic map). By breaking the linearity, the unpredictability of the proposed generators in the family of coupling PRNGs is enhanced while the nice properties of efficiency, long period, and excellent statistical properties are preserved. Furthermore, the hardware efficiencies are validated by hardware implementations using a TSMC 0.18 mu m CMOS process with a throughput rate greater than 8,000 Mbit/s. In addition to the extremely long period length, the proposed nonlinear PRNGs can generate random sequences that fulfill all the randomness requirements of NIST SP 800-22 test suite.
Parallel Random Number Generators Based on Large Order Multiple Recursive Generators
(2009-01-01)
Deng, Lih-Yuan
;
Shiau, Jyh-Jen Horng
;
Tsai, Gwei-Hung
;
理學院
;
College of Science
Classical random number generators like Linear Congruential Generators (LCG) and Multiple Recursive Generators (MRG) are popular for large-scale simulation studies. To speed up the simulation process, a systematic method is needed to construct and parallelize the random number generators so that they can run simultaneously on several computers or processors. LCGs and MRGs have served as baseline generators for some parallel random number generator (PRNG) constructed in the literature. In this paper, we consider the parallelization problem particularly for a general class of efficient and portable large-order MRGs, in which most coefficients of the recurrence equation are nonzero. With many nonzero terms, such MRGs have an advantage over the MRGs with just a few nonzero terms that they can recover more quickly from a bad initialization. With the special structure imposed on the nonzero coefficients of the new class of generators, the proposed PRNGs can be implemented efficiently. A method of automatic generation of the corresponding MRGs for parallel computation is presented.
Phylogenetic tree construction using trinucleotide usage profile (TUP)
(2016-10-06)
Chen, Si
;
Deng, Lih-Yuan
;
Bowman, Dale
;
Shiau, Jyh-Jen Horng
;
Wong, Tit-Yee
Background: It has been a challenging task to build a genome-wide phylogenetic tree for a large group of species containing a large number of genes with long nucleotides sequences. The most popular method, called feature frequency profile (FFP-k), finds the frequency distribution for all words of certain length k over the whole genome sequence using (overlapping) windows of the same length. For a satisfactory result, the recommended word length (k) ranges from 6 to 15 and it may not be a multiple of 3 (codon length). The total number of possible words needed for FFP-k can range from 4(6) = 4096 to 4(15). Results: We propose a simple improvement over the popular FFP method using only a typical word length of 3. A new method, called Trinucleotide Usage Profile (TUP), is proposed based only on the (relative) frequency distribution using non-overlapping windows of length 3. The total number of possible words needed for TUP is 43 = 64, which is much less than the total count for the recommended optimal " resolution" for FFP. To build a phylogenetic tree, we propose first representing each of the species by a TUP vector and then using an appropriate distance measure between pairs of the TUP vectors for the tree construction. In particular, we propose summarizing a DNA sequence by a matrix of three rows corresponding to three reading frames, recording the frequency distribution of the non-overlapping words of length 3 in each of the reading frame. We also provide a numerical measure for comparing trees constructed with various methods. Conclusions: Compared to the FFP method, our empirical study showed that the proposed TUP method is more capable of building phylogenetic trees with a stronger biological support. We further provide some justifications on this from the information theory viewpoint. Unlike the FFP method, the TUP method takes the advantage that the starting of the first reading frame is (usually) known. Without this information, the FFP method could only rely on the frequency distribution of overlapping words, which is the average (or mixture) of the frequency distributions of three possible reading frames. Consequently, we show (from the entropy viewpoint) that the FFP procedure could dilute important gene information and therefore provides less accurate classification.
Scalable parallel multiple recursive generators of large order
(2009-01-01)
Deng, Lih-Yuan
;
Li, Huajiang
;
Shiau, Jyh-Jen Horng
;
統計學研究所
;
Institute of Statistics
To speed up the process of performing a large statistical simulation study, it is natural and common to divide the large-scale simulation task into several relatively independent sub-tasks in a way that these sub-tasks can be handled by individual processors in parallel. To obtain a good overall simulation result by synthesizing results from these sub-tasks, it is crucial that good parallel random number generators are used. Thus, designing suitable and independent uniform random number generators for the sub-tasks has become a very important issue in large-scale parallel simulations. Two commonly used uniform random number generators, linear congruential generator (LCG) and multiple recursive generator (MRG), have served as backbone generators for some parallel random number generators constructed in the past. We will discuss some general construction methods. A systematic leapfrog method to automatically choose different multipliers for LCGs to have the maximum-period and a method to construct many maximum-period MRGs from a single MRG are available in the literature. In this paper, we propose to combine both approaches to generate different MRGs "randomly", quickly and automatically. while retaining the maximum-period property. Published by Elsevier B.V.
Secure and Fast Encryption (SAFE) with Classical Random Number Generators
(2018-08-01)
Deng, Lih-Yuan
;
Shiau, Jyh-Jen Horng
;
Lu, Henry Horng-Shing
;
Bowman, Dale
;
統計學研究所
Pseudo-random number generators (PRNGs) play an important role in both areas of computer simulation and computer security. Currently, there appears to be a huge divide between the types of PRNGs used in these two areas. For PRNGs in computer security applications, the security concern is extremely important. For PRNGs in computer simulation applications, the properties of high-dimensional equi-distribution, efficiency, long period-length, and portability are important. In recent years, there have been many PRNGs proposed in the area of computer simulation satisfying these nice properties. However, most of them are linear generators, thus sharing the same weakness in predictability. The major aim of this article is to propose a general class of secure generators, called SAFE (secure and fast encryption) generators, by properly "mixing" two baseline generators with the aforementioned properties to obtain a secure generator that would inherit these nice properties. Specifically, we propose applying a general mutual-shuffling method to certain linear generators, such as the currently most popular MT19937 generator and large-order multiple recursive generators, as well as outputting certain nonlinear transformations of the generated variates to construct secure PRNGS.