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）演算法來生成偽隨機數，這是生成隨機數序列的舊方法之一。程式設計師需要注意常數值以生成高質量的隨機數。此外，模值可以幫助我們限制隨機數的最大值，並且我們可以將限制值新增到生成的數字中以繫結最小值。