Thread: Doubts about detecting the periodicity of psuedo random functions

  1. #46
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    >> 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;
    }

  2. #47
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Quote Originally Posted by Sebastiani View Post
    >> 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!
    How would that work for a PRNG?
    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

  3. #48
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by CornedBee View Post
    How would that work for a PRNG?
    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....)

  4. #49
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    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

  5. #50
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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 ....

  6. #51
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    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;
    }

  7. #52
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by Sebastiani View Post
    >> 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!
    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);
    //}

  8. #53
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    >> 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;
    }

  9. #54
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    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.

  10. #55
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by Sebastiani View Post
    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.
    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);
    //}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. time Delays and Random functions
    By markphaser in forum C++ Programming
    Replies: 17
    Last Post: 02-20-2006, 07:10 PM
  2. random functions, is it possible?
    By sreetvert83 in forum C++ Programming
    Replies: 8
    Last Post: 09-02-2005, 11:50 AM
  3. How do I restart a random number sequence.
    By jeffski in forum C Programming
    Replies: 6
    Last Post: 05-29-2003, 02:40 PM
  4. Random function's application:Dice Roller
    By angeljicu in forum C Programming
    Replies: 0
    Last Post: 11-02-2002, 05:29 AM
  5. random functions
    By bluehead in forum C++ Programming
    Replies: 5
    Last Post: 11-09-2001, 04:04 AM