Author Topic: Idiosyncrasies of rand()  (Read 3581 times)

0 Members and 1 Guest are viewing this topic.

Offline Goober5000

  • HLP Loremaster
  • Moderator
  • 214
    • Goober5000 Productions
Idiosyncrasies of rand()
Also, be aware that the random number generator will return the same sequence of numbers from mission to mission unless you give it a random seed before first use.

 

Offline General Battuta

  • Poe's Law In Action
  • 214
  • i wonder when my postcount will exceed my iq
Re: Idiosyncrasies of rand()
Also, be aware that the random number generator will return the same sequence of numbers from mission to mission unless you give it a random seed before first use.

Wait, what?

 

Offline The E

  • He's Ebeneezer Goode
  • Moderator
  • 213
  • Nothing personal, just tech support.
    • Steam
    • Twitter
Re: Idiosyncrasies of rand()
Looking through the code, we're initializing the global(!) rng several times over the runtime of the program, if not several times over the course of a mission. I wonder whether that's actually a good idea; shouldn't we only seed the rng once (or twice, if we need to sync the rng for multiplayer)?
If I'm just aching this can't go on
I came from chasing dreams to feel alone
There must be changes, miss to feel strong
I really need lifе to touch me
--Evergrey, Where August Mourns

 

Offline 0rph3u5

  • 211
  • Oceans rise. Empires fall.
Re: Idiosyncrasies of rand()
Also, be aware that the random number generator will return the same sequence of numbers from mission to mission unless you give it a random seed before first use.

Wait, what?

It the difference between random-multiple-of/rand-multiple and random-of/rand in the sexp. "rand" will always return the same result from within the range you have set if the event is called more than once, rand-multiple will return different results each time...



EDIT: BTW can engine randomize negative numbers now? - I am still operating under the assumption that if I want the engine to randomly place/move objects via sexp, I only get to use the +/+/+ quadrant of the mission space...
« Last Edit: February 24, 2016, 05:19:32 pm by 0rph3u5 »
"As you sought to steal a kingdom for yourself, so must you do again, a thousand times over. For a theft, a true theft, must be practiced to be earned." - The terms of Nyrissa's curse, Pathfinder: Kingmaker

==================

"I am Curiosity, and I've always wondered what would become of you, here at the end of the world." - The Guide/The Curious Other, Othercide

"When you work with water, you have to know and respect it. When you labour to subdue it, you have to understand that one day it may rise up and turn all your labours into nothing. For what is water, which seeks to make all things level, which has no taste or colour of its own, but a liquid form of Nothing?" - Graham Swift, Waterland

"...because they are not Dragons."

 

Offline Galemp

  • Actual father of Samus
  • 212
  • Ask me about GORT!
    • Steam
    • User page on the FreeSpace Wiki
Re: Idiosyncrasies of rand()
"rand" will always return the same result from within the range you have set if the event is called more than once, rand-multiple will return different results each time...

I see... so if you have several events like "Disable transport #rand" and "Disarm transport #rand" then that will be persistent for the duration of the mission. If you were to use rand-multiple, you would want to write that value to a variable, then use the variable in your events.

Am I doing this right?
"Anyone can do any amount of work, provided it isn't the work he's supposed to be doing at that moment." -- Robert Benchley

Members I've personally met: RedStreblo, Goober5000, Sandwich, Splinter, Su-tehp, Hippo, CP5670, Terran Emperor, Karajorma, Dekker, McCall, Admiral Wolf, mxlm, RedSniper, Stealth, Black Wolf...

 

Offline Goober5000

  • HLP Loremaster
  • Moderator
  • 214
    • Goober5000 Productions
Re: Idiosyncrasies of rand()
Topic split because I don't want to bog down a straightforward help request with implementation details.


Also, be aware that the random number generator will return the same sequence of numbers from mission to mission unless you give it a random seed before first use.

Wait, what?

That was my initial reaction too.  While FREDding a mission for Scroll, I used sexps to make a simple departure after a random period of time.  However, I noticed that the departure delay was identical for every playthrough of the mission.  It wasn't until I made a new event that seeded the random number generator and then chained the delay sexp to that event (so that rand wouldn't evaluate until after the seeding) that I finally got the delay to vary from playthrough to playthrough.

However, the plot thickens...

Looking through the code, we're initializing the global(!) rng several times over the runtime of the program, if not several times over the course of a mission. I wonder whether that's actually a good idea; shouldn't we only seed the rng once (or twice, if we need to sync the rng for multiplayer)?

I looked through the code just now myself.  With the exception of two edge cases, we seed the RNG once when the game starts up and then once each time a mission is loaded.  This is the correct behavior, within the parameters of FS2's design.

However, the seed-upon-mission-load is written to use the system clock time for single-player missions.  This should produce a unique random number sequence for every playthrough.  It therefore baffles me as to why I was ending up with the same delay every time. :confused:


EDIT: BTW can engine randomize negative numbers now? - I am still operating under the assumption that if I want the engine to randomly place/move objects via sexp, I only get to use the +/+/+ quadrant of the mission space...

