How does a random number generator work?

How do random number generator works? (for example in C/C++ Java)

H开发者_StackOverflow社区ow can I write my own random number generator? (for example in C/C++ Java)

There is also this algorithm:

Oh, and more seriously:

Random number generators use mathematical formulas that transfer set of numbers to another one. If, for example, you take a constant number N and another number n_0, and then take the value of n mod N (the modulo operator), you will get a new number n_1, which looks as it if is unrelated to n_0. Now, repeat the same process with n_1 and you'll get another number. What you have here is a (VERY BAD) generator of seemingly random numbers.

Remember, the method I've described here is a toy method that should not be used for anything serious. It does, however, illustrate the general principle.

Also note:

If all scientific papers whose results are in doubt because of bad rands were to disappear from library shelves, there would be a gap on each shelf about as big as your fist.

(paraphrased from chapter 7 of Numerical recipes). This is a must-read text for anyone who uses random number generators for any serious work.

One of the things to keep in mind is that there are no 'true' random number generators. They just generate numbers that look random to us mere mortals.

One of the easiest examples of this (to implement, as well) is the Linear congruential generator. Sure, the numbers look unpredictable to you and me, but they're actually evenly spaced within a finite field.

Of course, some generators, like Blum Blum Shub aren't predictable for an outsider even if he applies serious mathematical skills and computing power to the task, but at the fundamental level, random number generators aren't random; they're regular and predictable.

How I made them in the old days was by getting some value from the system that changes really rapidly, for example the system millisecond timer.

The next thing you have to do is to apply some formula that will generate a new number from this "input" number and clip it to the range you need, eg 0..255:

random_number = integer(formula(timer-value)) MOD 255

That way, you have a new "random" number every time you call the function.

An example formula function could be:
formula(x) = ((x XOR constant) + constant2) MOD range
XOR used to be one of my favourites.

Update: I realize that this formula is a very bad one, it generates a pretty predictable set of numbers. Also, the system timer is too predictable as a source. So for most applications, this does not suffice. If you need better randomness, use more sources than just the system timer and better formulas to combine them.

I found this one for Java:

http://www.javamex.com/tutorials/random_numbers/java_util_random_algorithm.shtml

by googling how random functions work java

I'm sure the answer is language-specific, but you can try altering my Google query for the language of your choice.

There is a lot of information available about how they are working ... see Konamiman's answer and use google a bit.

Why would you like to write a new random generator? You probably should not try to do so ... until you need something very special. For example in a game you could use a shuffle bag which produces 'fair' random values - have a look at this interesting question on SO.
I post this here, because I really liked the idea and implementation when I read about it the first time :)

It's also common to seed these types of generators by using something like the fifth decimal of the current clock time which also appears random to us. Add together inputs from a few chaotic systems, e.g. weather data, stock market data, again, using modulus and you have good seed numbers.

here is some code for rolling dice it uses a random number generator I developed myself the pad in this RNG hold hexadecimal values 15 of them in all

 DIM pad(15) AS INTEGER
CLS
egg$ = "EFCDBA01457FA968"
  ghh$ = egg$
 nom% = 0
