Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

When good pseudorandom numbers go bad

blog.djnavarro.net

Post reply on HN
Print view View original

31–39 of 39 posts

Re: When good pseudorandom numbers go bad

#31

Post by hansvm »

thaumasiotes wrote: post #8
AlotOfReading wrote: post #2

Most people don't really care about numerical stability or correctness. What they usually want is reproducibility, but they go down a rabbit hole with those other topics as a way to get it, at least in part because everyone thinks reproducibility is too slow. It was 20 years ago, but that's not the case today. The vast majority of hardware today implements 754 reproducibly if you're willing to stick to a few basic pr…

I don't actually understand why you'd want reproducibility in a statistical simulation. If you fix the output, what are you learning? The point of the simulation is to produce different random numbers so you can see what the outcomes are like... right? Let's say I write a paper that says "in this statistical model, with random seed 1495268404, I get Important Result Y", and you criticize me on the grounds that when y…

- It eliminates one way of forging results. Without stating the seed, people could consistently fail to reproduce your results and you could always have "oops, guess I had a bad seed" as an excuse. You still have to worry about people re-running the simulation till the results look good, but that's handled via other mechanisms.

- Many algorithms are vastly easier to implement stochastically than deterministically. If you want to replay the system (e.g., to locally debug some production issue), you need those "stochastic" behaviors to nonetheless be deterministic.

- If you're a little careful with how you implement deterministic randomness, you can start to ask counterfactual questions -- how would the system have behaved had I made this change -- and actually compare apples to apples when examining an experimental run.

Even in your counterexample, the random seeds being reproducible and published is still important. With the seed and source published, now anyone can cheaply verify the issue with the simulation, you can debug it, you can investigate the proportion of "bad" seeds and suss out the error bounds of the simulation, etc.

Re: When good pseudorandom numbers go bad

#32

Post by skybrian »

hansvm wrote: post #26
somat wrote: post #19

This is a perpetual problem in computer science, people want a hash function, then decide that the random function very nearly does what they want. then use the random function as a hash function and are dumbfounded that it turns out there is no hard specification for how it works internally. The random function has no guarantee of result across versions, system, time. Hell I would even be harsh enough to say that an…

> hash is the deterministic function In most languages and libraries, hashing is still only deterministic within a given run of the program. Authors generally have no qualms "fixing" implementations over time, and some systems introduce a salt to the hash intentionally to help protect web programmers from DOS "CVEs". If you want reproducible RNG, you need to write it yourself. System's based on Jax's notion of splitt…

I don’t think you need to write it yourself, since there are also libraries that implement specific algorithms for pseudo-random number generators, if if you’re worried, you could pin or vendor the dependency.

But it’s true that if the algorithm isn’t specified then the implementation is free to change it, and probably should change it sometimes, to ensure calls don’t depend on it being fixed.

(Reproducibility is normally about what happens when you use the same version of everything.)

Re: When good pseudorandom numbers go bad

#33

Post by AlotOfReading »

aragilar wrote: post #24
AlotOfReading wrote: post #2

Most people don't really care about numerical stability or correctness. What they usually want is reproducibility, but they go down a rabbit hole with those other topics as a way to get it, at least in part because everyone thinks reproducibility is too slow. It was 20 years ago, but that's not the case today. The vast majority of hardware today implements 754 reproducibly if you're willing to stick to a few basic pr…