Yes, rand and rand-multiple should accept and return negative numbers now.


I see... so if you have several events like "Disable transport #rand" and "Disarm transport #rand" then that will be persistent for the duration of the mission. If you were to use rand-multiple, you would want to write that value to a variable, then use the variable in your events.

Am I doing this right?

You only need rand-multiple if you have a repeating event, whether that is due to a repeat count, a trigger count, or a when-argument sexp.  Rand-multiple will return different numbers for every repetition.  Rand will return the same number for every repetition.

 

Offline karajorma

  • King Louie - Jungle VIP
  • Administrator
  • 214
    • Karajorma's Freespace FAQ
Re: Idiosyncrasies of rand()
If the seed you give rand is 0 it should always spit out the same numbers every time. Could it be that your system clock is somehow giving zero as the seed?

We have actually talked about this before.
« Last Edit: February 25, 2016, 01:11:25 am by karajorma »
Karajorma's Freespace FAQ. It's almost like asking me yourself.

[ Diaspora ] - [ Seeds Of Rebellion ] - [ Mind Games ]

 

Offline The E

  • He's Ebeneezer Goode
  • Moderator
  • 213
  • Nothing personal, just tech support.
    • Steam
    • Twitter
Re: Idiosyncrasies of rand()
My question is, why are we reseeding the rng anyway? I can sort of see doing so in order to keep the rng in sync in multiplayer (even though that largely doesn't matter to us, since most of the important rng-related things, like sexps and AI, are handled by the server), but surely a single seed on program start should yield a sufficiently random number sequence?

The thing about seeding the rng in sexps is that you can only predict the first round of call to the rng (That is, during a single run of eval_sexp for the entire tree). After that, given that we use random numbers in various other places, it should be impossible to determine what the next number will be.
If I'm just aching this can't go on
I came from chasing dreams to feel alone
There must be changes, miss to feel strong
I really need lifе to touch me
--Evergrey, Where August Mourns

 

Offline Galemp

  • Actual father of Samus
  • 212
  • Ask me about GORT!
    • Steam
    • User page on the FreeSpace Wiki
Re: Idiosyncrasies of rand()
My question is, why are we reseeding the rng anyway? ...surely a single seed on program start should yield a sufficiently random number sequence?

As Goober noted in his mission testing, if we want a random number to be used in a mission, it should be randomized for every playthrough. Replaying the same mission in the same program session should re-seed the RNG.
"Anyone can do any amount of work, provided it isn't the work he's supposed to be doing at that moment." -- Robert Benchley

Members I've personally met: RedStreblo, Goober5000, Sandwich, Splinter, Su-tehp, Hippo, CP5670, Terran Emperor, Karajorma, Dekker, McCall, Admiral Wolf, mxlm, RedSniper, Stealth, Black Wolf...

 
Re: Idiosyncrasies of rand()
You don't need to re-seed the RNG each mission, though. It's effectively re-seeding itself every time you draw a random number, you won't get the same draws if you play a mission twice.
The good Christian should beware of mathematicians, and all those who make empty prophecies. The danger already exists that the mathematicians have made a covenant with the devil to darken the spirit and to confine man in the bonds of Hell.

 

Offline The E

  • He's Ebeneezer Goode
  • Moderator
  • 213
  • Nothing personal, just tech support.
    • Steam
    • Twitter
Re: Idiosyncrasies of rand()
I think you don't know how the random number generator works, so here's a brief explanation.
In C, there is only a single rng. It exists over the lifetime of the program, and continues to generate a sequence of random numbers based on a seed. Seeding it once on program start is usually enough; the only reason to reseed it is to ensure some level of reproducibility over multiple iterations of the program.

In this context, this means that reseeding on mission start is pointless, because we've already done everything we can do to ensure nonreproducibility by seeding the rng on startup.
If I'm just aching this can't go on
I came from chasing dreams to feel alone
There must be changes, miss to feel strong
I really need lifе to touch me
--Evergrey, Where August Mourns

 

Offline Galemp

  • Actual father of Samus
  • 212
  • Ask me about GORT!
    • Steam
    • User page on the FreeSpace Wiki
Re: Idiosyncrasies of rand()
In this context, this means that reseeding on mission start is pointless, because we've already done everything we can do to ensure nonreproducibility by seeding the rng on startup.

So what happens if you replay the same mission twice in the same session?
"Anyone can do any amount of work, provided it isn't the work he's supposed to be doing at that moment." -- Robert Benchley

Members I've personally met: RedStreblo, Goober5000, Sandwich, Splinter, Su-tehp, Hippo, CP5670, Terran Emperor, Karajorma, Dekker, McCall, Admiral Wolf, mxlm, RedSniper, Stealth, Black Wolf...

 

Offline The E

  • He's Ebeneezer Goode
  • Moderator
  • 213
  • Nothing personal, just tech support.
    • Steam
    • Twitter
Re: Idiosyncrasies of rand()
Assuming the RNG is not reseeded with a fixed value, you will get a different number stream every time.
If I'm just aching this can't go on
I came from chasing dreams to feel alone
There must be changes, miss to feel strong
I really need lifе to touch me
--Evergrey, Where August Mourns

 

Offline Goober5000

  • HLP Loremaster
  • Moderator
  • 214
    • Goober5000 Productions
Re: Idiosyncrasies of rand()
If the seed you give rand is 0 it should always spit out the same numbers every time. Could it be that your system clock is somehow giving zero as the seed?

If the seed you give rand is 0 it will simply not re-seed the RNG, which means it will retain the seed it had at mission load.  (Which, for single player, is the system time at the point you loaded the mission.)

I suppose it's possible that the clock is somehow returning zero.  Obviously, something is producing the bizarre behavior, whether it's the clock or my sexp logic.  More testing is required.

Quote
We have actually talked about this before.

Indeed.  But whereas in that previous conversation I was making a guess at the implementation, in this one I'm talking about the results of testing.


My question is, why are we reseeding the rng anyway? I can sort of see doing so in order to keep the rng in sync in multiplayer (even though that largely doesn't matter to us, since most of the important rng-related things, like sexps and AI, are handled by the server), but surely a single seed on program start should yield a sufficiently random number sequence?

Your reasoning is correct.  The RNG is seeded at game startup (in game_init()) and that should be sufficient, for single player.  For multiplayer, it makes sense to sync the RNG at the beginning of every mission to ensure that all clients receive the same sequence of values.  However, that block of code re-seeds the RNG for single player too.  That's unnecessary, but theoretically harmless.


But hold the phone, look at this...

Code: [Select]
void __cdecl srand (
    unsigned int seed
    )
{
    _getptd()->_holdrand = (unsigned long)seed;
}


int __cdecl rand (
    void
    )
{
    _ptiddata ptd = _getptd();

    return( ((ptd->_holdrand = ptd->_holdrand * 214013L
        + 2531011L) >> 16) & 0x7fff );
}

That calculation tosses out the least significant 16 bits of the seed.  That means that, as long as you restart the mission within 65,536 seconds (which is more than 18 hours), it is as if you are using the same seed at the beginning of every playthrough.  That would give you the same sequence of numbers!

Am I reading this right?  Does anyone else have an implementation of rand()?

EDIT: Well, apparently a brief search indicates rand() has all sorts of implementation problems, even more than the RAND_MAX of 0x7fff problem that was solved fairly recently.  Looks like I've uncovered another rabbit hole. :p

EDIT2: Looks like I'm not the only one who has noticed this, though those guys were unable to figure out the cause.

EDIT3: I'll investigate this a bit more and then I think I'll make a PR to not seed the RNG anymore on single-player mission load.
« Last Edit: February 25, 2016, 11:06:53 pm by Goober5000 »

 

Offline niffiwan

  • 211
  • Eluder Class
Re: Idiosyncrasies of rand()
If you're feeling really keen, you could replace rand() entirely with a new RNG. I don't think we really need a MT implementation since FSO isn't a high security app, but an LC or Fibonacci should be good enough for gaming purposes.

(aside: Coverity semi-recently marked all uses of rand() in FSO as a potential security issue... and it generally does seem to be a rubbish RNG)
Creating a fs2_open.log | Red Alert Bug = Hex Edit | MediaVPs 2014: Bigger HUD gauges | 32bit libs for 64bit Ubuntu
----
Debian Packages (testing/unstable): Freespace2 | wxLauncher
----
m|m: I think I'm suffering from Stockholm syndrome. Bmpman is starting to make sense and it's actually written reasonably well...

 

Offline jg18

  • A very happy zod
  • 210
  • can do more than spellcheck
Re: Idiosyncrasies of rand()
If you're feeling really keen, you could replace rand() entirely with a new RNG. I don't think we really need a MT implementation since FSO isn't a high security app, but an LC or Fibonacci should be good enough for gaming purposes.

Or if we end up including Boost and want to maintain MSVC 2010 compatibility, we could use Boost::Random instead.

 

Offline The E

  • He's Ebeneezer Goode
  • Moderator
  • 213
  • Nothing personal, just tech support.
    • Steam
    • Twitter
Re: Idiosyncrasies of rand()
boost::random is probably the best option here.
If I'm just aching this can't go on
I came from chasing dreams to feel alone
There must be changes, miss to feel strong
I really need lifе to touch me
--Evergrey, Where August Mourns

 

Offline m!m

  • 211
Re: Idiosyncrasies of rand()
According to the MSDN documentation MSVC 2010 support the new <random> header.

 

Offline Goober5000

  • HLP Loremaster
  • Moderator
  • 214
    • Goober5000 Productions
Re: Idiosyncrasies of rand()
For the purposes of this thread, all we need to do is not seed the RNG every time we load a mission in single player.  I've posted a PR here: https://github.com/scp-fs2open/fs2open.github.com/pull/547

Long-term, yes, it would be nice to have a new RNG, since there are a few problems with rand().  I like the xorshift1024* generators described here and here.