Método de congruencia multiplicativa para generar números pseudoaleatorios

El método congruencial multiplicativo (método de Lehmer) es un tipo de generador congruencial lineal para generar números pseudoaleatorios en un rango específico. Este método se puede definir como: 

 

donde, 
X , la secuencia de números pseudoaleatorios
m ( > 0), el módulo
a (0, m), el multiplicador
X ₀ [0, m), valor inicial de la secuencia – denominado semilla

 

m, a y X ₀ deben elegirse adecuadamente para obtener un período casi igual a m.

 

Acercarse: 

• Elija el valor inicial ( X ₀ ), el parámetro de módulo ( m ) y el término multiplicador ( a ).
• Inicialice la cantidad requerida de números aleatorios para generar (por ejemplo, una variable entera noOfRandomNums ).
• Defina el almacenamiento para mantener los números aleatorios generados (aquí, se considera el vector ) de tamaño noOfRandomNums .
• Inicialice el índice 0 del vector con el valor inicial ^.
• Para el resto de los índices, siga el método congruencial multiplicativo para generar los números aleatorios.

númerosaleatorios[i] = (númerosaleatorios[i – 1] * a) % m 

Finalmente, devuelva los números aleatorios.
A continuación se muestra la implementación del enfoque anterior:

// C++ implementation of the
// above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to generate random numbers
void multiplicativeCongruentialMethod(
    int Xo, int m, int a,
    vector<int>& randomNums,
    int noOfRandomNums)
{
 
    // Initialize the seed state
    randomNums[0] = Xo;
 
    // Traverse to generate required
    // numbers of random numbers
    for (int i = 1; i < noOfRandomNums; i++) {
 
        // Follow the multiplicative
        // congruential method
        randomNums[i]
            = (randomNums[i - 1] * a) % m;
    }
}
 
// Driver Code
int main()
{
    int Xo = 3; // seed value
    int m = 15; // modulus parameter
    int a = 7; // multiplier term
 
    // Number of Random numbers
    // to be generated
    int noOfRandomNums = 10;
 
    // To store random numbers
    vector<int> randomNums(noOfRandomNums);
 
    // Function Call
    multiplicativeCongruentialMethod(
        Xo, m, a, randomNums,
        noOfRandomNums);
 
    // Print the generated random numbers
    for (int i = 0; i < noOfRandomNums; i++) {
        cout << randomNums[i] << " ";
    }
    return 0;
}

// Java implementation of the above approach
import java.util.*;
 
class GFG{
 
// Function to generate random numbers
static void multiplicativeCongruentialMethod(
    int Xo, int m, int a,
    int[] randomNums,
    int noOfRandomNums)
{
     
    // Initialize the seed state
    randomNums[0] = Xo;
     
    // Traverse to generate required
    // numbers of random numbers
    for(int i = 1; i < noOfRandomNums; i++)
    {
         
        // Follow the multiplicative
        // congruential method
        randomNums[i] = (randomNums[i - 1] * a) % m;
    }
}
 
// Driver code
public static void main(String[] args)
{
     
    // Seed value
    int Xo = 3;
     
    // Modulus parameter
    int m = 15;
     
    // Multiplier term
    int a = 7;
     
    // Number of Random numbers
    // to be generated
    int noOfRandomNums = 10;
     
    // To store random numbers
    int[] randomNums = new int[noOfRandomNums];
     
    // Function Call
    multiplicativeCongruentialMethod(Xo, m, a,
                                     randomNums,
                                     noOfRandomNums);
     
    // Print the generated random numbers
    for(int i = 0; i < noOfRandomNums; i++)
    {
        System.out.print(randomNums[i] + " ");
    }
}
}
 
// This code is contributed by offbeat

# Python3 implementation of the
# above approach
 
