C#•8mo ago

Feeding Random into itself - does it "corrupt the randomness"?

If I am to reinitialize an instance of System.Random after every .NextDouble() using the return value as a seed, would that make the randomness worse in some way? I want to do this in order to be able to persist and unpersist a System.Random, via knowing the seed at every step of the way.

45 Replies

Angius•8mo ago

Worse? Probably not. Creating a bunch of Random instances is more likely to make randomness worse. Can't you just use a single Random instance, with a single seed, and reuse that? I'd maybe generate, like, 100k values using this method of yours and check if they follow normal distribution

ACiDCA7•8mo ago

i understood his footnote like he wants the randomfunction to be deterministic i guess for replayability?

Joreyk ( IXLLEGACYIXL )•8mo ago

if you create a random on the approximately same time without special seed it will yields the exact same random values as it has teh same seed: the time

Angius•8mo ago

You just need one seeded instance for it to be deterministic

VladOP•8mo ago

this, yeah the point is to be able to save and resume the randomness, like in a game's save file for instance

Angius•8mo ago

Save the seed, then?

VladOP•8mo ago

I don't think you can extract the seed

Jimmacle•8mo ago

you start with a known one

Angius•8mo ago

VladOP•8mo ago

yes, but as soon as you random once, the seed is now different

Jimmacle•8mo ago

Angius•8mo ago

Jimmacle•8mo ago

that's not what a seed is

VladOP•8mo ago

I misspoke, let me rephrase

Angius•8mo ago

You create an instance of Random with a given seed. You reuse that instance everywhere It's guaranteed to be deterministic for the same seed

VladOP•8mo ago

every time you call next you are now "1 random pull" past the initial seed, therefore even if you use the same seed unless you keep track of how many randoms you pulled you cannot resume back to the same state

Jimmacle•8mo ago

so you need to keep track of how many numbers you've generated

VladOP•8mo ago

hmm I guess that could work, but wouldnt calling Next 1000 times be kind of slow?

Jimmacle•8mo ago

1000? probably instantaneous

VladOP•8mo ago

I mean as time goes on "loading the save" would get slower and slower

Jimmacle•8mo ago

or you could look into persisting the Random internals

VladOP•8mo ago

alright, well I might do that then

Angius•8mo ago

Save the generated values in the save ¯\_(ツ)_/¯

VladOP•8mo ago

I did look into it, but it seems they've changed a couple times over the years and I rather not depend on undocumented behavior not sure what you mean

Angius•8mo ago

Instead of regenerating the values from the seed, save them in the savegame That way you won't have to skip 1000 random results

Jimmacle•8mo ago

that doesn't help him

VladOP•8mo ago

ah, you misunderstand - the idea is to have the next random be the same when you reload

Angius•8mo ago

Ah, right I misunderstood, then

VladOP•8mo ago

Jimmacle•8mo ago

the goal is to persist Random so when the game is loaded again it's as if it was never quit at all

VladOP•8mo ago

I'll just keep track of how many randoms were pulled and hope it never becomes a problem xd thanks for the help ZZZZ and Jimm

Jimmacle•8mo ago

personally i'd just assume the implementation of random won't change, the existing changes were made backwards compatible anyway or implement your own random class that you can control the implementation of

VladOP•8mo ago

that was going to be my next try 😄

Jimmacle•8mo ago

i'm sure there are a pile of PRNG algorithms out there that you can copy and paste

VladOP•8mo ago

easier to get that past code review than reflection of random underscore properties

Jimmacle•8mo ago

looks like the current Random uses a port of http://prng.di.unimi.it/xoshiro256starstar.c

Unknown User•8mo ago

Message Not Public

Angius•8mo ago

Benchmarked it, btw:

| Method      | Seed        | Mean          | Error         | StdDev        |
|------------ |------------ |--------------:|--------------:|--------------:|
| One         | -2147483648 |      6.185 ns |     0.3347 ns |     0.9710 ns |
| Hundred     | -2147483648 |  1,011.573 ns |    21.5309 ns |    63.1465 ns |
| Thousand    | -2147483648 |  9,059.311 ns |    58.3614 ns |    45.5647 ns |
| TenThousand | -2147483648 | 92,219.667 ns | 1,793.3376 ns | 1,993.2900 ns |
| One         | 2147483647  |      5.445 ns |     0.2605 ns |     0.7516 ns |
| Hundred     | 2147483647  |    959.814 ns |    19.1163 ns |    47.2508 ns |
| Thousand    | 2147483647  |  8,902.830 ns |   172.3596 ns |   143.9281 ns |
| TenThousand | 2147483647  | 88,445.468 ns |   785.1084 ns |   612.9610 ns |

