Random number generation device and random number generation method

#This application is based upon and claims the benefit of priority of the prior Japanese Patent Application No. 2019-131765, fled on Jul. 17, 2019, the entire contents of which are incorporated herein by reference.

#The embodiment discussed herein is related to a random number generation device and a random number generation method.

#When information processing is carried out by using a computer, an algorithm corresponding to the processing to be carried out is executed to obtain a target result. Among such cases, in a case where there is a highly efficient deterministic algorithm, the calculation process is often carried out in a relatively short time. Therefore, it is very important to find an efficient deterministic algorithm. However, such an efficient algorithm is present only for some relatively simple problems.

#FIG. 1 is a diagram illustrating a configuration example of a random number generation device configured to generate a normal random number.

#FIG. 2 is a diagram illustrating a configuration example of a random number generation device configured to generate an exponential random number.

#FIG. 3 is a diagram illustrating a configuration example of a random number generation device using feedback.

#As an effective calculation technique applicable to a relatively wide range of problems for which an efficient algorithm is not present, there exists a Monte Carlo method in which calculation processing is carried out by using random numbers, and this method is widely used in numerical calculations (for example, numerical integration), discrete optimization problems, and the like. Since the Monte Carlo method is a method for obtaining expected values by using asymptotic properties of random variables, the method has an advantage that the dependence on the nature of problems is relatively small to be applicable to a wide range of problems; on the other hand, the method has a disadvantage that the calculation time is relatively long because the convergence is slow.

#In order to compensate for the disadvantage that the calculation time of the Monte Carlo method is relatively long, it is considered that the algorithm of the method is implemented by hardware to be executed at high speed in parallel, but in this case, a large number of pseudo-random numbers are simultaneously generated in the hardware. In a case where the correlation between the pseudo-random numbers is strong, since the convergence of the expected value is deteriorated, it is desirable to efficiently generate a large number of pseudo-random numbers with a small correlation.

#Various kinds of pseudo-random numbers are present in accordance with probability distribution thereof. In the Monte Carlo method, mainly used are a uniform random number having the same probability, a normal random number having a normal distribution, an exponential random number having an exponential distribution, and the like in terms of values in a fixed section. It is relatively easy to efficiently generate a uniform random number by hardware. As a random number generation device configured to generate a uniform random number, a linear-feedback shift register (LFSR), Mersenne Twister extended from the LFSR, and the like are known. However, it is not easy to efficiently generate a normal random number and an exponential random number by hardware.