# Function to generate random numbers
def multiplicativeCongruentialMethod(Xo, m, a,
                                     randomNums,
                                     noOfRandomNums):
 
    # Initialize the seed state
    randomNums[0] = Xo
 
    # Traverse to generate required
    # numbers of random numbers
    for i in range(1, noOfRandomNums):
         
        # Follow the linear congruential method
        randomNums[i] = (randomNums[i - 1] * a) % m
 
# Driver Code
if __name__ == '__main__':
     
    # Seed value
    Xo = 3
     
    # Modulus parameter
    m = 15
     
    # Multiplier term
    a = 7
 
    # Number of Random numbers
    # to be generated
    noOfRandomNums = 10
 
    # To store random numbers
    randomNums = [0] * (noOfRandomNums)
 
    # Function Call
    multiplicativeCongruentialMethod(Xo, m, a,
                                     randomNums,
                                     noOfRandomNums)
 
    # Print the generated random numbers
    for i in randomNums:
        print(i, end = " ")
 
# This code is contributed by mohit kumar 29

// C# implementation of the above approach
using System;
 
class GFG{
 
// Function to generate random numbers
static void multiplicativeCongruentialMethod(
    int Xo, int m, int a,
    int[] randomNums,
    int noOfRandomNums)
{
     
    // Initialize the seed state
    randomNums[0] = Xo;
     
    // Traverse to generate required
    // numbers of random numbers
    for(int i = 1; i < noOfRandomNums; i++)
    {
         
        // Follow the multiplicative
        // congruential method
        randomNums[i] = (randomNums[i - 1] * a) % m;
    }
}
 
// Driver code
public static void Main(String[] args)
{
     
    // Seed value
    int Xo = 3;
     
    // Modulus parameter
    int m = 15;
     
    // Multiplier term
    int a = 7;
     
    // Number of Random numbers
    // to be generated
    int noOfRandomNums = 10;
     
    // To store random numbers
    int[] randomNums = new int[noOfRandomNums];
     
    // Function call
    multiplicativeCongruentialMethod(Xo, m, a,
                                     randomNums,
                                     noOfRandomNums);
     
    // Print the generated random numbers
    for(int i = 0; i < noOfRandomNums; i++)
    {
        Console.Write(randomNums[i] + " ");
    }
}
}
 
// This code is contributed by sapnasingh4991

<script>
 
// Javascript program to implement
// the above approach
 
// Function to generate random numbers
function multiplicativeCongruentialMethod(
    Xo, m, a,
    randomNums, noOfRandomNums)
{
       
    // Initialize the seed state
    randomNums[0] = Xo;
       
    // Traverse to generate required
    // numbers of random numbers
    for(let i = 1; i < noOfRandomNums; i++)
    {
           
        // Follow the multiplicative
        // congruential method
        randomNums[i] = (randomNums[i - 1] * a) % m;
    }
}
 
    // Driver Code
           
    // Seed value
    let Xo = 3;
       
    // Modulus parameter
    let m = 15;
       
    // Multiplier term
    let a = 7;
       
    // Number of Random numbers
    // to be generated
    let noOfRandomNums = 10;
       
    // To store random numbers
    let randomNums = new Array(noOfRandomNums).fill(0);
       
    // Function Call
    multiplicativeCongruentialMethod(Xo, m, a,
                                     randomNums,
                                     noOfRandomNums);
       
    // Print the generated random numbers
    for(let i = 0; i < noOfRandomNums; i++)
    {
        document.write(randomNums[i] + " ");
    }
 
</script>

3 6 12 9 3 6 12 9 3 6

Complejidad temporal: O(N), donde N es el número total de números aleatorios que necesitamos generar.
Espacio auxiliar : O(1)
El significado literal de pseudo es falso . Estos números aleatorios se llaman pseudo porque se utiliza algún procedimiento aritmético conocido para generar. Incluso la secuencia generada forma un patrón, por lo que el número generado parece ser aleatorio, pero puede que no sea verdaderamente aleatorio .