Linear congruential generator: Difference between revisions

=={{header|11l}}==

seed = 0

Int a, c, m

print(‘MS RAND:’)

L 5

{{out}}

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

=={{header|Batch}}==

@echo off & setlocal enabledelayedexpansion

goto:eof

'''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 sharp|C#}}==

{{works with|C sharp|C#|6+}}

<!-- By Martin Freedman, 17/01/2018 -->

using System.Collections.Generic;

using System.Linq;

}

}

Produces:

<pre>BSD next 10 Random

</pre>

From a Free Cell Deal solution

using System;

using System.Collections.Generic;

}

}

Output:

<pre>Microsoft

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

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

{{libheader| Winapi.Windows}}

{{Trans|C#}}

program Linear_congruential_generator;

end.

{{out}}

The task doesn't specify what random seed is to be used. This program uses 1, with results identical to those from the Elixir program.

[Linear congruential generators for pseudo-random numbers.

EDSAC program, Initial Orders 2.]

E 15 Z [define entry point]

P F [acc = 0 on entry]

{{out}}

<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()];;

=={{header|Factor}}==

{{works with|Factor|0.98}}

: lcg ( seed a c m quot: ( state -- rand ) -- list )

0 1103515245 12345 2147483648 [ ] lcg ! bsd

0 214013 2531011 2147483648 [ -16 shift ] lcg ! ms

{{out}}

<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

=={{header|FreeBASIC}}==

' compile with: fbc -s console

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>MS generator

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

Currently, jq arithmetic is based on IEEE 754 64-bit numbers. As a result, it is trivial to implement the Microsoft linear congruential generator (LCG), but the BSD generator requires some kind of "big integer" support. In this section, therefore, we first present functions to support the Microsoft LCG, and then present functions to support the LCG on the assumption that a suitable jq "BigInt" library is available.

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

function getlgc(r::Integer, a::Integer, c::Integer, m::Integer, sh::Integer)

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

=={{header|Mathematica}}/{{header|Wolfram Language}}==

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

var state = seed

result = iterator: int =

inc count

if count == 10:

{{out}}

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

{$mode iso}

var

writeln(bsdrand:12, msrand:12);

end.

Output:

<pre> BSD MS

=={{header|Perl}}==

package LCG;

print "\nMS:\n";

12345

1406932606

32285

10450

=={{header|Phix}}==

{{libheader|Phix/mpfr}}

As per the comments, I had to resort to gmp to get BSDrnd() to work on 32-bit.

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #004080;">atom</span> <span style="color: #000000;">seed</span>

<span style="color: #0000FF;">?</span><span style="color: #008000;">"MSrnd"</span>

<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">10</span> <span style="color: #008080;">do</span> <span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">MSrnd</span><span style="color: #0000FF;">())</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

{{out}}

<pre>

=={{header|PHP}}==

{{works with|PHP|5.3+}}

function bsd_rand($seed) {

return function() use (&$seed) {

echo $lcg(), " ";

echo "\n";

=={{header|Picat}}==

===Methods as hard coded predicates===

% BSD

Seed = cond(M.has_key(ms_state),M.get(ms_state),0),

Rand = ((214013*Seed + 2531011) mod 2**31),

{{out}}

===Generalized version===

Using a global global map for setting/setting seeds etc.

% BSD

Rand = ((M.get(multiplier)*M.get(seed) + M.get(adder)) mod M.get(mod)),

M.put(seed,Rand),

{{out}}

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

10 over size -

space swap of

10 times

[ BSD-rand echonum

{{out}}

=={{header|R}}==

rand_BSD <- function(n = 1) {

seed <- 0

rand_MS(10)

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

We'll define subroutines implementing the LCG algorithm for each version. We'll make them return a lazy list.

sub bsd {

$^seed, ( 1103515245 * * + 12345 ) % modulus ... *

say "\nMS LCG first 10 values (first one is the seed):";

<pre>BSD LCG first 10 values (first one is the seed):

=={{header|REXX}}==

/*──────── and MS random number generators: BSD= 0──►(2^31)-1 MS= 0──►(2^16)-1 */

numeric digits 20 /*use enough dec. digs for the multiply*/

" rand" right(ms % two@@16, 6)

end /*j*/

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

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

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_

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

{{incomplete|Scheme|Precise which Scheme implementation and version you are using and which Report on the Algorithmic Language

Scheme version it supports}}

(define ((msvcrt-rand seed)) (set! seed (remainder (+ (* 214013 seed) 2531011) 2147483648)) (quotient seed 65536))

(rand-list (msvcrt-rand 0) 10)

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

=={{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|Standard ML}}==

open Word32

in

(toInt (>> (state, 0w16)), state)

end

;Test code<nowiki>:</nowiki>

(print (" " ^ Int.toString rand); rand)

val () = print "\nMSC:\n"

val () = doTimes (test2 o mscLcg, 7, 0w0)

{{out}}

<pre>BSD:

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

=={{header|VBA}}==

Public stateMS As Variant

Private Function bsd() As Long

Debug.Print Format(bsd, "@@@@@@@@@@"), Format(ms, "@@@@@")

Next i

<pre> BSD MS

12345 38

{{libheader|Wren-fmt}}

Some of the intermediate calculations here require integers >= 2^53 so we need to use BigInt.

import "/fmt" for Fmt

example.call(0)

{{out}}

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>