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

Predicting the next Math.random() in Java

franklinta.com

Post reply on HN
Print view View original

51–58 of 58 posts

Re: Predicting the next Math.random() in Java

#51

Post by dspillett »

sehugg wrote: post #34
SeanLuke wrote: post #24

Earlier quoted context omitted.

> Math.random() is simply a super-fast decent RNG Actually, java.util.Random is a horrible, horrible RNG. Its least significant bit (for example) is grotesquely nonrandom. See http://www.alife.co.uk/nonrandom/ for a wonderful demonstration of its awfulness. There are other serious bugs in java.util.Random which Sun, er, Oracle, has steadfastly refused to fix or revise for a decade now due to concerns about "backward…

An appropriate Xorshift generator is likely much better (and faster) than java.util.Random: http://xorshift.di.unimi.it/ I've used them to improve my hashing collision rate.

If you want true random, then many CPUs/SoCs have environment based TRNGs. The SoC used in the rPi can emit half a million random bits per second (that passed the statistical tests I threw them through), and many Intel chips have an RNG in them now (though I don't know if it is as easy to access in userland as the rPi's is).

If you need more than your current CPU provides then you could chain a bunch of them together, or pick a good PRNG for your main source and simply reseed that on a regular basis with the output of your TRNG.

There are some concerns with generators like those in the rPi as they are not documented, so you have no way of knowing exactly how good they are or if the manufacturer has somehow arranged for there to be some predictability - but if you are that paranoid you need to be building your own generator from scratch anyway!

Re: Predicting the next Math.random() in Java

#52

Post by TheLoneWolfling »

michaelt wrote: post #43
SeanLuke wrote: post #37

Earlier quoted context omitted.

> Backward compatibility in a RNG is actually rather important, weirdly enough. For example, anything that uses deterministic seeds for repeatability of procedural generation or optimization. (Read: Minecraft, among other more important things). This seems like a very, very bad thing to rely on. Other than Java, how many other languages have guarantees in generator determinism from version to version as part of the l…

Any language that allows the PRNG to be manually seeded, presumably? I mean, if manually seeding the PRNG doesn't produce a deterministic result, you wouldn't make it part of the API.

Counterexample: Python [1]

[1] http://stackoverflow.com/a/19179886/1814881

Re: Predicting the next Math.random() in Java

#53

Post by TheLoneWolfling »

dspillett wrote: post #51
sehugg wrote: post #34

Earlier quoted context omitted.

An appropriate Xorshift generator is likely much better (and faster) than java.util.Random: http://xorshift.di.unimi.it/ I've used them to improve my hashing collision rate.

If you want true random, then many CPUs/SoCs have environment based TRNGs. The SoC used in the rPi can emit half a million random bits per second (that passed the statistical tests I threw them through), and many Intel chips have an RNG in them now (though I don't know if it is as easy to access in userland as the rPi's is). If you need more than your current CPU provides then you could chain a bunch of them together…

The problem with this is that it's not ubiquitous, and there are multiple different implementations.

There's a reason why OSes provide a HAL.

Re: Predicting the next Math.random() in Java

#54

Post by TheLoneWolfling »

MichaelGG wrote: post #29
UnoriginalGuy wrote: post #11

Earlier quoted context omitted.

By that logic nothing should ever be called random (in any context). There are things we can measure but don't understand the source of the entropy, but they aren't random we just haven't figured out the source yet. Most things we consider random are quantifiable and predictable with enough data (be it nature or computers). Plus there are several definitions of the term "random" (English) which are in-line with the p…

I thought quantum processes were truly random.

As far as we know. That isn't the same thing as "it is".

If you assume that quantum processes are truly random, there are a bunch of ways for a computer to generate truly random noise - the easiest class being shot noise (connect a computer to a good camera in an almost pitch-black enclosure, or send a small current through a diode), but there are others.

Re: Predicting the next Math.random() in Java

#55

Post by TheLoneWolfling »

prawks wrote: post #49
cdwhite wrote: post #40

Earlier quoted context omitted.

Also, when you're writing scientific code (Monte Carlo simulations, for example, or disordered systems), the folk wisdom is that you must to keep track of what seed you used. I've never had to use these records myself, but I can image wanting to go back and reproduce exactly the same calculation, for (e.g.) debugging or verifying new code. Now you think about resurrecting some previous grad student's code that only w…

