Java程序实现线性同余生成器以生成伪随机数

---

线性同余生成器（LCG）是一种生成看似随机数序列的技术，但实际上这些数字是确定的。这也是将其称为伪随机数的原因之一。

线性同余生成器（LCG）技术基于前一个数字生成随机数，并使用线性递推来生成随机数序列。

我们可以使用以下LCG公式根据前一个数字生成随机数。

$$\mathrm{x_{n+1}=(mult\:x_{n}+\:increment\:mod\:modulus)}$$

在上式中，“mod”表示模运算。

• $\mathrm{x_{n+1}}$ - 要生成的下一个伪随机数。

• $\mathrm{x_{n}}$ - 前一个生成的随机数。

• Mult - 乘法常数。

• Increment - 加法常数。

• Modulus - 模运算的常数。

注意 - 我们应该选择常数的值，以便使用LCG算法生成合适的随机数。此外，我们需要一个“初始”数字，我们可以称之为种子值，来开始生成随机数序列。

这里，我们提供了一些示例。

示例

输入

initial = 32, modulas = 11, mult = 5, increment = 13, totalNums = 15

输出

32 8 9 3 6 10 8 9 3 6 10 8 9 3 6

说明 - 根据给定的公式，它生成了总共15个数字。

输入

initial = 100, modulas = 74, mult = 8, increment = 37, totalNums = 5

输出

   100 23 73 29 47

说明 - 这里，数字是在1到74的范围内生成的。并且看起来像是随机数。

方法1

在这种方法中，我们将使用上面解释的公式根据前一个生成的随机数生成随机数序列。

算法

步骤1 - 使用常数值初始化所有变量。同时，初始化“allRandoms”数组来存储随机数。

步骤2 - 执行generateRandom()函数。

步骤3 - 在generateRandom()函数中，使用初始数字初始化数组的第一个元素。

步骤4 - 之后，使用循环进行总共“totalNums”次的迭代。

步骤5 - 在循环的当前迭代中，将“((allRandoms[i - 1] * mult) + increment) % modulas”的值存储在allRandoms[i]位置。

步骤6 - 打印随机数。

示例

import java.util.*;
public class Main {
   static void generateRandom(int initial, int modulas, int mult, int 
increment, int[] allRandoms, int totalNums) {
      // Initial state of Linear Congruential Generator
      allRandoms[0] = initial;
      // Genereate sequence of random numbers
      for (int i = 1; i < totalNums; i++) {
         // linear congruential method
         allRandoms[i] = ((allRandoms[i - 1] * mult) + increment) % modulas;
      }
   }
   public static void main(String[] args) {
      // Initial value, and using that, we need to start generating a random number
      int initial = 32;
      // Integer for modulo operation
      int modulas = 11;
      // Integer for multiplier
      int mult = 5;
      // Integer to add
      int increment = 13;
      // count of random numbers to be generated
      int totalNums = 15;
      // array to store random numbers
      int[] allRandoms = new int[totalNums];
      generateRandom(initial, modulas, mult, increment, allRandoms, totalNums);
      // print numbers
      System.out.println("Random numbers generated are: ");
      for (int p = 0; p < totalNums; p++) {
         System.out.print(allRandoms[p] + " ");
      }
   }
}

输出

Random numbers generated are: 
32 8 9 3 6 10 8 9 3 6 10 8 9 3 6

时间复杂度 - O(N)，因为我们找到了N个随机数。

空间复杂度 - O(N)，因为我们存储了所有随机数。但是，如果我们不需要存储任何随机数，则可以将其优化为O(1)。

我们学习了线性同余生成器（LCG）算法来生成伪随机数，这是生成随机数序列的旧方法之一。程序员需要注意常数值以生成高质量的随机数。此外，模值可以帮助我们限制随机数的最大值，并且我们可以将限制值添加到生成的数字中以绑定最小值。