Linear congruential generator: Difference between revisions

{{task|Randomness}}

 

* <math>r_{n + 1} = a \times r_n + c \pmod m</math>

 

 

* <math>r_0</math> is a seed.

* <math>r_1</math>, <math>r_2</math>, <math>r_3</math>, ..., are the random numbers.

* <math>a</math>, <math>c</math>, <math>m</math> are constants.

 

If one chooses the values of <math>a</math>, <math>c</math> and <math>m</math> with care, then the generator produces a uniform distribution of integers from <math>0</math> to <math>m - 1</math>.

In these formulas, the seed becomes <math>state_0</math>. The random sequence is <math>rand_1</math>, <math>rand_2</math> and so on.

 

 

* <math>state_{n + 1} = 1103515245 \times state_n + 12345 \pmod{2^{31}}</math>

* <math>rand_n = state_n</math>

* <math>rand_n</math> is in range 0 to 2147483647.

 

 

* <math>state_{n + 1} = 214013 \times state_n + 2531011 \pmod{2^{31}}</math>

* <math>rand_n = state_n \div 2^{16}</math>

* <math>rand_n</math> is in range 0 to 32767.

 

 

=={{header|Ada}}==

We first specify a generic package LCG:

 

type Base_Type is mod <>;

Multiplyer, Adder: Base_Type;

-- changes the state and outputs the result

 

 

Then we provide a generic implementation:

 

 

State: Base_Type := Base_Type'First;

end Random;

 

 

Next, we define the MS- and BSD-instantiations of the generic package:

 

 

procedure Run_LCGs is

Ada.Text_IO.Put_Line(M31'Image(MS_Rand.Random));

end loop;

 

Finally, we run the program, which generates the following output (note that the first ten lines are from the BSD generator, the next ten from the MS generator):

10450

30612</pre>

 

=={{header|bc}}==

 

As with dc, bc has no bitwise operators.

 

define rand() {

 

randseed = 1

 

=={{header|C}}==

In a pretended lib style, this code produces a rand() function depends on compiler macro: <code>gcc -DMS_RAND</code> uses MS style, otherwise it's BSD rand by default.

 

/* always assuming int is at least 32 bits */

 

return 0;

 

 

 

using System;

using System.Collections.Generic;

}

}

Output:

<pre>Microsoft

551188310

</pre>

 

enum uint RAND_MAX = (1U << 31) - 1;

uint seed = 0;

 

seed = (seed * 1_103_515_245 + 12_345) & RAND_MAX;

return seed;

}

 

seed = (seed * 214_013 + 2_531_011) & RAND_MAX;

return seed >> 16;

 

void main() {

LinearCongruentialGenerator rnd;

 

 

rnd.seed = 0;

Output:

<pre>12345

''dc'' has no bitwise operations, so this program uses the modulus operator (<code>2147483648 %</code>) and division (<code>65536 /</code>). Fortunately, ''dc'' numbers cannot overflow to negative, so the modulus calculation involves only non-negative integers.

 

* lrx -- (random number from 0 to 2147483647)

*

[* Set seed to 1, then print the first 3 random numbers. *]sz

1 sR

 

<pre>1103527590

662824084</pre>

 

* lrx -- (random number from 0 to 32767)

*

[* Set seed to 1, then print the first 3 random numbers. *]sz

1 sR

 

<pre>41

18467

6334</pre>

 

=={{header|F_Sharp|F#}}==

 

let bsd seed =

let state = ref seed

(fun (_:unit) ->

!state)

let ms seed =

let state = ref seed

(fun (_:unit) ->

!state / (1<<<16))

 

=={{header|Forth}}==

1 15 lshift 1- constant MAX-RAND-MS

 

;

 

 

Output:

=={{header|Fortran}}==

{{works with|Fortran|90 and later}}

implicit none

 

write(*, "(2i12)") bsdrand(), msrand()

end do

Output

<pre> BSD MS

794471793 10450

551188310 30612</pre>

=={{header|Go}}==

 

import "fmt"

example(0)

example(1)

Output:

<pre>

2035015474 19169

</pre>

 

=={{header|Icon}} and {{header|Unicon}}==

The following LCRNG's behave in the same way maintaining the state (seed) from round to round. There is an srand procedure for each lcrng that maintains the seed state and allows the user to assign a new state.

 

procedure main()

procedure rand_MS() #: lcrng

return ishift(srand_MS((214013 * srand_MS() + 2531011) % 2147483648),-16)

 

{{libheader|Icon Programming Library}}

=={{header|J}}==

'''Solution:'''

:

}. (mod | c + a * ])^:(<y+1) x

)

 

