Asaki Saito
Future University Hakodate, Japon
https://www.researchgate.net/profile/Asaki_Saito
Date(s) : 03/12/2019 iCal
11 h 00 min - 12 h 00 min
Pseudorandom sequences with high (dimensional) uniformity and quasirandom sequences are known to be very useful for Monte Carlo computation. It is, however, still an interesting question how we can generate a {pseudorandom sequence in the original sense}, i.e., a computer-generated sequence of numbers that appear similar to a typical sample of independently identically distributed random variables.
According to ergodic theory, one of the simplest chaotic maps on the unit interval, namely the Bernoulli map {x} ↦ 2{x} mod 1, can generate ideal random binary sequences. However, its use as a pseudorandom number generator has been difficult due to the drawbacks of conventional simulation methods, such as those using double-precision binary floating-point numbers or arbitrary-precision rational numbers.
In this talk, we present a pseudorandom bit generator that exactly computes chaotic true orbits of the Bernoulli map on real cubic algebraic integers having complex conjugates. In particular, we clarify a seed selection method that can select initial points (i.e., seeds) without bias and can make the pseudorandom sequences derived from them be very different from each other.
Moreover, in order to evaluate the memory usage of our generator, we give upper bounds concerning the growth of the representation of points on a true orbit. We also report results of a large variety of tests indicating that the generated pseudorandom sequences have good statistical properties as well as an advantage over what is probably the most popular generator, the Mersenne Twister MT19937. In the end, we discuss the use of Newton’s method to approximate the true orbit generator.
This is a joint work with Akihiro Yamaguchi
Catégories