The secret of rand()

Page: 1 2
ID:161342
 
May 19 2008, 8:19 pm
So how does the computer (or DM in this case) actually produce RANDOM answers from rand()? Surely it must be based off of something that is predictable? What if you call rand() twice really close together? This has been bugging me since I first touched a Commodore 64 as a small child!

~Ease~
May 19 2008, 8:21 pm
As with almost all random functions, this is a pseudorandom number generator. The random number, even when using random_seed() is system dependent. It probably is predictable, but likely rather difficult to figure out, and most people on BYOND couldn't do it.
May 19 2008, 8:24 pm
Number1 + maths = Number2
Number2 + maths = Number3
Number3 + maths = Number4
May 19 2008, 9:52 pm
In response to Popisfizzy
Popisfizzy wrote:
As with almost all random functions, this is a pseudorandom number generator. The random number, even when using random_seed() is system dependent. It probably is predictable, but likely rather difficult to figure out, and most people on BYOND couldn't do it.

BYOND uses the default rand() implementation in c libs; the implementation varies with platform.
May 20 2008, 1:06 am
Basically, there's some complicated maths going on that generates a sequence of numbers. Generally the sequence does repeat after a while - the idea is that the 'period' of the sequence is long enough that it is unnoticeable. Knuth has an excellent discussion of random number generation in one of his Art of Computer Programming books - try looking for it in a library.
May 20 2008, 4:31 am
In response to Jp
I'm pretty sure I heard somewhere that BYOND's rand() is based on world.time rather than a seed, but don't take my word for it.
May 20 2008, 6:40 am
In response to DivineO'peanut
world.time would be the seed, then (and you can also initialize the generator with a custom seed). Lots of psuedorandom generators use the system clock or a similar value as a base, since it is quite suitable.
May 20 2008, 8:25 am (Edited on May 20 2008, 8:34 am)
In response to Kaioken
Oh, you're right of course! I didn't finish that sentence; I meant to write "rather than a given seed, so the sequence doesn't exactly repeat itself."

... Well, further thinking about it, I'm not sure world.time should be called a "seed," seeing as it is only an element of the calculation and doesn't store itself in the generator. But I'll leave that to the proffessionals.
May 20 2008, 10:29 am
In response to DivineO'peanut
That is obviously not the case, because it would result in pretty much the same sequence of random numbers every single time. world.time starts at 0, and random number generators are only "seeded" once, after that they just use the last generated random number.
May 21 2008, 6:16 pm
In response to DivineO'peanut
Call rand() enough times with the same arguments and it will repeat.
May 22 2008, 1:06 am
In response to Garthor
Isn't world.time a number representing the current date? Or was that world.realtime?
May 22 2008, 1:12 am
In response to Jp
Jp wrote:
Call rand() enough times with the same arguments and it will repeat.

Roll a die enough times and it will repeat. :p
May 22 2008, 1:32 am
In response to Shadowdarke
Ah, but not reliably, with a predictable period, every time. :P
May 22 2008, 7:31 am
As many have said already a computer generated random number is only a pseudo-random number. There's a whole lot of math involved on the internal level, but at the base of it is what's called a seed. A random number generator will always be the same with a given seed. For example:
mob/verb/test_rand()
  rand_seed(10)
  usr<<rand()

should always output the same value. The value may be system dependent, but assuming identical environments the number will be the same. On my system it outputs 0.515717 (random generators usually generate a number between 0 and 1, and use additional math to give a value between a different range).

Most generators use the system clock value as a seed as it's precise enough to provide a different value every time the generator is used. Theoretically, if you could make the generator generate a number fast enough, it would indeed duplicate values due to using the same seed value. This would have to be VERY fast though, as most system clocks operate in several decimals of a second.

So, in answer to part of your question; yes, a random number generator is predictable, IF you know the seed being used and the math behind the generator.

Ease wrote:
So how does the computer (or DM in this case) actually produce RANDOM answers from rand()? Surely it must be based off of something that is predictable? What if you call rand() twice really close together? This has been bugging me since I first touched a Commodore 64 as a small child!