rand_bsd=: (1103515245 12345 , <.2^31) lcg

'''Example Use:'''

12345 1406932606 654583775 1449466924 229283573 1109335178 1051550459 1293799192 794471793 551188310

654583775 rand_bsd 4

1449466924 229283573 1109335178 1051550459

rand_ms 10

 

=={{header|K}}==

ms:{1_(y{_(((214013*x)+2531011)!(_2^31))}\x)%(_2^16)}

 

12345 1406932606 654583775 1449466924 229283573 1109335178 1051550459 1293799192 794471793 551188310

ms[0;10]

 

=={{header|Liberty BASIC}}==

'by default these are 0

global BSDState

randMS = int(MSState / 2 ^ 16)

end function

 

NestList[BSDrand, 0, 10]

-> {0, 12345, 1406932606, 654583775, 1449466924, 229283573, 1109335178, 1051550459, 1293799192, 794471793, 551188310}

MSrand[x_] := Mod[x*214013 + 2531011, 2147483648]

BitShiftRight[ NestList[MSrand, 0, 10], 16]

 

=={{header|PARI/GP}}==

MSFTseed=Mod(1,1<<31);

BSD()=BSDseed=1103515245*BSDseed+12345;lift(BSDseed);

 

=={{header|Pascal}}==

var

x1, x2: int64;

const

a = 1103515245;

bsdrand := x1;

end;

const

a = 214013;

msrand := x2 div 65536;

end;

var

begin

writeln(' BSD MS');

for i := 1 to 10 do

writeln(bsdrand:12, msrand:12);

Output:

<pre> BSD MS

 

=={{header|Perl}}==

package LCG;

 

 

print "\nMS:\n";

12345

1406932606

32285

10450

 

<pre>

12345

1406932606

794471793

551188310

38

7719

30612

</pre>

 

=={{header|PicoLisp}}==

 

(de bsdRand ()

(>> 16

(setq *MsSeed

Output:

<pre>: (do 7 (printsp (bsdRand)))

 

=={{header|PL/I}}==

(nofixedoverflow, nosize):

LCG: procedure options (main);

 

end LCG;

OUTPUT:

<pre>

308566760 7038

534615297 21512

</pre>

 

=={{header|PureBasic}}==

Static state.q

If seed >= 0

Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()

CloseConsole()

Sample output:

<pre>BSD (seed = 1)

 

=={{header|Python}}==

def rand():

rand.seed = (1103515245*rand.seed + 12345) & 0x7fffffff

return rand.seed >> 16

rand.seed = seed

 

=={{header|Ruby}}==

You can create multiple instances of LCG::Berkeley or LCG::Microsoft. Each instance privately keeps the original seed in @seed, and the current state in @r. Each class resembles the core Random class, but with fewer features. The .new method takes a seed. The #rand method returns the next random number. The #seed method returns the original seed.

 

module Common

# The original seed of this generator.

end

end

 

The next example sets the seed to 1, and prints the first 5 random numbers.

 

p (1..5).map {lcg.rand}

# prints [1103527590, 377401575, 662824084, 1147902781, 2035015474]

lcg = LCG::Microsoft.new(1)

p (1..5).map {lcg.rand}

 

=={{header|Scheme}}==

 

 

; auxiliary function to get a list of 'n random numbers from generator 'r

 

; (12345 1406932606 654583775 1449466924 229283573 1109335178 1051550459 1293799192 794471793 551188310)

 

 

=={{header|Tcl}}==

Using an object-oriented solution, inspired by (but not a translation of) the [[#Ruby|Ruby]] solution above.

 

# General form of a linear-congruential RNG

next $initialSeed 214013 2531011 [expr {2**31}] [expr {2**16}]

}

Demo code:

puts BSD:\t\[[sample [BSDRNG new 1]]\]

Output:

<pre>

BSD: [1103527590, 377401575, 662824084, 1147902781, 2035015474]

MS: [41, 18467, 6334, 26500, 19169]

</pre>