| Method      | Seed        | Mean          | Error         | StdDev        |
|------------ |------------ |--------------:|--------------:|--------------:|
| One         | -2147483648 |      6.185 ns |     0.3347 ns |     0.9710 ns |
| Hundred     | -2147483648 |  1,011.573 ns |    21.5309 ns |    63.1465 ns |
| Thousand    | -2147483648 |  9,059.311 ns |    58.3614 ns |    45.5647 ns |
| TenThousand | -2147483648 | 92,219.667 ns | 1,793.3376 ns | 1,993.2900 ns |
| One         | 2147483647  |      5.445 ns |     0.2605 ns |     0.7516 ns |
| Hundred     | 2147483647  |    959.814 ns |    19.1163 ns |    47.2508 ns |
| Thousand    | 2147483647  |  8,902.830 ns |   172.3596 ns |   143.9281 ns |
| TenThousand | 2147483647  | 88,445.468 ns |   785.1084 ns |   612.9610 ns |

Decrypted•8mo ago

I got resumable rand class somewhere, let me try to find it

Angius•8mo ago

Safe to assume that no, generating a lot of random values won't be an issue

ACiDCA7•8mo ago

quick calculation even if you generate 60 randoms a second for 50h based on the benchmark above its just around 0.1s to calculate them from new in one batch

Decrypted•8mo ago

public class Rng
{
    public byte[] State => _state;

    private byte[] _state = new byte[32];

    public Rng(int seed)
    {
        var rand = new Random(seed);
        
        // fill state from seed
        rand.NextBytes(_state);
    }

    public Rng(byte[] state)
    {
        _state = state;
    }

    public int Next()
    {
        // Hash new state
        if (!SHA256.TryHashData(_state, _state, out _))
        {
            throw new InvalidOperationException();
        }

        var bigInt = new BigInteger(_state);
        
        return (int)(bigInt % int.MaxValue);
    }
}

public class Rng
{
    public byte[] State => _state;

    private byte[] _state = new byte[32];

    public Rng(int seed)
    {
        var rand = new Random(seed);
        
        // fill state from seed
        rand.NextBytes(_state);
    }

    public Rng(byte[] state)
    {
        _state = state;
    }

    public int Next()
    {
        // Hash new state
        if (!SHA256.TryHashData(_state, _state, out _))
        {
            throw new InvalidOperationException();
        }

        var bigInt = new BigInteger(_state);
        
        return (int)(bigInt % int.MaxValue);
    }
}

This uses SHA256 to hash the state on top of itself You can then persist the 32 byte state and resume from it when required. Not sure if this is the best way to do this. I don't even know if the bigInt % int.MaxValue is safe operation for converting to int..

Jimmacle•8mo ago

without actually benchmarking it that looks slow i'd also want to see some proof that this generates a good distribution of random numbers since you're attempting to use SHA256 as a PRNG algorithm definitely better to just use a proper PRNG implementation in a way that you have access to the internal state to persist

| Method     | Mean        | Error     | StdDev    |
|----------- |------------:|----------:|----------:|
| Random100k |    698.7 us |   9.77 us |  12.71 us |
| Rng100k    | 25,313.9 us | 391.05 us | 346.65 us |

| Method     | Mean        | Error     | StdDev    |
|----------- |------------:|----------:|----------:|
| Random100k |    698.7 us |   9.77 us |  12.71 us |
| Rng100k    | 25,313.9 us | 391.05 us | 346.65 us |

distribution aside, that implementation is 36 times slower than plain Random

VladOP•8mo ago

damn thanks for taking the time to benchmark it

Jimmacle•8mo ago

i'd just copy the implementation from https://source.dot.net/#System.Private.CoreLib/src/libraries/System.Private.CoreLib/src/System/Random.Xoshiro256StarStarImpl.cs,cf33c3a42d4a8ee6 and tweak it to your needs or see https://prng.di.unimi.it/ for all the generators like it in case a different algorithm is more appropriate

Gaming

Programming

Feeding Random into itself - does it "corrupt the randomness"?