~Ease~
May 22 2008, 12:05 pm
On the C64 BASIC kernal, there was the rand function and a randomize command. This was the same with the vic20, pet, etc. If I remember correctly, C64 randomize didn't use the clock because it was considered too predictable. Instead, they were able to make use of RF noise coming from the sound chip and use that. I could be wrong, though. Been a long time!
May 23 2008, 6:55 am
In response to Traztx
Traztx wrote:
Instead, they were able to make use of RF noise coming from the sound chip and use that. I could be wrong, though. Been a long time!

Yep, this is a known method of a different, quality seed source. Such a good source effectively changes the the psuedo-random number generator into a random one; although most games use a psuedorandom generator, which is effectively ultimately predictable. Players actually abuse the predictability on some types of singleplayer games, by making pre-defined actions to result in a specifically random result that is wanted. An example would be killing an enemy in a very specific way and order of actions, in order to cause a specific random item to be dropped after the battle.

(Anyway, this topic doesn't belong in this section, since it isn't really directly related to BYOND or how to do things in DM. As for most things, the internet holds a lot of info about this. You can access an adequate amount of it by searching in Google,Wikipedia... =) )
May 23 2008, 7:26 am
In response to Kaioken
Kaioken wrote:
Traztx wrote:
Instead, they were able to make use of RF noise coming from the sound chip and use that. I could be wrong, though. Been a long time!

Yep, this is a known method of a different, quality seed source. Such a good source effectively changes the the psuedo-random number generator into a random one; although most games use a psuedorandom generator, which is effectively ultimately predictable. Players actually abuse the predictability on some types of singleplayer games, by making pre-defined actions to result in a specifically random result that is wanted. An example would be killing an enemy in a very specific way and order of actions, in order to cause a specific random item to be dropped after the battle.

This basically amounts to a myth, because there's no way for a player to influence the random sequence. At bes,t you can figure out where you are on the sequence, and just run through it until you reach the number you want... but keeping in mind that random number generators tend to repeat after in the range of 4.3*106001 (thank you, Wikipedia!) that's not going to be very helpful.

An example that might fit what you're talking about would be the Civilization games, or at least IV: your current random seed gets saved, so if you load a savefile, anything random (which is almost always combat) will occur exactly the same as it would've, so it's somewhat more difficult to cheese a fight by saving and loading when you fail.
May 23 2008, 9:18 am
In response to Garthor
Garthor wrote:
This basically amounts to a myth,

But why, I've done it myself multiple times, and so have many others. Of course, you wouldn't be able to do it in any game, and mostly only effectively on single-player games. It also depends on the system you're playing the game on...

there's no way for a player to influence the random sequence.

Doing actions in the game that cause use of the RNG does influence it. In actuality, I'm not well-informed on the specifics, though, as I haven't done actual deep research or experimenting myself on that; all that is needed is following a list of steps in a respective guide after resetting the game.

An example that might fit what you're talking about would be the Civilization games, or at least IV:

Of course, that's not the only game where you can cause the random seed to acquire a previous value. Resetting the system and/or reloading a save or doing a specific in-game action, can all possibly work in the right games.
May 23 2008, 10:17 am
In response to Traztx
Traztx wrote:
On the C64 BASIC kernal, there was the rand function and a randomize command. This was the same with the vic20, pet, etc. If I remember correctly, C64 randomize didn't use the clock because it was considered too predictable. Instead, they were able to make use of RF noise coming from the sound chip and use that. I could be wrong, though. Been a long time!

The Atari series pulled its random numbers from the shift registers in the POKEY chip, which was used for joystick control and sound. I think it's likely other home computers did the same, so maybe that's what you were thinking of, though I don't really know those architectures so I couldn't say. Without researching it myself I wouldn't rule out that RF noise actually was pulled in, but converting that to high-entropy digital data would probably have been a bit of a chore for the computers of the time. And with the speeds they ran under, it'd be crucial to get 8 random bits in parallel, which might not have been achievable.

Lummox JR
May 23 2008, 11:27 am
In response to Kaioken
If a game always uses the same seed then yes, you can predict the value at any time. Most games will seed the random number generator with the clock, however, and you won't be able to do that.

I find it really funny that these hypothetical games you're talking about never bothered to do such a thing.
Page: 1 2