random number generator

[Barnaby W. Füi]

how would you create one? it seems all too convienient that when programming, etc., they are just "there", how would you make something create its own completely random results without falling back on an existing random number generator?

 

[blahblah99]

Are you talking about a software random generator, or a true random generator?


Software RNG's usually use the time() function as a seed value. There ARE algorithms for random number generation, but then you fall upon the same numbers if you restart the program.


Nature is a true RNG - if you want true randomness, use nature and the decay time of an isotope (i think?).

 

[Barnaby W. Füi]

<< There ARE algorithms for random number generation, but then you fall upon the same numbers if you restart the program >>


i mean a TRUE random number generator, just using standard programming languages, not using a predetermined value to base it from, how would you accomplish such a thing, and not one where it would give the same results every time you run it?

 

[m0ti]

Just a guess, but you could get the time from the system clock, and then do a large number of shift and rotate operations on it (like RC5), and then scale it to the appropriate range.

 

[Zach]

<<

<< There ARE algorithms for random number generation, but then you fall upon the same numbers if you restart the program >>


i mean a TRUE random number generator, just using standard programming languages, not using a predetermined value to base it from, how would you accomplish such a thing, and not one where it would give the same results every time you run it? >>



The point of using a computer is that it returns the same value for a given input every single time. You need to use something that fluctuates to make random crap happen, like running math operations on the system time. A computer can't just "guess a number". I mean, think about it. Write an algorithm.

if (maybe) {
x *= 3;
} else {
x *= 2;
}

Okay, now get the computer to get a different maybe value each time.

 

[Sunner]

Doesn't the RNG on Intel's newer chipsets use all kinds of variables, such as time, system temperatures, etc to create random numbers?

That would seem like a very good way to come up with the basics of a random number.

 

[Haden]

For older cpu's random functions are based on time value. I know only one algorith for sure (Synclair systems used it in +-1985).
As systems starts it begins to rise particular number by power. (7.5^2, 7.5^3...). It's done every step so at certain moment you can't really know what number is currently called random. Some other math operations are applied so "random" numbers don't increase/decrease periodically.
Again then certain program runs it's run moment is unknown so random numbers seems to be really scattered.
If for some reason you want to write random generator, I suggest these steps:
1. Get several values based on current system time, time since windows start etc.
2. Apply some math functions (sin, cos, exp) (not sure is it usefull, but wont make it worse)
3. Create some IF (a>b).... checks, (a,b... is your values from step 1-2). Different paths should count random number differently:
(say if ((a>b) && (c<d)) random=a+b/c-d else ....)

Your random number will reflect system time, current date, current time at "unknown" moment.
Scale it.

P.S. However I see no reason for you to do something like this, random function soon will be cpu temperature related (Intel already did this I think).

 

[Barnaby W. Füi]

well i'm not trying to make one, just curious as to how they are made.

so really without relying on time or date, or some predetermined value, there is no way to create a real random number with a computer. interesting.

 

[Zach]

Well, computers are really dumb. If this, then that. That's pretty much it. Can't get random with that, but that's the purpose, to not be random. So it ends up being a chore to not be random. Unlike people.

 

[flood]

You could use the nth digit of pi formula. It doesnt take much to compute it and the digits of pi are perfectly random.

 

[warhorse]

If you are interested in random theory, check this out:
http://www-2.cs.cmu.edu/afs/cs.cmu....e/Materials/Lectures/lecture20/lecture20.html
Basically, you can define a random number through incompressibility. If you can't compess a number, there must be no pattern and therefore it must be random

Back on topic:

There are functions f(x) where you just take a number (I think, I can't remember) and then you can generate a random number. If the distribution of outputs as the limit of inputs approaches infinity is evenly distributed over the ten digits, then the function is considered random. If I remember correctly you can use these functions to return a single digit which is random.
There are ways to make upper bounds and so on, but there is a specific definition of "random" such that some functions will generate numbers that are random "enough" such that given true randomness you could never ever tell the difference.

Ok. By now, I remember the classroom and the professor that taught that, but that was last semester and so I don't have access to those materials.

 

[CTho9305]

but you can generate pi with an algorithm. is that not the same effect as compression?

 

[warhorse]

Yes, you are right. Pi is not a random number. However it's digits can be considered random. Therefore I think using a function that calculates the n'th digit of pi is effectively random.

 

[Mookow]

I remember some guy wrote an article where he used a device that took the "thermal noise" (it was some kind of noise) off a diode at the 5th digit or something like that. It gave very, very close to random numbers (he XOR-ed (exclusive or-ed) and the resulting number was almost ideal).

 

[flood]

<< but you can generate pi with an algorithm. is that not the same effect as compression? >>



linkage


<< A simple formula discovered with the integer-relation algorithm dubbed PSLQ makes it possible to calculate the Nth binary digit of Pi without computing any of the first N-1 digits, and do the computation with very little computing power. >>



(regarding pi)
<<in the familiar base 10 decimal number system, any single digit of a normal number occurs one tenth of the time, any two-digit combination occurs one one-hundredth of the time, and so on. It's like throwing a fair, ten-sided die forever and counting how often each side or combination of sides appears.>>

 

[Turkey]

Depends on your definition of random... everything is random in one sense or another. There are such things as random number functions (generators) that have no apparent or easy to distinguish pattern between inputs and outputs, one of which is what your computer uses to generate random numbers. There are an infinite number of possible implementable random number generators using standard programming languages - you could capture the key values recently input and use that as a random number, or feed that as input to a hash function if you wanted, or capture the timing of recently input keys, or the data that comes to your network connection device, or use a function of the previous N points the mouse, etc etc.

Supposedly MS's GUIDGen.exe will produce a unique 128-bit number every time it's run, no matter if it's on different machines at different times in different locations. Don't ask me how it works. But, I did some math.

2^128 = 3.4e38 +-

If each processor can do 2bil guids/sec (unlikely), and there are, say, 1e12 processors able to do this (also unlikely), then

2bil guids/sec * 1tera processors = 2e21 guid*proc/sec

It would then take about 1.7e 17 sec to generate all guids possible, which is about 5.4 bil years. Of course this time will decrease as people adopt faster processors and use them in the distributed GUIDGen.exe project . That's pretty random.

 

[Shalmanese]

<< You could use the nth digit of pi formula. It doesnt take much to compute it and the digits of pi are perfectly random. >>



Why is it only me that sees something wrong with this? What is n? n is a random integer right? How do we calculate n? Why thats simple, we simply pick an nth digit of pi...

 

[VTHodge]

<<

<< You could use the nth digit of pi formula. It doesnt take much to compute it and the digits of pi are perfectly random. >>



Why is it only me that sees something wrong with this? What is n? n is a random integer right? How do we calculate n? Why thats simple, we simply pick an nth digit of pi... >>



hehehe . . . I love it.

But seriously . . . I have read that when doing encryption and things of that nature, mathematicians use the randomness of radio interference in the atmosphere. I don't have anything to back that up though, just thought it was worth throwing into the ring.

 

[Jerboy]

How DO you create TRUE random numbers? Be it computer or not.

Does tossing multiple dices of various type(18sided, 6 sided, etc. ) comes up with closer to true random number than computers could ever generate?

 

[Shalmanese]

Big thing a while ago about how Toshiba released a True random number generator that plugs into a PCI slot and utilises thermal noise, lots of hubub.

 

[Moohooya]

Typically one would want an equal probability of any number being returned by a random number generator, and their being no petterns in the sequence of numbers returned.

Just becuase pi does not repeat, does not say that pi contains an equal distrubuation of the numbers 0-9, or even that there is no pattern. The number
1.121121112111121111121111112
does not repeat but the pattern is simple, and the distribution is awful.

I don't know enough about pi to even thing about how to prove that it could be used for random number generation, so I'd leave it well along and look at other algorithms.

You actually don't need to use any fancy math, trig functions etc to get a pretty decent random number sequence from a seed. This for the most part is all you'll ever need. The seed can be generated by so many different parts, you can be sure you have a decent seed value.

For example, I'd use a combination of the following.
Current time (low resolution)
Time since system was started (low resolution)
Current CPU timer value (high resolution)

These should be available to everyone.

If however you wanted to add more truely random numbers
Ping time to www.yahoo.com
Current mouse position
Time since last key press
Current microphone sample. (Check there is a microphone attached.)