zen% = LEN(ghh$)
WHILE zen% > 0
opp$ = LEFT$(ghh$, 1)
eff% = ASC(opp$)
IF eff% >= 48 AND eff% <= 57 THEN eff% = eff% - 48 ELSE eff% = (eff% - 65) + 10
IF eff% > 15 THEN eff% = eff% - 32
pad(nom%) = eff%
nom% = nom% + 1
zen% = LEN(ghh$) - 1
ypp$ = RIGHT$(ghh$, zen%)
ghh$ = ypp$
WEND
sol& = 0
FOR zyx% = 0 TO 3
sol& = sol& * 16
sol& = sol& + pad(zyx%)
NEXT zyx%
sat% = sol& - 32768
RANDOMIZE sat%
FOR zyx% = 0 TO 15
PRINT HEX$(pad(zyx%));
NEXT zyx%
RANDOMIZE TIMER
respawn:
INPUT "sides per die"; die%
INPUT " number of dice"; dice%
INPUT "number to add to dice roll can be negative"; num%
INPUT "multiplier use 1 if so desired single precision floating point number"; g!
PRINT " hit any key to roll again with these values hit n for new values and q to quit"
PRINT " the number will be added or subtracted first before the multiplier takes effect"
reroll:
sum! = 0
FOR x% = 1 TO dice%
GOSUB rndmz
GOSUB demf
GOSUB drand
k% = INT(dr# * die%) + 1
sum! = sum! + k%
NEXT x%
sum! = (sum! + num) * g!
PRINT "you rolled a :"; sum!
i$ = ""
WHILE i$ = "": i$ = INKEY$: WEND
IF i$ = "n" THEN GOTO respawn
IF i$ = "q" THEN GOTO theend
GOTO reroll
theend:
SYSTEM
END
rndmz: rhet$ = ""
zum% = 0
FOR yxz% = 0 TO 15
FOR zyx% = 0 TO 15
IF zyx% MOD 3 = 0 THEN zum% = (zum% + pad(zyx%)) MOD 16
IF zyx% MOD 3 = 1 THEN zum% = (zum% + 16 - pad(zyx%)) MOD 16
IF zyx% MOD 3 = 2 THEN zum% = (zum% + INT(RND * 16)) MOD 16
NEXT zyx%
rhet$ = rhet$ + HEX$(zum%)
NEXT yxz%
ghh$ = rhet$
RETURN
demf: nom% = 0
zen% = LEN(ghh$)
WHILE zen% > 0
opp$ = LEFT$(ghh$, 1)
eff% = ASC(opp$)
IF eff% >= 48 AND eff% <= 57 THEN eff% = eff% - 48 ELSE eff% = (eff% - 65) + 10
IF eff% > 15 THEN eff% = eff% - 32
pad(nom%) = eff%
nom% = nom% + 1
zen% = LEN(ghh$) - 1
ypp$ = RIGHT$(ghh$, zen%)
ghh$ = ypp$
WEND
FOR zyx% = 0 TO 15
'PRINT HEX$(pad(zyx%));
NEXT zyx%
RETURN
drand: dr# = pad(0)
FOR eff% = 1 TO 15
dr# = dr# / 16
dr# = dr# + pad(eff%)
NEXT eff%
dr# = dr# / 16
RETURN
derf: a# = 1
x# = 1
b# = 1 / (2 ^ .5)
c# = .2500000000000011#
FOR u% = 1 TO 3
y# = a#
a# = (a# + b#) / 2
b# = (b# * y#) ^ .5
c# = c# - x# * (a# - y#) ^ 2
x# = 2 * x#
pi# = ((a# + b#) ^ 2) / (4 * c#)
PRINT pi#
NEXT u%
pi# = pi# + .000000000000015#
PRINT pi#

this here at the end calculates pi to almost as many places possible in just 3 loops through the algorythm sorry about it being written in archaic basic language, it's the only programing language I know, it might be possible to port this over to c++ or Java
Just take a careful look at the logic of this and especially close attention to the priming or seeding / initialization procedures, which must be used or it will fail as a good rng... this is one I developed for gaming purposes where having huge security is not as much of a concern as speed...

Depends on the goal: speed vs quality vs security.

Speed & Security: Linear Congruence is straight forward and does not depend on a public source, privacy of a key is crucial for crypto systems.

Quality: random.org is a source of true random, where you get about 10000 16-Bit values per day free.

Combining several random sources (simpliest XOR) combines their properties.

So, if you also maintain a pool of true random numbers, you have all of speed, quality and security.

https://github.com/fsssosei/Pure_PRNG/tree/main/src/prng_algorithms_package Here is the implementation of the following algorithm: Inversive Congruential Generator, LCG64_32_ext, XSM64, Ran64