Proposal: web-based random state scrambles for 3x3

[Stefan]

Yeah yeah yeah. It doesn't matter *what* you compute, some physics simulation or artificial number playing or whatever. Is it deterministic or not? If it's deterministic and has limited memory, eventually it must cycle. Only if you have infinite memory or a nondeterministic source, you can evade cycling.

 

[Stefan]

So working precision never changes across machines?

It really shouldn't. Unless you're talking about hardware with the express purpose of being nondeterministic (I've read about some cryptography chips, they might do something like that). Other than that, standards are in place because you want your program to run properly on all computers, so you don't want different computers to behave differently. This for example is the main standard for floating point calculations, I think:
http://en.wikipedia.org/wiki/IEEE_754-2008

As in, take a double-pendulum, given some initial conditions.

If your pendulum is a real physical object, then you can probably get true randomness from it. If you just deterministically simulate it on the computer, then you're no better than other PRNGs, just different, and quite possibly worse.

 

[JBCM627]

If it's deterministic and has limited memory, eventually it must cycle.

Pi should never cycle, and you can find the nth digit using a recursive formula. I think that is a sufficient counterpoint, unless I missed something.

Edit: Ah, I think I did... x_n blows up in terms of memory usage.

 

[JBCM627]

As in, take a double-pendulum, given some initial conditions.

If your pendulum is a real physical object, then you can probably get true randomness from it. If you just deterministically simulate it on the computer, then you're no better than other PRNGs, just different, and quite possibly worse.

Alright, I agree... Although I'd be interested to see what the period would be for what I suggested.

 

[Stefan]

Edit: Ah, I think I did... x_n blows up in terms of memory usage.

That's somewhat the problem, yes. The state of this generator is the pair of n and x_n. And with the formula, you can get from state (n-1, x_n-1) to state (n, x_n). It's less important how "large" each state is (it's an encoding issue anyway), what matters is that with finite memory, you can only encode and distinguish a finite number of states. If your computer has 1 TB memory, it only has 2^(2^43) different possible states. A huge number, but still finite. So in your sequence of (n, x_n) states for the Pi computation, eventually you'll run out of new states your computer can possibly be in, you'll be in a previous state again, and revisit the states you visited from there the first time. Welcome to the cycle.

 

[Stefan]

Although I'd be interested to see what the period would be for what I suggested.

You'd need to define it properly first. And I suspect it'll be less random than "normal" PRNGs, and less memory efficient, too. You can get longer periods simply by using more memory. Mersenne Twister for example has a period of length (2^19937)-1 using only 19968 bits for its state. I think that's quite efficient, and that's because it was intentionally *made* that way. I doubt some physical simulation would use the memory nearly as efficiently.

 

[JBCM627]

Although I'd be interested to see what the period would be for what I suggested.

You'd need to define it properly first. And I suspect it'll be less random than "normal" PRNGs, and less memory efficient, too. You can get longer periods simply by using more memory. Mersenne Twister for example has a period of length (2^19937)-1 using only 19968 bits for its state. That's almost perfectly efficient, and that's because it was intentionally *made* that way. I doubt some physical simulation would use the memory nearly as efficiently.

Yeah, I see your point.

A double-pendulum would require information about 2 distinct angles for a state, and the rate of change of those angles, so 4 pieces of information, although this can technically be reduced to 3. anyway, trivial example of an unreachable state (assuming you don't start with it): the pendulum dangling straight down (angular velocity of both arms are 0, and angles don't change).

A naive implementation of a double-pendulum simulation would probably be relatively inefficient in terms of the amount of memory a state takes up. But a good implementation could presumably be almost perfectly efficient.

 

[Stefan]

Another problem of such a simulation is that it might be very hard to analyze how good it is. How do you determine the period length, for example? You can't just test it and count. Well you can if it's short, but then it's no good anyway. The systematic way PRNGs like Mersenne Twister are created makes the analysis possible. In that sense, "chaotic" is actually *bad*.

A naive implementation of a double-pendulum would probably be relatively inefficient in terms of the amount of memory a state takes up. But a good implementation could presumably compress this to make it almost perfectly efficient.

Nah, probably not. Remember you're trying to create randomness. Good randomness doesn't compress well. And bad randomness is, well, bad.

 

[JBCM627]

A naive implementation of a double-pendulum would probably be relatively inefficient in terms of the amount of memory a state takes up. But a good implementation could presumably compress this to make it almost perfectly efficient.

Nah, probably not. Remember you're trying to create randomness. Good randomness doesn't compress well. And bad randomness is, well, bad.

By this, I meant taking 4 parameters to 3. A double-pendulum also only has 2 degrees of freedom, so I think you can compress it to 2. But without creating a simple implementation, I'm not sure how efficient this would be.

I guess I should look into exactly how MT works more.

 

[Stefan]

A naive implementation of a double-pendulum would probably be relatively inefficient in terms of the amount of memory a state takes up. But a good implementation could presumably compress this to make it almost perfectly efficient.

Nah, probably not. Remember you're trying to create randomness. Good randomness doesn't compress well. And bad randomness is, well, bad.

By this, I meant taking 4 parameters to 3. A double-pendulum also only has 2 degrees of freedom, so I think you can compress it to 2. But without creating a simple implementation, I'm not sure how efficient this would be.

I think we're talking about different things here.

Imagine each of your parameters is a 6656-bits floating point value. Then with 3 such parameters you use the same amount of state memory as Mersenne Twister. Now... if your simulation's periods are longer than MT's (2^19937)-1 period, it's more memory-efficient, if they're shorter, it's less memory-efficient. Relating the period length to the amount of memory used to represent the state, I mean. And I suspect yours would have differently long periods including quite short ones. And again, probably hard to analyze.

This is worth reading: http://en.wikipedia.org/wiki/PRNG#Periodicity
Period of (2^n)−1 using n bits apparently gets achieved by some PRNGs, and that's almost perfect (only a single state going to waste). You're not going to achieve that with a side product of a physics simulation that by itself doesn't care about maximizing the period length.

 

[Stefan]

Period of (2^n)−1 using n bits apparently gets achieved by some PRNGs, and that's almost perfect (only a single state going to waste). You're not going to achieve that with a side product of a physics simulation that by itself doesn't care about maximizing the period length.

In order to be that efficient, your pendulum, once started, would have to go through every single state it could possibly be in (except one state, standing still).

 

[qqwref]

This is worth reading: http://en.wikipedia.org/wiki/PRNG#Periodicity
Period of (2^n)−1 using n bits apparently gets achieved by some PRNGs, and that's almost perfect (only a single state going to waste).

I'd say that IS perfect, actually. You don't really want a period of exactly 2^n because then there could very well be a clear pattern every 2^k outputs (for k < n). But if the period is (2^n)-1 you can choose n such that this number has very few nontrivial factors (if any at all!). For instance, as you know, (2^19937)-1, the cycle length of the Mersenne Twister, is a Mersenne prime, so the PRNG itself is a lot stronger and looks more chaotic.

 

[Stefan]

You don't really want a period of exactly 2^n because then there could very well be a clear pattern every 2^k outputs (for k < n).

Could be, but doesn't have to be, so I don't see how that makes me want to waste a state. And MT could also have a clear pattern every 2^k outputs virtually all the time (except once, somewhere in its long period where we're very unlikely to ever be).