The linear congruential generator is a very simple example of a random number generator.

All linear congruential generators use this formula:

 




r

n
+
1


=
a
×

r

n


+
c


(
mod

m
)



{\displaystyle r_{n+1}=a\times r_{n}+c{\pmod {m}}}




Where:

 




r

0




{\displaystyle r_{0}}

 is a seed.
 




r

1




{\displaystyle r_{1}}

, 




r

2




{\displaystyle r_{2}}

, 




r

3




{\displaystyle r_{3}}

, ..., are the random numbers.
 



a


{\displaystyle a}

, 



c


{\displaystyle c}

, 



m


{\displaystyle m}

 are constants.


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.



BSD formula

 



s
t
a
t

e

n
+
1


=
1103515245
×
s
t
a
t

e

n


+
12345


(
mod


2

31


)



{\displaystyle state_{n+1}=1103515245\times state_{n}+12345{\pmod {2^{31}}}}


 



r
a
n

d

n


=
s
t
a
t

e

n




{\displaystyle rand_{n}=state_{n}}


 



r
a
n

d

n




{\displaystyle rand_{n}}

 is in range 0 to 2147483647.


Microsoft formula

 



s
t
a
t

e

n
+
1


=
214013
×
s
t
a
t

e

n


+
2531011


(
mod


2

31


)



{\displaystyle state_{n+1}=214013\times state_{n}+2531011{\pmod {2^{31}}}}


 



r
a
n

d

n


=
s
t
a
t

e

n


÷

2

16




{\displaystyle rand_{n}=state_{n}\div 2^{16}}


 



r
a
n

d

n




{\displaystyle rand_{n}}

 is in range 0 to 32767.


The BSD formula was so awful that FreeBSD switched to a different formula.

More info is at Random number generator (included)#C.




;x86-64 assembly code for Microsoft Windows
;Tested in windows 7 Enterprise Service Pack 1 64 bit
;With the AMD FX(tm)-6300 processor
;Assembled with NASM version 2.11.06 
;Linked to C library with gcc version 4.9.2 (x86_64-win32-seh-rev1, Built by MinGW-W64 project)
 
;Assembled and linked with the following commands:
;nasm -f win64 <filename>.asm -o <filename>.obj
;gcc <filename>.obj -o <filename>
 
;Takes number of iterations to run RNG loop as command line parameter.
 
extern printf,puts,atoi,exit,time,malloc
 
section .data
align 64
errmsg_argnumber: db "There should be no more than one argument.",0
align 64
errmsg_noarg: db "Number of iterations was not specified.",0
align 64
errmsg_zeroiterations: db "Zero iterations of RNG loop specified.",0
 
align 64
errmsg_timefail: db "Unable to retrieve calender time.",0
align 64
errmsg_mallocfail: db "Unable to allocate memory for array of random numbers.",0
 
align 64
fmt_random: db "The %u number generated is %d",0xa,0xd,0
 
section .bss
 
section .text
global main
 
main:
 
;check for argument
cmp rcx,1
jle err_noarg
 
;ensure that only one argument was entered
cmp rcx,2
jg err_argnumber
 
 
;get number of times to iterate get_random
mov rcx,[rdx + 8]
call atoi
 
 
;ensure that number of iterations is greater than 0
cmp rax,0
jle err_zeroiterations
mov rcx,rax
 
 
;calculate space needed for an array containing the random numbers
shl rcx,2
 
;move size of array into r14
mov r14,rcx
 
;reserve memory for array of random numbers with malloc
call malloc
 
cmp rax,0
jz err_mallocfail
 
;pointer to array in r15
mov r15,rax
 
 
;seed the RNG using time()
xor rcx,rcx
call time
 
;ensure that time returns valid output
cmp rax,-1
jz err_timefail
 
;calculate address of end of array in r14
add r14,r15
 
 
;pointer to array of random numbers in r15
;address of end of array in r14
;current address in array in rdi
;multiplier in rbx
;seed in rax
;current random number in rcx
 
 
;prepare random number generator
 
mov rdi,r15
 
mov rbx,214013
 
 
get_random:
 
;multiply by 214013 and add 2561011 to get next state
mul ebx
add eax,2531011
 
;shr by 16 and AND with 0x7FFF to get current random number
mov ecx,eax
shr ecx,16
and ecx,0x7fff
 
;store random number in array
mov [rdi],ecx
 
add rdi,4
cmp rdi,r14
jl get_random
 
 
;pointer to array of random numbers in r15
;address of end of array in r14
;current address in array in rdi
;array index in rsi
 
 
xor rsi,rsi
mov rdi,r15
 
print_random:
 
mov rcx,fmt_random
mov rdx,rsi
mov r8d,[rdi]
call printf
 
add rsi,1
add rdi,4
cmp rdi,r14
jl print_random
 
xor rcx,rcx
call exit
 
 
;;;;;;;;;;ERROR MESSAGES;;;;;;;;;;;;;;;;
 
err_argnumber:
 
mov rcx,errmsg_argnumber
call puts
 
jmp exit_one
 
 
err_noarg:
 
mov rcx,errmsg_noarg
call puts
 
jmp exit_one
 
 
err_zeroiterations:
 
mov rcx,errmsg_zeroiterations
call puts
 
jmp exit_one
 
 
err_timefail:
 
mov rcx,errmsg_timefail
call puts
 
jmp exit_one
 
 
err_mallocfail:
 
mov rcx,errmsg_mallocfail
call puts
 
 
exit_one:
 
mov rcx,1
call exit