How does the computer generate a random number?

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

Assasinof6
Posts: 22
Joined: Sun May 09, 2010 1:37 pm UTC

How does the computer generate a random number?

Postby Assasinof6 » Sat Jul 24, 2010 2:42 pm UTC

I was just fooling arounde in C++, and I decided to use the <cmath> (or <math.h> if you prefer C) random function rand().
It gives me 41 every-time. This isn't a particular concern, but just curiosity- why can't the math library / computer generate a random number? If you are really interested, here is the simplified version of the code I was using at the time:
Spoiler:
#include <iostream>
#include <cmath>
int main()
{
using namespace std;

double num1;
num1 = rand();
cout<<num1;

return 0;
}
I see.
What?
That you don't.

danreil
Posts: 26
Joined: Tue May 18, 2010 1:57 am UTC

Re: How does the computer generate a random number?

Postby danreil » Sat Jul 24, 2010 3:21 pm UTC

I'm not too familiar with how rand() works in C, but did you try feeding the system time into the random seed number?

Rysto
Posts: 1460
Joined: Wed Mar 21, 2007 4:07 am UTC

Re: How does the computer generate a random number?

Postby Rysto » Sat Jul 24, 2010 4:43 pm UTC

It can't unless it has specialized, expensive equipment for measuring a truly random event. Commodity hardware certainly does not. Instead, the computer produces a sequences of pseudo-random numbers algorithmically.

User avatar
SlyReaper
inflatable
Posts: 8015
Joined: Mon Dec 31, 2007 11:09 pm UTC
Location: Bristol, Old Blighty

Re: How does the computer generate a random number?

Postby SlyReaper » Sat Jul 24, 2010 4:57 pm UTC

"Random" numbers in a computer aren't random, they're simply complicated functions of some other number. From your description, it sounds like your random function has a constant seed, and will therefore produce exactly the same sequence of "random" numbers every time the program is run. The usual way to get around this is to set your system time as the seed.
Image
What would Baron Harkonnen do?

User avatar
sircrayons
Posts: 86
Joined: Wed Mar 10, 2010 3:17 am UTC
Contact:

Re: How does the computer generate a random number?

Postby sircrayons » Sat Jul 24, 2010 5:08 pm UTC

You should call to srand() once before you start using rand().
"Ford, you're turning into a penguin. Stop it."

Assasinof6
Posts: 22
Joined: Sun May 09, 2010 1:37 pm UTC

Re: How does the computer generate a random number?

Postby Assasinof6 » Sat Jul 24, 2010 5:57 pm UTC

sircrayons wrote:You should call to srand() once before you start using rand().


why, whats the difference?
I see.
What?
That you don't.

User avatar
Xanthir
My HERO!!!
Posts: 5400
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: How does the computer generate a random number?

Postby Xanthir » Sat Jul 24, 2010 7:15 pm UTC

So, there are several ways to generate random numbers in a computer: real randomness, and pseudorandomness.

Real randomness is what you get on a unix system by reading from /dev/random, for example (for most unixes - some of them treat /dev/random as /dev/urandom, below). That gets filled with randomness by integrating "noise" from the activity of your disk and network, which is assumed to be unpredictable and high-entropy. Some computers have special chips on them which grab atmospheric radio-frequency noise just to help fill /dev/random with more and higher-quality randomness.

Pseudorandomness, on the other hand, uses specially crafted algorithms that generate a definite series of numbers, which is nonetheless unpredictable if you don't know what the starting number was (the starting number is commonly known as a "seed"). Pseudorandomness is closely related to cryptography. The /dev/urandom device on unix systems is a pseudorandom generator. It uses some randomness to establish seeds, but then uses high-quality pseudorandom generators to produce numbers for you. Eventually they cycle around and start reproducing the same numbers, but good algos can go a very long time without doing so.

The advantage of pseudorandom number generators is that you only need to feed them unpredictable data when you start them out - afterwards, they can just pump out pseudorandom numbers for a long time without stopping. True random generators need to constantly be fed unpredictable data so that they can keep up their pool of entropy that they use to generate numbers. But, pseudorandom generators can be predicted if you know what algorithm is being used and what the seed is.

Most programming languages with a random-number function use a pseudorandom generator internally. Some languages seed the generator for you automatically, some don't. In C you need to explicitly seed the generator before you use it by calling the srand() function with some unpredictable argument. While not sufficient for *true* cryptographic purposes, just passing the system time, which changes every second, is usually sufficient to make the numbers "random" for use in an ordinary program.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
sircrayons
Posts: 86
Joined: Wed Mar 10, 2010 3:17 am UTC
Contact:

Re: How does the computer generate a random number?

Postby sircrayons » Sat Jul 24, 2010 7:27 pm UTC