I mean, if you get different results for the same input on the same machine with the same code, I'd be concerned. But that's not that interesting really, as you actually care that you get the right answer, not the same answer (otherwise you get https://en.wikipedia.org/wiki/Oil_drop_experiment ). Stability and correctness will get you closer to a right answer than demanding you get the same answer to someone else who…

I don't think it's usually meaningful to discuss the idea of a "correct answer" without doing the traditional numerical analysis stuff. Realistically, we don't need to formalize most programs to that degree and provide precise error bounds either.

To give a practical example, I work on autonomous vehicles. My employer runs a lot of simulations against the vehicle code to make sure it meets reasonable quality standards. The hardware the code will be running on in the field isn't necessarily available in large quantities in the datacenter though. And realistically I'm not going to be able to apply numerical analysis to thousands of functions and millions of test cases to determine what the "correct" answer is in all cases. Instead, I can privilege whatever the current result is as "correct enough" and ensure the vehicle hardware always gets the same results as the datacenter hardware, then leverage the many individual developers merging changes to review their own simulation results knowing they'll apply on-road. This is a pretty universal need for most software projects. If I'm a frontend dev, I want to know that my website will render the same on my computer as the client's. If I'm a game engine dev, I want to ensure that replays don't diverge from the in-game experience. If I'm a VFX programmer, I want to ensure that the results generated on the artist's workstation looks the same as what comes out of the render pipeline at the end. Etc.

All of these applications can still benefit from things like stability, but the benefits are orthogonal to reproducibility.

Re: When good pseudorandom numbers go bad

#34

Post by FooBarBizBazz »

somat wrote: post #19

This is a perpetual problem in computer science, people want a hash function, then decide that the random function very nearly does what they want. then use the random function as a hash function and are dumbfounded that it turns out there is no hard specification for how it works internally. The random function has no guarantee of result across versions, system, time. Hell I would even be harsh enough to say that an…

The article has absolutely nothing to do with "hashes vs. PRNGs". Literally nothing. It's all about the linear algebra and floating point operations that happen (in this case) to be used to transform those numbers. It has nothing to do with PRNGs.

Also, PRNG and hash functions are extremely similar, and there's no reason why one should be deterministic and the other not. They're both built out of simple integer and bit operations. If a certain PRNG is implementation-defined, that's a detail of the specific (possibly standard) library you've chosen; it's nothing fundamental.

Re: When good pseudorandom numbers go bad

#35

Post by dzaima »

AlotOfReading wrote: post #27
dzaima wrote: post #22

Earlier quoted context omitted.

The only case I recall of denormals specifically being improperly handled is 32-bit ARM NEON; and indeed clang and gcc just don't use it without -ffast-math. NaNs indeed can get different bit patterns, but my point was that, given that you need to explicitly bit-reinterpret the NaN to have that affect anything, that can't really affect most code. I guess perhaps blindly hashing a NaNs bits? (that of course goes under…

The Intel compiler used to (and possibly still does) set the SSE FTZ bit by default, leading to a situation where two different FPUs on the same chip (x87 and SSE) had different FP configs. I was indeed thinking of ARM though. I've come across chips with both VFP and NEON where they're handled differently. For NaNs, if we're being strict then you don't need to reach that far. Here's one example from LLVM: https://git…

Intel compilers default to -ffast-math wholesale, so they're just entirely broken: https://godbolt.org/z/18xoEf5Gf

Those LLVM issues are unrelated afaict - the former is high-level IR optimizations that just result in non-reproducible NaN bit patterns (and the things that wouldn't be just NaN bit patterns I can't even repro on the reported llvm 8.0 or any other version I tested)

The latter though is indeed a proper compiler bug, min/max are an awful mess... didn't know that the ARM fminnm/fmaxnm that were that funky though, caring about sNaN vs qNaN... makes them essentially unusable for compilers (not even useful in known-not-NaN contexts, as then fmin/fmax are equivalent)

Re: When good pseudorandom numbers go bad

#36

Post by thaumasiotes »

hansvm wrote: post #31
thaumasiotes wrote: post #8

Earlier quoted context omitted.

I don't actually understand why you'd want reproducibility in a statistical simulation. If you fix the output, what are you learning? The point of the simulation is to produce different random numbers so you can see what the outcomes are like... right? Let's say I write a paper that says "in this statistical model, with random seed 1495268404, I get Important Result Y", and you criticize me on the grounds that when y…

- It eliminates one way of forging results. Without stating the seed, people could consistently fail to reproduce your results and you could always have "oops, guess I had a bad seed" as an excuse. You still have to worry about people re-running the simulation till the results look good, but that's handled via other mechanisms. - Many algorithms are vastly easier to implement stochastically than deterministically. If…

> It eliminates one way of forging results. Without stating the seed, people could consistently fail to reproduce your results and you could always have "oops, guess I had a bad seed" as an excuse.

Why does this matter? If people consistently fail to get results similar to yours by using different seeds, your results are invalid whether or not you made them up. And if people consistently do get results similar to yours with different seeds, your results are valid whether or not you made them up. No?

> Even in your counterexample, the random seeds being reproducible and published is still important.

> you can investigate the proportion of "bad" seeds and suss out the error bounds of the simulation

How does publishing seeds help with that? You do that by examining different seeds. If you know what seeds were used in the paper, this process doesn't change in any way.

Re: When good pseudorandom numbers go bad

#37

Post by coolcase »

pfortuny wrote: post #21
coolcase wrote: post #12

Earlier quoted context omitted.

Thanks! So machine differences in their FP units drives the entropy, and the code doesn't handle that when picking eigenvectors?

Implementations of IEEE-754 can differ between machines, and the order of operations in a library/compiled function can also be different. It is not entropy, it is the nature of floating-point arithmetic.

Thanks. So sounds like the same machine should run the same calculations and get the same results each time, but differences may appear between machines.

Re: When good pseudorandom numbers go bad

#38

Post by aragilar »

AlotOfReading wrote: post #33
aragilar wrote: post #24

Earlier quoted context omitted.

I mean, if you get different results for the same input on the same machine with the same code, I'd be concerned. But that's not that interesting really, as you actually care that you get the right answer, not the same answer (otherwise you get https://en.wikipedia.org/wiki/Oil_drop_experiment ). Stability and correctness will get you closer to a right answer than demanding you get the same answer to someone else who…

I don't think it's usually meaningful to discuss the idea of a "correct answer" without doing the traditional numerical analysis stuff. Realistically, we don't need to formalize most programs to that degree and provide precise error bounds either. To give a practical example, I work on autonomous vehicles. My employer runs a lot of simulations against the vehicle code to make sure it meets reasonable quality standard…

I agree, if you know your requirements are such that you don't care about the correct answer, but any good enough consistent answer will do (e.g. the fast inverse square root), then doing the full numerical analysis is not worth your while (though I'd still do some back of the envelope estimates just to make sure the answer is in the "good enough" category and not in the "wtf" category). The issue is when there's libraries involved (especially more generic libraries are involved), typically they don't document what assumptions they are making, so unless you are very clear about the limitations of your code, people will use the library inappropriately (and I've seen some really bad implementations, even from people claiming that their code can be used for more traditional numerical work).

To me it's the same as whether your default random number generator is a CSPRNG or just a PRNG, and generally it's safer for all involved if it's the former. The latter should exist, just with lots of warnings and guidance.

Re: When good pseudorandom numbers go bad

#39

Post by saagarjha »

aragilar wrote: post #25
saagarjha wrote: post #16

Earlier quoted context omitted.

You can definitely do operations in a reproducible way (assuming you do the reductions in a defined order) but, yeah, you might lose some performance. Unfortunately the ML people seem to pick better performance over correctness basically every time :(

But is that correctness or reproducibility? The latter isn't important as the former.

I don't think they care about either
Post reply on HN