>> I agree in theory, but most of the better RNGs have periods which are absurdly long, making it infeasible to test this way.
And of course, some may not be periodic at all!
This is a discussion on Doubts about detecting the periodicity of psuedo random functions within the C++ Programming forums, part of the General Programming Boards category; >> I agree in theory, but most of the better RNGs have periods which are absurdly long, making it infeasible ...
>> I agree in theory, but most of the better RNGs have periods which are absurdly long, making it infeasible to test this way.
And of course, some may not be periodic at all!
Code:#include <cmath> #include <complex> bool euler_flip(bool value) { return std::pow ( std::complex<float>(std::exp(1.0)), std::complex<float>(0, 1) * std::complex<float>(std::atan(1.0) *(1 << (value + 2))) ).real() < 0; }
Perhaps not very random, and it might take an enormous amount of state, but it's probably possible to work something out where you have a "shuffle" of your range, and when you get to the end you reshuffle, and so on. You'd have to take care that your re-shuffles don't repeat, which means you do the same trick at a meta-level, and so on.
(For instance, a small example to see if what I'm saying even makes sense: let's say I have three numbers in my range; all the possible shuffles are 1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2, 3 2 1. I can run them in that order (call that A1), then I can run them in a different order: maybe 1 2 3, then 2 1 3, then 3 1 2, then 1 3 2, then 2 3 1, then 3 2 1 (call that A2). I can rearrange those six shuffles in 6!=720 different ways, so now I have A1 through A720. That pattern of 720*18 numbers we'll call B1 -- I have 720! = a very large number of ways to reshuffle A1 through A720 into B1 through Bsomething large....)
But every time you change the random sequence based on a different random sequence, you're pretty much taking the cross product of two PRNGs, which will prolong the total sequence a lot, but it's still a finite sequence that eventually has to repeat.
All the buzzt!
CornedBee
"There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
- Flon's Law
Didn't say I was changing the random sequence based on another random sequence, or at least I don't think I did. Even if I did, the point (I think) is that I start by shuffling three things around, then six things (the six groups of three), then 720 things (the 720 groups of the six groups of three), then ....
You wouldn't necessarily have to shuffle anything. You would just need a set of transformations that could maintain an "out of sync" state indefinitely.
Code:#include <cmath> #include <complex> bool euler_flip(bool value) { return std::pow ( std::complex<float>(std::exp(1.0)), std::complex<float>(0, 1) * std::complex<float>(std::atan(1.0) *(1 << (value + 2))) ).real() < 0; }
All PRNGs are periodic. There are a finite amount of bits of memory, which means there are a finite number of states. So any PRNG will eventually either stop functioning (enter an invalid state), or come back to a state it has been in before, at which point it repeats itself.
Only on a machine with infinite memory can you have a PRNG which never repeats itself. I think people have invented several non-periodic PRNGs but they are not useful because they require infinite memory.
Code://try //{ if (a) do { f( b); } while(1); else do { f(!b); } while(1); //}
>> All PRNGs are periodic. There are a finite amount of bits of memory, which means there are a finite number of states. So any PRNG will eventually either stop functioning (enter an invalid state), or come back to a state it has been in before, at which point it repeats itself. Only on a machine with infinite memory can you have a PRNG which never repeats itself. I think people have invented several non-periodic PRNGs but they are not useful because they require infinite memory.
You're assuming that it all depends on memory, but in fact it is has more to do with symmetry than anything else. Most transformations, when coupled together, tend to generate repetitious and mutually reinforcing cycles. But if you could create a sufficently imbalanced system the sequence could concievably mutate without end. It's a very difficult problem, of course, which explains why memory is used to deal with this sort of thing, but I'm convinced that it is possible.
I could be wrong, though.
Code:#include <cmath> #include <complex> bool euler_flip(bool value) { return std::pow ( std::complex<float>(std::exp(1.0)), std::complex<float>(0, 1) * std::complex<float>(std::atan(1.0) *(1 << (value + 2))) ).real() < 0; }
How do you intend to make or use a prng that doesn't have to store anything (no state)? I realize you're not really saying that, but that's really the only notion I have coming from what you've posted.
And sufficiently imbalanced might as well mean "totally random" because I don't think arithmetic works that way. I'm tired, but not that tired.
How do you intend to create a state within the machine that is NOT represented by a configuration of bits? The state space is enormous, but FINITE.
I suppose you could design your PRNG to take advantage of memory errors caused by cosmic rays, but then, you could only ever switch to a state other than what the PRNG would have switched to, which is simply a "jump" in the cycle, not a move to another cycle entirely.
And if you're doing weird stuff like using cosmic rays, you probably ought to be a using a hardware RNG based on Johnson noise, or the nuclear breakdown of an unstable isotope, or something like that.
Code://try //{ if (a) do { f( b); } while(1); else do { f(!b); } while(1); //}