Assasinof6 wrote:
sircrayons wrote:You should call to srand() once before you start using rand().


why, whats the difference?


Well, the computer uses some algorithm to generate random numbers. The algorithm is generally a simple formula that takes some initial value (called the seed), plugs it in to this formula, and computes the result. This result becomes the first pseudo-random number generated (in the case of your program, this would be the 41). When you call rand() again to ask for a second number, it takes the previous result (again, your 41) and plugs it into the formula to compute the next number. It does this for as many numbers as you ask it for. That is, it always uses the previous result to calculate the next.

The problem with this is that every time you run your program the first random number you generate will always be the same. As a matter of fact, so will the second, and third, and every number after. The reason is that rand() uses the same seed (the number 1) the first time it's called. To change this, you call srand() before your first call to rand(), and pass to srand() some other seed value. Commonly, you'll use the current time so that the seed is something different each time you run your program:

Code: Select all

#include <cstdlib>
#include <ctime>
#include <iostream>

int main()
{
    std::srand(static_cast<unsigned>(std::time(0)));
    for(int i = 0; i < 10; ++i)
    {
        std::cout << std::rand() << std::endl;
    }

    return 0;
}
"Ford, you're turning into a penguin. Stop it."

mouseposture
Posts: 42
Joined: Tue Sep 15, 2009 2:42 am UTC

Re: How does the computer generate a random number?

Postby mouseposture » Sat Jul 24, 2010 11:05 pm UTC

Maybe worth mentioning that the reproducibility of pseudorandom sequences, given the same seed, is really quite useful, if you're runing a Monte Carlo simulation: you may want to run the program repeatedly with "random" input that's the same every time. If you were using a truly random generator, you'd have to store the entire random sequence in a file.

Can someone tell me this: Is my system insecure if I exhaust its supply of entropy, e.g.

Code: Select all

cat /dev/random > /dev/null


I'm fascinated by the notion of randomness as a valuable commodity of which one can have less than one needs.

User avatar
hotaru
Posts: 1045
Joined: Fri Apr 13, 2007 6:54 pm UTC

Re: How does the computer generate a random number?

Postby hotaru » Sat Jul 24, 2010 11:24 pm UTC

mouseposture wrote:Can someone tell me this: Is my system insecure if I exhaust its supply of entropy, e.g.

Code: Select all

cat /dev/random > /dev/null

no.
When the entropy pool is empty, reads from /dev/random will block until additional environmental noise is gathered.

Code: Select all