Couldn't you solve this by tracking the version of Java (for example) used initially to develop the simulation?

Until a required library (or Java itself) has a security flaw and the new version does not support that version of Java.

Re: Predicting the next Math.random() in Java

#56

Post by lutusp »

eru wrote: post #39
lutusp wrote: post #12

Earlier quoted context omitted.

> Real random numbers are useless because everything follow some distribution. First, real random numbers are quite valuable. Second, yes, all numerical sequences follow a distribution, but one of those distributions is called the "normal distribution", and I think you may be able to guess what that refers to. > Actually random generators in programming languages should be called pseudorandom to avoid confusions. It…

Why is the normal distribution important here? (In programming, people often start from the uniform distribution, don't they?)

> Why is the normal distribution important here?

There may be a terminological confusion at work here. A normal or uniform number shows no internal pattern:

http://en.wikipedia.org/wiki/Normal_number

Quote: "In mathematics, a normal number is a real number whose infinite sequence of digits in every base b[1] is distributed uniformly in the sense that each of the b digit values has the same natural density 1/b, also all possible b^2 pairs of digits are equally likely with density b^−2, all b^3 triplets of digits equally likely with density b^−3, etc."

There are also pseudorandom generators whose purpose it is to generate results that agree with a normal or Gaussian distribution, for particular purposes.

http://www.design.caltech.edu/erik/Misc/Gaussian.html

Quote: "This note is about the topic of generating Gaussian pseudo-random numbers given a source of uniform pseudo-random numbers."

The problem here is that a normal number shows a uniform distribution of its digits among the possible values, and the term normal distribution is sometimes used to describe this outcome.

> In programming, people often start from the uniform distribution, don't they?

Yes, and as set out above, this starting point may be described in a confusing way.

Re: Predicting the next Math.random() in Java

#57

Post by cdwhite »

prawks wrote: post #49
cdwhite wrote: post #40

Earlier quoted context omitted.

Also, when you're writing scientific code (Monte Carlo simulations, for example, or disordered systems), the folk wisdom is that you must to keep track of what seed you used. I've never had to use these records myself, but I can image wanting to go back and reproduce exactly the same calculation, for (e.g.) debugging or verifying new code. Now you think about resurrecting some previous grad student's code that only w…

Couldn't you solve this by tracking the version of Java (for example) used initially to develop the simulation?

Yeah, and this is why I'm very careful about recording the versions I use for a calculation (version number and/or commit for the language, library version numbers, and commit for my code). The thing is, that's not your first step: the first step is to try and get the thing to run on whatever Java (/Julia/Matlab/Mathematica/Fortran) you have installed. If that doesn't work, there are a thousand things it could be (improper usage, some missing file you had no clue you might need, change in libraries, change in OS/distro/CPUarch, out-of-memory with a new set of parameters); installing an old version of your language and trying it on that is not necessarily easy, and certainly not the first bug-finding step.

Philip Guo (pgbovine) addressed many of these problems in his thesis work, on Burrito (http://www.pgbovine.net/burrito.html ) and CDE (http://www.pgbovine.net/cde.html ). Both of these look very cool, but I've never managed to get over the hump and actually start playing with them.

At this point I should note that I'm actually in favor of fixing a bad standard-library PRNG---I just think it's important to understand (a) what could break, and (b) why users might be unhappy about the breakage. This isn't quite a Chesterton's Fence sort of situation, but it's similar in spirit.

Re: Predicting the next Math.random() in Java

#58

Post by eru »

lutusp wrote: post #56
eru wrote: post #39

Earlier quoted context omitted.

Why is the normal distribution important here? (In programming, people often start from the uniform distribution, don't they?)

> Why is the normal distribution important here? There may be a terminological confusion at work here. A normal or uniform number shows no internal pattern: http://en.wikipedia.org/wiki/Normal_number Quote: "In mathematics, a normal number is a real number whose infinite sequence of digits in every base b[1] is distributed uniformly in the sense that each of the b digit values has the same natural density 1/b, also a…

I have never seen the term normal distribution used in connection with anything but the Gaussian normal distribution. Especially not in connection with normal numbers. Can you point to some examples of people using this sense?
Post reply on HN