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|360 Assembly}}==

LINCONG CSECT

USING LINCONG,R12

XDEC DS CL12

YREGS

{{out}}

<pre>

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):

 

=={{header|ALGOL 68}}==

BEGIN

COMMENT

srand (0)

END

{{out}}

<pre>

 

=={{header|AutoHotkey}}==

Loop, 10

BSD .= "`t" (a := BSD(a)) "`n"

Seed := Mod(214013 * Seed + 2531011, 2147483648)

return, [Seed, Seed // 65536]

'''Output:'''

<pre>BSD:

30612</pre>

 

 

echo BSD Rand

set p2= %2

echo %p1:~-2% %p2:~-10%

'''Output:'''

<pre>

=={{header|BBC BASIC}}==

{{works with|BBC BASIC for Windows}}

PRINT "MS generator:"

dummy% = FNrandMS(0)

DEF FNmuladd(A%,B%,C%) : PRIVATE M% : LOCAL P% : IF M% = 0 DIM P% 8

IF P% THEN [OPT 0 : .M% mul ebx : add eax,ecx : btr eax,31 : ret :]

'''Output:'''

<pre>

 

As with dc, bc has no bitwise operators.

 

define rand() {

 

randseed = 1

 

=={{header|Befunge}}==

This required a bit of trickery to handle signed overflow and negative division in a portable way. It still won't work on all implementations, though. In particular Javascript-based interpreters can't handle the BSD formula because of the way Javascript numbers lose their least significant digits when they become too large.

 

v $$_^#!\-1:\%***:*::*882 ++*"yf"3***+***+*<

>025*>\:488**:*/:0\`6"~7"+:*+01-2/-*+."O?+"55v

 

{{out}}

 

=={{header|Bracmat}}==

& 2^-16:?rshift

& (randBSD=mod$(!seed*1103515245+12345.!RANDMAX):?seed)

& 0:?i

& whl'(1+!i:~>10:?i&out$!randMS)

 

Output:

=={{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;

 

=={{header|C++}}==

 

//--------------------------------------------------------------------------------------------------

return 0;

}

Output:

<pre>

; C++11

{{works with|C++11}}

#include <random>

 

return 0;

Output:

<pre>

=={{header|Clojure}}==

 

 

(defn iterator [a b]

(take 10 ms) ;-> (38 7719 21238 2437 8855 11797 8365 32285 10450 30612)

 

 

=={{header|Common Lisp}}==

"returns an RNG according to :seed and :mode keywords

default mode: bsd

 

(let ((rng (make-rng :mode 'ms :seed 1)))

 

 

Another solution could be:

(loop for candidate = seed then (mod (+ (* multiplier candidate) adder) bounds)

for result = candidate then (floor (/ candidate divisor))

when (and (< result max) (> result min)) collect result into valid-numbers

 

Which defaults to the BSD formula, but can be customized to any formula with keyword arguments, for example:

(loop for i from 0 upto 5 collect

(list i

(linear-random 0 :times i)

 

Outputs:

4 229283573 8855

5 1109335178 11797</pre>

 

=={{header|D}}==

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

uint seed = 0;

foreach (immutable i; 0 .. 10)

writeln(rnd.randMS);

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|Elixir}}==

def ms_seed(seed) do

Process.put(:ms_state, seed)

:io.format "~11w~8w~n", [LCG.bsd_rand, LCG.ms_rand]

end)

 

{{out}}

=={{header|Erlang}}==

{{trans|Elixir}}

-export([bsd_seed/1, ms_seed/1, bsd_rand/0, ms_rand/0]).

 

ms_seed(0),

io:fwrite("~10s~c~5s~n", ["BSD", 9, "MS"]),

 

{{Out}}

=={{header|ERRE}}==

ERRE doesn't generate the proper output from the BSD constants; it uses double-precision floating point, which is not enough for some of the intermediate products: for exact computation you can use MULPREC program. The BSD series deviates starting with the third value (see sample output below).

 

!$DOUBLE

PRINT(TAB(10);XRND)

END FOR

{{out}}

<pre>

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

 

let bsd seed =

let state = ref seed

state := (214013 * !state + 2531011) &&& System.Int32.MaxValue

!state / (1<<<16))

<pre>let rndBSD = lcg.bsd 0;;

let BSD=[for n in [0 .. 9] -> rndBSD()];;

val MS : int list =

[38; 7719; 21238; 2437; 8855; 11797; 8365; 32285; 10450; 30612]</pre>

 

=={{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|FreeBASIC}}==

' compile with: fbc -s console

 

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>MS generator

794471793

551188310</pre>

 

=={{header|Go}}==

 

import "fmt"

example(0)

example(1)

Output:

<pre>

 

=={{header|Haskell}}==

msr = map (`div` 2^16) . tail . iterate (\n -> (214013 * n + 2531011) `mod` 2^31)

 

main = do

print $ take 10 $ bsd 0 -- can take seeds other than 0, of course

 

=={{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:'''

0 m lcg y NB. default seed of 0

:

 

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

'''Example Use:'''

12345 1406932606 654583775 1449466924 229283573 1109335178 1051550459 1293799192 794471793 551188310

654583775 rand_bsd 4

38 7719 21238 2437 8855 11797 8365 32285 10450 30612

1 rand_ms 5 NB. seed of 1

 

=={{header|Java}}==

{{works with|Java|8}}

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

 

.map(i -> i >> 16);

}

 

<pre>BSD:

 

=={{header|jq}}==

====Microsoft LCG====

# from the Microsoft C Runtime.

# Input: [ count, state, rand ]

| next_rand_Microsoft # the seed is not so random

| recurse(if .[0] < n then next_rand_Microsoft else empty end)

'''Example''':

rand_Microsoft(1;5)

{{out}}

18467

6334

26500

====BSD LCG====

The following code has been tested with the "BigInt" library at [https://gist.github.com/pkoppstein/d06a123f30c033195841].

# Input: [count, previous]

def next_rand_berkeley:

| next_rand_berkeley # skip the seed itself

| recurse(if .[0] < n then next_rand_berkeley else empty end)

'''Example''':

rand_berkeley(1;5)

{{out}}

377401575

662824084

1147902781

 

=={{header|Julia}}==

<tt>getlgc</tt> creates a linear congruential generator as a closure. This function is used to create the two generators called for by the task.

state = r

return function lgcrand()

for _ in 1:nrep

@printf("%14d\n", msrand())

 

{{out}}

 

=={{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|Kotlin}}==

 

class Lcg(val a: Long, val c: Long, val m: Long, val d: Long, val s: Long) {

val msc = Lcg(214013, 2531011, 1 shl 31, 1 shl 16, 0)

for (i in 1..10) println("${msc.nextInt()}")

 

{{out}}

 

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

'by default these are 0

global BSDState

randMS = int(MSState / 2 ^ 16)

end function

 

=={{header|Logo}}==

Note that, perhaps ironically, [[UCB Logo]], as of version 6.0, doesn't generate the proper output from the BSD constants; it uses double-precision floating point, which is not enough for some of the intermediate products. In UCBLogo, the BSD series deviates starting with the third value (see sample output below).

 

make "LCG_MS [214013 2531011 65536 2147483648]

make "LCG_BSD [1103515245 12345 1 2147483648]

print []

]

 

Output:<pre>12345

This requires Lua 5.3 or later because previous versions didn't have support for large integers or integral arithmetic operations.

 

new = function(class, a, c, m, rand)

local self = setmetatable({}, class)

print(("\t%10d"):format(ms.rnd()))

end

 

{{Out}}

</pre>

 

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|Maxima}}==

ms_rand() := quotient(seed: mod(214013 * seed + 2531011, 2147483648), 65536)$

makelist(ms_rand(), 20); /* see http://oeis.org/A096558 */

[12345, 1406932606, 654583775, 1449466924, 229283573, 1109335178, 1051550459,

1293799192, 794471793, 551188310, 803550167, 1772930244, 370913197, 639546082, 1381971571,

 

=={{header|Nim}}==

result = iterator: int =

while true:

 

proc msvcrtRand(seed: int): iterator: int =

result = iterator: int =

while true:

 

=={{header|Oforth}}==

Function genLCG returns a block object that, when performed, will return the next random number from the LCG.

 

| ch |

Channel newSize(1) dup send(seed) drop ->ch

 

{{out}}

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

Note that up to PARI/GP version 2.4.0, <code>random()</code> used a linear congruential generator.

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

 

=={{header|Phix}}==

{{out}}

<pre>

=={{header|PHP}}==

{{works with|PHP|5.3+}}

function bsd_rand($seed) {

return function() use (&$seed) {

echo $lcg(), " ";

echo "\n";

 

=={{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>

 

=={{header|PowerShell}}==

Function msstate{

Param($current_seed)

$seed = randBSD($seed)

Write-Host $seed}

 

{{Out}}

 

=={{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

{{works with|Python|3.x}}

def rand():

nonlocal seed

seed = (214013*seed + 2531011) & 0x7fffffff

return seed >> 16

 

=={{header|Racket}}==

The following solution uses generators and transcribes the mathematical formulas above directly. It does not attempt to be efficient.

 

#lang racket

(require racket/generator)

(define bsd-rand (rand bsd-update identity))

(define ms-rand (rand ms-update (λ (x) (quotient x (expt 2 16)))))

 

=={{header|REXX}}==

 

/* [↓] show 20 rand #'s for each seed.*/

{{out|output|text= &nbsp; &nbsp; (shown at five-sixth size.) }}

<pre style="font-size:84%">

state 1 BSD 12345 MS 2531011 rand 38

state 2 BSD 1406932606 MS 505908858 rand 7719

state 19 BSD 996984527 MS 196417061 rand 2997

state 20 BSD 1157490780 MS 962080852 rand 14680

state 1 BSD 1103527590 MS 2745024 rand 41

state 2 BSD 377401575 MS 1210316419 rand 18467

state 19 BSD 1647418052 MS 316395082 rand 4827

state 20 BSD 1675546029 MS 356309989 rand 5436

</pre>

 

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|Run BASIC}}==

global ms

print "Num ___Bsd___";chr$(9);"__Ms_"

ms = (214013 * ms + 2531011) mod (2 ^ 31)

msRnd = int(ms / 2 ^ 16)

<pre>

Num ___Bsd___ __Ms_

9 794471793 10450

10 551188310 30612</pre>

 

=={{header|Rust}}==

 

pub use rand::{Rng, SeedableRng};

println!("{}", ms.gen::<bool>());

println!("{}", ms.gen_ascii_chars().take(15).collect::<String>());

 

=={{header|Scala}}==

def bsdRandom(rseed:Int):Iterator[Int]=new Iterator[Int]{

var seed=rseed

println("MS : "+ toString( msRandom(1)))

}

{{out}}

<pre>-- seed 0 --

 

=={{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|Seed7}}==

[http://seed7.sourceforge.net/libraries/array.htm#rand%28in_arrayType%29 rand(arr)]. This function selects a random element from an array.

 

include "bigint.s7i";

 

writeln(bsdRand lpad 12 <& msRand lpad 12);

end for;

 

Output:

Uses the Random library provided by SequenceL to create new Random Number Generators

 

import <Utilities/Random.sl>;

 

(Value : newSeed / 65536,

Generator : (Seed : newSeed, RandomMin : RG.RandomMin, RandomMax : RG.RandomMax, NextFunction : RG.NextFunction));

Output

<pre>

MS Values: [38,7719,21238,2437,8855,11797,8365,32285,10450,30612]

</pre>

=={{header|Sidef}}==

{{trans|Ruby}}

 

# Creates a linear congruential generator and remembers the initial seed.

 

var lcg2 = LCG::Microsoft(1)

{{out}}

<pre>

 

=={{header|Sparkling}}==

"BSD": 0,

"MS": 0

function Microsoft_rand() {

return (states.MS = (214013 * states.MS + 2531011) % (1 << 31)) % (1 << 15);

 

Output seen after seeding both generators with 0:

 

spn:9> Microsoft_rand()

= 7875

= 1449466924

spn:19> BSD_rand()

 

=={{header|Stata}}==

 

function rand_bsd(u) {

m = 65536

 

rand_seq(&rand_bsd(),1,10)

 

'''Output''': compare with OEIS '''[http://oeis.org/A096553 A096553]''' and '''[http://oeis.org/A096558 A096558]'''.

=={{header|Swift}}==

 

 

class LinearCongruntialGenerator {

{

print(BSDLinearCongruntialGenerator.random())

{{out}}<pre>Microsft Rand:

38

=={{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>

=={{header|uBasic/4tH}}==

uBasic is an integer BASIC without any bitwise operations. That's why a trick is used when it enters the negative domain. Unfortunately, it is not portable and must be adjusted for different integer widths. This 32-bit version produces the proper result, though.

b = 0 ' Initial BSD seed

m = 0 ' Initial MS seed

m = Pop() % (2 ^ 31) ' Now we got a number less than 2^31

Push m / (2 ^ 16) ' So we can complete the operation

{{out}}

<pre>BSD

=={{header|UNIX Shell}}==

 

 

function BSD() {

 

output BSD

 

{{out}}

30612

 

</pre>

 

 

First example using integer instructions.

;Tested in windows 7 Enterprise Service Pack 1 64 bit

;With the AMD FX(tm)-6300 processor

 

mov rcx,1

 

Second example using AVX instructions.

{{incorrect|X86 Assembly|It will not produce output identical to that of the Microsoft rand() function.}}

;Tested in windows 7 Enterprise Service Pack 1 64 bit

;With the AMD FX(tm)-6300 processor

 

mov rcx,1

 

{{out|Sample}}

[[File:LCG2XPL0.gif|right]]

 

int R;

 

N:= ChIn(1); \wait for keystoke

SetVid(3); \restore normal text mode

 

=={{header|zkl}}==

fcn srand(s){ seed = s }

 

const A=214013, C=2531011, TWO16=(1).shiftLeft(16);

fcn rand{ (seed = (seed * A + C) % TWO31) / TWO16 }

{{out}}

<pre>