How to resolve the algorithm Linear congruential generator step by step in the Java programming language

Published on 12 May 2024 09:40 PM
#Java

How to resolve the algorithm Linear congruential generator step by step in the Java programming language

Table of Contents

Problem Statement

The linear congruential generator is a very simple example of a random number generator. All linear congruential generators use this formula:

Where:

If one chooses the values of

a

{\displaystyle a}

,

c

{\displaystyle c}

and

m

{\displaystyle m}

with care, then the generator produces a uniform distribution of integers from

0

{\displaystyle 0}

to

m − 1

{\displaystyle m-1}

. LCG numbers have poor quality.

r

n

{\displaystyle r_{n}}

and

r

n + 1

{\displaystyle r_{n+1}}

are not independent, as true random numbers would be. Anyone who knows

r

n

{\displaystyle r_{n}}

can predict

r

n + 1

{\displaystyle r_{n+1}}

, therefore LCG is not cryptographically secure. The LCG is still good enough for simple tasks like Miller-Rabin primality test, or FreeCell deals. Among the benefits of the LCG, one can easily reproduce a sequence of numbers, from the same

r

0

{\displaystyle r_{0}}

. One can also reproduce such sequence with a different programming language, because the formula is so simple. The task is to replicate two historic random number generators. One is the rand() function from BSD libc, and the other is the rand() function from the Microsoft C Runtime (MSCVRT.DLL). Each replica must yield the same sequence of integers as the original generator, when starting from the same seed. In these formulas, the seed becomes

s t a t

e

0

{\displaystyle state_{0}}

. The random sequence is

r a n

d

1

{\displaystyle rand_{1}}

,

r a n

d

2

{\displaystyle rand_{2}}

and so on.

The BSD formula was so awful that FreeBSD switched to a different formula. More info is at Random number generator (included)#C.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Linear congruential generator step by step in the Java programming language

Linear Congruential Generators (LCGs)

Linear Congruential Generators (LCGs) are a type of pseudorandom number generator that is defined by the following recurrence relation:

X[n+1] = (a * X[n] + c) mod m

where:

  • X[n] is the current state of the generator
  • X[n+1] is the next state of the generator
  • a is the multiplier
  • c is the increment
  • m is the modulus

Source Code Overview

The provided Java code defines two LCGs, one for the BSD operating system and one for the MS operating system.

BSD LCG

The BSD LCG is defined by the following parameters:

  • a = 1,103,515,245
  • c = 12,345
  • m = 2^31 - 1

The randBSD method initializes the LCG with a given seed and returns an IntStream that generates a sequence of random numbers.

MS LCG

The MS LCG is defined by the following parameters:

  • a = 214,013
  • c = 2,531,011
  • m = 2^31 - 1

The randMS method initializes the LCG with a given seed and returns an IntStream that generates a sequence of random numbers. Additionally, the MS LCG performs a right shift of 16 bits on each generated number.

Main Method

The main method creates two IntStreams for each LCG and limits the output to the first 10 random numbers.

Output

The output of the program is as follows:

BSD:
-1013911710
-2043182885
-1733331755
1800172871
-935474200
-1838629527
-783760301
-1352769937
1321303975
29320538

MS:
41175297
48472935
45410267
37387933
14656175
53150325
17590749
31837485
48936739
41938477

Note:

The LCGs used in this code are simple examples and are not suitable for cryptographic purposes. For secure applications, it is recommended to use more sophisticated random number generators, such as Mersenne Twister or Xorshift.

Source code in the java programming language

import java.util.stream.IntStream;
import static java.util.stream.IntStream.iterate;

public class LinearCongruentialGenerator {
    final static int mask = (1 << 31) - 1;

    public static void main(String[] args) {
        System.out.println("BSD:");
        randBSD(0).limit(10).forEach(System.out::println);

        System.out.println("\nMS:");
        randMS(0).limit(10).forEach(System.out::println);
    }

    static IntStream randBSD(int seed) {
        return iterate(seed, s -> (s * 1_103_515_245 + 12_345) & mask).skip(1);
    }

    static IntStream randMS(int seed) {
        return iterate(seed, s -> (s * 214_013 + 2_531_011) & mask).skip(1)
                .map(i -> i >> 16);
    }
}

You may also check:How to resolve the algorithm File size step by step in the PHP programming language
You may also check:How to resolve the algorithm RSA code step by step in the Python programming language
You may also check:How to resolve the algorithm JSON step by step in the Bracmat programming language
You may also check:How to resolve the algorithm Hofstadter Q sequence step by step in the ARM Assembly programming language
You may also check:How to resolve the algorithm Non-decimal radices/Convert step by step in the Action! programming language