factorial product enumFromTo 1
isPrime n 
factorial (1) `mod== 1

tuseroni
Posts: 124
Joined: Fri Jun 25, 2010 10:41 pm UTC

Re: How does the computer generate a random number?

Postby tuseroni » Sun Jul 25, 2010 12:13 am UTC

there is pretty much nothing to add here. i came into this with a list of points to make on the topic...and everyone has beat me to it...

so instead i will talk about how much i love /dev/random
when i want to make something which i know is frikken random i use /dev/random (usually i use some set of bytes from /dev/random and use that as the seed in srand() to keep me from having to make a read to /dev/random every time i needed a new random number) /dev/random is cryptographically secure (unless you know exactly what the system entropy was at the point of reading...which can happen if done during early boot up)
but if you are just, say, rolling a die....srand(std::time(0)) will be more than enough for a good seed.
Image

Assasinof6
Posts: 22
Joined: Sun May 09, 2010 1:37 pm UTC

Re: How does the computer generate a random number?

Postby Assasinof6 » Sun Jul 25, 2010 2:14 am UTC

Ok, thank you very much everyone! Now I understand.
I see.
What?
That you don't.

User avatar
thoughtfully
Posts: 2253
Joined: Thu Nov 01, 2007 12:25 am UTC
Location: Minneapolis, MN
Contact:

Re: How does the computer generate a random number?

Postby thoughtfully » Sun Jul 25, 2010 5:12 am UTC

Rysto wrote:It can't unless it has specialized, expensive equipment for measuring a truly random event. Commodity hardware certainly does not. Instead, the computer produces a sequences of pseudo-random numbers algorithmically.

A lot of Nvidia motherboard chipsets used to have shot noise TRNGs in them. It doesn't have to be difficult or expensive. I seem to recall the old Intel i860 did also, but that isn't really a consumer item.
Image
Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away.
-- Antoine de Saint-Exupery

shieldforyoureyes
Posts: 342
Joined: Sat Apr 19, 2008 9:00 am UTC
Contact:

Re: How does the computer generate a random number?

Postby shieldforyoureyes » Sun Jul 25, 2010 10:24 am UTC

mouseposture wrote:Maybe worth mentioning that the reproducibility of pseudorandom sequences, given the same seed, is really quite useful, if you're runing a Monte Carlo simulation: you may want to run the program repeatedly with "random" input that's the same every time. If you were using a truly random generator, you'd have to store the entire random sequence in a file.


I use that all the time in animation - I have a random sequence that generates some aspect of one frame, and I need the sequence to be the same for every frame in the animation.

shieldforyoureyes
Posts: 342
Joined: Sat Apr 19, 2008 9:00 am UTC
Contact:

Re: How does the computer generate a random number?

Postby shieldforyoureyes » Sun Jul 25, 2010 10:28 am UTC

Xanthir wrote:
Real randomness is what you get on a unix system by reading from /dev/random, for example (for most unixes - some of them treat /dev/random as /dev/urandom, below). That gets filled with randomness by integrating "noise" from the activity of your disk and network, which is assumed to be unpredictable and high-entropy. Some computers have special chips on them which grab atmospheric radio-frequency noise just to help fill /dev/random with more and higher-quality randomness.


There is a tiny niche of users who do not consider the noise from disk & network activity to be sufficient, and require a special hardware source for "real random numbers". Crypto accelerators usually include a real random number generator.

User avatar
Dthen
Still hasn't told us what comes after D
Posts: 553
Joined: Sat Jan 02, 2010 6:35 pm UTC
Location: Ayrshire, Scotland

Re: How does the computer generate a random number?

Postby Dthen » Sun Jul 25, 2010 10:42 am UTC

http://xkcd.com/221/

Mandatory comic link.
Dthen wrote:I AM NOT A CAT.

jagdragon
Posts: 19
Joined: Sat Feb 28, 2009 11:35 pm UTC

Re: How does the computer generate a random number?

Postby jagdragon » Sun Jul 25, 2010 10:55 am UTC

Dthen wrote:http://xkcd.com/221/

Mandatory comic link.


Liking the mandatory comic link.

So why are both /dev/urandom and /dev/random on unix systems? Is there some reason that one would choose to have a pseudorandom number rather than an almost-cryptographically-secure random number?

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: How does the computer generate a random number?

Postby Berengal » Sun Jul 25, 2010 12:24 pm UTC

Because /dev/random blocks. Try 'cat /dev/random', see what happens, jiggle the mouse a bit, then compare with 'cat /dev/urandom'.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
PM 2Ring
Posts: 3707
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

Re: How does the computer generate a random number?

Postby PM 2Ring » Sun Jul 25, 2010 12:50 pm UTC

I see that Berengal's answered the /dev/random v /dev/urandom question, so I'll just comment on this bit:
jagdragon wrote:Is there some reason that one would choose to have a pseudorandom number rather than an almost-cryptographically-secure random number?

Because you can regenerate the same random data for later re-use, instead of saving it in a big array or in a file. As mouseposture said it's important when analyzing simulated random processes. If you want to try a variety of techniques to manipulate or analyze a random system, it's very handy to be able to re-create the same data set. And as shieldforyoureyes said, this is also very useful when doing animation.

I use this technique a lot when creating random scenes in POV-Ray, a free script-based ray-tracer. Say I want a few thousand objects randomly placed around the scene, with random colours. I use a few pseudo-random streams to generate the position, size, orientation & colours of my objects. The POV script is re-run for each frame of an animation, and I can use the frame number to transform the camera viewpoint, or to algorithmically alter the objects current location, etc, and to do that I need to know the objects' original location as well as the time (which can be determind from the frame number). If I was using "true" random numbers I would need to store all those random parameters in a file, & re-read them for each frame, which is much slower than simply regenerating tha same pseudo-random sequence.

mouseposture
Posts: 42
Joined: Tue Sep 15, 2009 2:42 am UTC

Re: How does the computer generate a random number?

Postby mouseposture » Sun Jul 25, 2010 3:01 pm UTC

hotaru wrote:
mouseposture wrote:Can someone tell me this: Is my system insecure if I exhaust its supply of entropy, e.g.

Code: Select all

cat /dev/random > /dev/null

no.
When the entropy pool is empty, reads from /dev/random will block until additional environmental noise is gathered.


Ow. I think my toaster just stabbed me in the face :?

User avatar
Xanthir
My HERO!!!
Posts: 5400
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: How does the computer generate a random number?

Postby Xanthir » Sun Jul 25, 2010 6:11 pm UTC

shieldforyoureyes wrote:
Xanthir wrote:
Real randomness is what you get on a unix system by reading from /dev/random, for example (for most unixes - some of them treat /dev/random as /dev/urandom, below). That gets filled with randomness by integrating "noise" from the activity of your disk and network, which is assumed to be unpredictable and high-entropy. Some computers have special chips on them which grab atmospheric radio-frequency noise just to help fill /dev/random with more and higher-quality randomness.


There is a tiny niche of users who do not consider the noise from disk & network activity to be sufficient, and require a special hardware source for "real random numbers". Crypto accelerators usually include a real random number generator.

That's why I explicitly said that some computers have a special chip just to generate higher-quality entropy. Atmospheric RF noise is the usual source. You could certainly have chips that use other types of sources, though.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: How does the computer generate a random number?

Postby Berengal » Sun Jul 25, 2010 9:15 pm UTC

It's also worth considering that real randomness is so hard to get that there are people selling it by the gigabyte.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
MHD
Posts: 630
Joined: Fri Mar 20, 2009 8:21 pm UTC
Location: Denmark

Re: How does the computer generate a random number?

Postby MHD » Mon Jul 26, 2010 8:19 pm UTC

Re: real randomness, you can buy a relatively cheap USB device that uses some photo-diode trick to create a lot of quantum-random data.

"Re" is Latin and means "Concerning the topic of."
EvanED wrote:be aware that when most people say "regular expression" they really mean "something that is almost, but not quite, entirely unlike a regular expression"

User avatar
Emu*
Posts: 689
Joined: Mon Apr 28, 2008 9:47 am UTC
Location: Cardiff, UK
Contact:

Re: How does the computer generate a random number?

Postby Emu* » Tue Jul 27, 2010 9:37 am UTC

Re: Re:, is it not short for "Regarding"?
Cosmologicon wrote:Emu* implemented a naive east-first strategy and ran it for an hour, producing results that rivaled many sophisticated strategies, visiting 614 cells. For this, Emu* is awarded Best Deterministic Algorithm!

troyp
Posts: 557
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW

Re: How does the computer generate a random number?

Postby troyp » Tue Jul 27, 2010 1:11 pm UTC

"re" means "thing" in Latin. I think it's actually shortened from the phrase "in re", which would mean something like "with regard to the thing" or "in the matter of".
People often think of it as standing for "regarding", though.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11116
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: How does the computer generate a random number?

Postby Yakk » Wed Jul 28, 2010 4:06 pm UTC

I think Star Control 2 used the "pseudo random seed" to populate the universe with planets that have texture.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
xe3r
Posts: 21
Joined: Sat Dec 12, 2009 8:56 pm UTC
Location: /tmp/earth
Contact:

Re: How does the computer generate a random number?

Postby xe3r » Sun Aug 01, 2010 12:39 pm UTC

You cannot create a random number through an algorithm..Through its definition.. But on the other hand,do you consider the world random,or too difficult to predict? :P

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

Re: How does the computer generate a random number?

Postby Token » Fri Aug 06, 2010 11:06 pm UTC

troyp wrote:"re" means "thing" in Latin. I think it's actually shortened from the phrase "in re", which would mean something like "with regard to the thing" or "in the matter of".
People often think of it as standing for "regarding", though.

It's the ablative singular of "res". No preposition needed - very literally, it means something close to "about the thing". In the specific case of emails, though, it might as well be short for "reply".
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

squareroot
Posts: 548
Joined: Tue Jan 12, 2010 1:04 am UTC
Contact:

Re: How does the computer generate a random number?

Postby squareroot » Fri Aug 06, 2010 11:40 pm UTC

Token wrote:
troyp wrote:"re" means "thing" in Latin. I think it's actually shortened from the phrase "in re", which would mean something like "with regard to the thing" or "in the matter of".
People often think of it as standing for "regarding", though.

It's the ablative singular of "res". No preposition needed - very literally, it means something close to "about the thing". In the specific case of emails, though, it might as well be short for "reply".

Often, though, ablatives will have prepositions... "in foro", for instance. "About the thing" would be better approximating by "de re", I think...
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me - __ -

User avatar
MHD
Posts: 630
Joined: Fri Mar 20, 2009 8:21 pm UTC
Location: Denmark

Re: How does the computer generate a random number?

Postby MHD » Mon Aug 09, 2010 2:57 pm UTC

xe3r wrote:You cannot create a random number through an algorithm..Through its definition.. But on the other hand,do you consider the world random,or too difficult to predict? :P


Good question. But quantum-mechanics might wanna have a word with you :P
EvanED wrote:be aware that when most people say "regular expression" they really mean "something that is almost, but not quite, entirely unlike a regular expression"

troyp
Posts: 557
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW

Re: How does the computer generate a random number?

Postby troyp » Tue Aug 10, 2010 4:47 am UTC

re re: I didn't mean to imply that the prepostition was necessary, just that it was, in fact, originally present - maybe for emphasis or whatever. At least that's what I remember hearing. I didn't mention the case of re since I couldn't remember if "in" took the dative or ablative case, or even what the ablative was for exactly. I mean what language even *has* an "ablative" case? Bloody Romans...
Anyway, I think "regarding" is a better 'false etymology' than "reply", since "re" doesn't have to be in a reply, necessarily.

How did this thread generate a random topic?


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 4 guests