4 ms·

Suppose you generated two permutations, one using true random numbers and the other using pseudo-random numbers. Now you have two fixed permutations. The cycles

Suppose you generated two permutations, one using true random numbers and the other using pseudo-random numbers. Now you have two fixed permutations. The cycles in both will obey the probabilities about such cycles, unless the pseudo-random generator was poor. But Romu generators pass PractRand, so their high quality numbers and cycles will obey those probabilities. But you brought up a good point: Each kind of Romu generator relies on one permutation and thus one set of cycles. The paper needs to discuss that fact. Thanks for pointing that out. Important request: Please post every specific error in reasoning or math you saw in the paper. You said there are several. I expect that you are not like many internet posters who reply with vagueness or discouragement when pressed for specifics. I need the specific errors so I can fix all of them before submitting the paper to a peer-reviewed journal. Also, a SAT solver that finds cycles in these generators would be very helpful!

ChrisLomont 7y ago
You cannot fix this error. Your proofs do not apply to such limited set of random permutations. You have to prove the cycle structure for the specific ones you chose, no matter how you choose them, otherwise you are playing with a time bomb. As such there’d be no reason to choose your method over many other PRNGs that do provide good cycle length guarantees and equidistribution metrics at the same CPU speeds. In fact, I think your method is a weaker subset of PCG generators, which are as fast and have all the good theoretical guarantees. What do you mean by “true random numbers”? There are 64! permutations on 64 bits. All Roma permutations are a vanishingly small subset of these with very specific structure. How can you prove that structure doesn’t introduce all sorts of bad cases? Don’t worry about all the errors. I doubt this one is fixable.
- deleted 7y ago
  [deleted]
- deleted 7y ago
  [deleted]
- MarkOverton 7y ago
  > You cannot fix this error. Your proofs do not apply to such limited set of random permutations. Incorrect. You are misunderstanding what a probability says. Suppose a ball has a 1/3 chance of landing in bin 1 and a 2/3 chance of bin 2. You throw one ball. But you did not see which bin it landed in. What do you know? You know it has a 1/3 and 2/3 chance of being in bin 1 or 2. Those probabilities apply to just one throw. A Romu generator uses one permutation. But you don't know the cycle-lengths. What do you know? You know the probabilities of various lengths. Those probabilities apply to just one permutation, just as they do for one ball-toss. Bob Jenkins created the JSF generator (http://burtleburtle.net/bob/rand/smallprng.html http://burtleburtle.net/bob/rand/smallprng.html), which is similar to Romu except it uses additions instead of a multiplication. He wrote an article on designing PRNGs (http://burtleburtle.net/bob/rand/talksmall.html#reversible http://burtleburtle.net/bob/rand/talksmall.html#reversible) in which he explains theory briefly and clearly, so this article might help you. > [64! possible permutations] All Roma permutations are a vanishingly small subset of these Yes. In fact, only one permutation is used. But that's irrelevant because the cycles are what matter. And I showed above that the cycles obey the equations for their probable lengths. > with very specific structure. Incorrect. Page 7 of the paper contains graphs of all the cycles in several generators with 32 bits of state, with measurements of their randomness. The cycles performed nearly ideally -- the 45-degree line in the graph. So their structure is not "very specific" (nonrandom); rather, they pass tough tests of randomness. > Don’t worry about all the errors. I doubt this one is fixable. There is no error. Again, read Bob Jenkins' article for a clear discussion of cycle lengths. Let's not discuss the topic of permutations and cycle lengths any further; it won't be productive. Instead: Please post your list of perceived errors in the paper, and let's talk about those. It'll only take a few minutes to write, and will benefit many people because I will clarify unclear parts of the paper.
  - ChrisLomont 7y ago
    >You are misunderstanding what a probability says I have a PhD in math. I've worked on this stuff for decades. Among other work, I wrote a decently cited article on the Hidden Subgroup Problem for quantum computation on arxiv, and this problem requires great understanding of the group structure of the permutation groups as well as a solid grounding in probabilty. It's not likely I am the one who misunderstands probability (or, as I will show you, permutations). >A Romu generator uses one permutation. But you don't know the cycle-lengths. What do you know? You know the probabilities of various lengths. Take your page 2 generator, switch to a 32 bit state so you can empirically check everything with code. The largest cycle length is 1499760802, or 34% of the state space. Check each cycle. The results contradict your "proof" result (2) that the probability P(|cycle with x|<= 2^k) = 2^k/(2^s-1). You simply don't get the bounds you claim. The next two largest cycles are 731971696(17%), 1137668726(26%) to aid you in your checking. They fall off pretty quickly after that. Maybe we were just unlucky, and the original constant caused the failure. Pick another multiplicand. Whoops. Same result. Try again. Same result. In fact, you will fail to meet the bounds of your "proof" for any multiplicand value. So, go ahead and tell me how to use a 32 bit state version of the page 2 generator for which we can compute exact cycle lengths that also meets your bounds. I'll wait..... Thus your "proof" fails to give correct bounds, for precisely the reasons I stated earlier. And thus your table 2 is incorrect - you don't understand the structure of your PRNG, or that it does not satisfy the theorems you are applying to analyze it. Otherwise the "proof" would be a proof. Math doesn't lie. And before you next make the error of claiming the quality increases with bit size, that is usually false. So many people have fallen into this trap in both PRNG creation and crypto. When each choice in your "proofs" is smaller than you claim, often these accumulate faster than the space increases, and you can have catastrophic failure in behavior. Another way to see it: using your page 2 generator again as an example (the others have the same flaws): take the state, mult by your odd, then the last bit is still the same. Rotate by half the bits. Now a middle bit of the next state is always the same as the last bit of the previous state. This is not random, and your proof requires that each choice in it is allowed to choose from the entire remaining possible state values. But we just cut that in half. This problem happens at every bit - there are too many relations between them due to the simplicity of your method to use that proof. Another way to see it: take 64 bit numbers and consider cycles from some permutation. There are (2^64)! such permutations, a number which has ~10^20 digits. It's an astounding size. The proofs apply when you choose your permutation unifrmly from this space. The word "uniformly" has precise mathematical meaning, and you no where near satisfy it. If you don't have a clear understand of what the word means and why you don't meet this requirement then you need to learn what it means. Your simple ROMA has a 64 bit constant (2^64 choices) and a rotation (a generous 64 choices). The number of such choices has about 21 digits, off by around 20 orders of magnitude. You are choosing from an infinitesimally tiny, well-strucutred subset of all the permutations. The theorems do not apply. The "well-structured" part will kill you in practice, just like here. Another way to see it: your "proof" doesn't mention your choices, thus your "proof "should hold for any constant. But it doesn't, which is easy to check. Hopefully that's enough different directions on why your cannot conclude what you did that you see one. Of course the code example shows it without any question. Finally, your entire method is a weaker version of PCG. Your first step is a MCG, which the PCG paper uses in the same manner, then you do a fixed rotation, wheras they use a varying rotation. You cannot prove anything, like cycle lengths or any equidistribution, but they, using the superior structure of PCG, can prove both. You claim yours is faster, but you don't compare against the best PCG methods - choice or accident? Without timing, PCG is likely as fast as yours, with demonstrable quality RNGs. And here's the kicker - the main reason people want PRNGs this fast are things like Monte Carlo, where large cycles and k-equidistribution is of serious concern, and you cannot provide one and make demonstrably incorrect claims on the other. >Bob Jenkins ... which is similar to Romu except it uses additions instead of a multiplication Bob does not make the errors you make; he carefully avoids them. His uses an XOR in the middle of some add, subtract, and rotates. This is fundamentally different. He even states this in the description you recommended I read: "For example, + is linear mod 2^32 and XOR is linear in GF(2^32), but the combination of + and XOR isn't linear. You combine + and XOR, and linearity goes away." You should read it and understand it too. That you see a plus in his and claim it as a defense of yours without understanding what he did and why doesn't create much faith in your analysis. Your sequence overlap "proofs" suffer from the same errors - and you can check them with the 32-bit versions of the code where you can empirically compute all cycles and check odds. Part of this follows from (2) being wrong, as demonstrated with code empirically, and being used as a basis in section 3.2. Without proper proofs I'd recommend no one use this for serious work. There is no real benefit to using it and so many wrong things with it as demonstrated. >Let's not discuss the topic of permutations and cycle lengths any further; it won't be productive. Agreed. Maybe you can either provide a 32 bit ROMU that meets your claimed bounds in (2) or replace your "proofs" with correct ones that agree with exhaustive experiment, then we have progress.
ChrisLomont 7y ago
It also dawned on me your method is basically the same as vonNeumann's 1946 middle square method, which turned out to be terrible from short cycles. His was base 10; yours is base 2. His dropped the bottom and top "bits". Yours drops the top (during the mult). His permuted each time via a different number; yours uses a fixed number. Both use a mult to scramble, and then retain a subset of the bits. Adding more rotates and mults does not change the underlying issues. This type of PRNG has been pretty thoroughly mined over the past 70+ years. You should dig through this work and the following literature on why PRNGs of this structure fell out of favor. I suspect exactly yours appears somewhere following this work. https://en.wikipedia.org/wiki/Middle-square_method https://en.wikipedia.org/wiki/Middle-square_method

ChrisLomont 7y ago

You cannot fix this error. Your proofs do not apply to such limited set of random permutations. You have to prove the cycle structure for the specific ones you chose, no matter how you choose them, otherwise you are playing with a time bomb. As such there’d be no reason to choose your method over many other PRNGs that do provide good cycle length guarantees and equidistribution metrics at the same CPU speeds. In fact, I think your method is a weaker subset of PCG generators, which are as fast and have all the good theoretical guarantees. What do you mean by “true random numbers”? There are 64! permutations on 64 bits. All Roma permutations are a vanishingly small subset of these with very specific structure. How can you prove that structure doesn’t introduce all sorts of bad cases? Don’t worry about all the errors. I doubt this one is fixable.

deleted 7y ago
[deleted]
deleted 7y ago
[deleted]
MarkOverton 7y ago
> You cannot fix this error. Your proofs do not apply to such limited set of random permutations. Incorrect. You are misunderstanding what a probability says. Suppose a ball has a 1/3 chance of landing in bin 1 and a 2/3 chance of bin 2. You throw one ball. But you did not see which bin it landed in. What do you know? You know it has a 1/3 and 2/3 chance of being in bin 1 or 2. Those probabilities apply to just one throw. A Romu generator uses one permutation. But you don't know the cycle-lengths. What do you know? You know the probabilities of various lengths. Those probabilities apply to just one permutation, just as they do for one ball-toss. Bob Jenkins created the JSF generator (http://burtleburtle.net/bob/rand/smallprng.html http://burtleburtle.net/bob/rand/smallprng.html), which is similar to Romu except it uses additions instead of a multiplication. He wrote an article on designing PRNGs (http://burtleburtle.net/bob/rand/talksmall.html#reversible http://burtleburtle.net/bob/rand/talksmall.html#reversible) in which he explains theory briefly and clearly, so this article might help you. > [64! possible permutations] All Roma permutations are a vanishingly small subset of these Yes. In fact, only one permutation is used. But that's irrelevant because the cycles are what matter. And I showed above that the cycles obey the equations for their probable lengths. > with very specific structure. Incorrect. Page 7 of the paper contains graphs of all the cycles in several generators with 32 bits of state, with measurements of their randomness. The cycles performed nearly ideally -- the 45-degree line in the graph. So their structure is not "very specific" (nonrandom); rather, they pass tough tests of randomness. > Don’t worry about all the errors. I doubt this one is fixable. There is no error. Again, read Bob Jenkins' article for a clear discussion of cycle lengths. Let's not discuss the topic of permutations and cycle lengths any further; it won't be productive. Instead: Please post your list of perceived errors in the paper, and let's talk about those. It'll only take a few minutes to write, and will benefit many people because I will clarify unclear parts of the paper.
- ChrisLomont 7y ago
  >You are misunderstanding what a probability says I have a PhD in math. I've worked on this stuff for decades. Among other work, I wrote a decently cited article on the Hidden Subgroup Problem for quantum computation on arxiv, and this problem requires great understanding of the group structure of the permutation groups as well as a solid grounding in probabilty. It's not likely I am the one who misunderstands probability (or, as I will show you, permutations). >A Romu generator uses one permutation. But you don't know the cycle-lengths. What do you know? You know the probabilities of various lengths. Take your page 2 generator, switch to a 32 bit state so you can empirically check everything with code. The largest cycle length is 1499760802, or 34% of the state space. Check each cycle. The results contradict your "proof" result (2) that the probability P(|cycle with x|<= 2^k) = 2^k/(2^s-1). You simply don't get the bounds you claim. The next two largest cycles are 731971696(17%), 1137668726(26%) to aid you in your checking. They fall off pretty quickly after that. Maybe we were just unlucky, and the original constant caused the failure. Pick another multiplicand. Whoops. Same result. Try again. Same result. In fact, you will fail to meet the bounds of your "proof" for any multiplicand value. So, go ahead and tell me how to use a 32 bit state version of the page 2 generator for which we can compute exact cycle lengths that also meets your bounds. I'll wait..... Thus your "proof" fails to give correct bounds, for precisely the reasons I stated earlier. And thus your table 2 is incorrect - you don't understand the structure of your PRNG, or that it does not satisfy the theorems you are applying to analyze it. Otherwise the "proof" would be a proof. Math doesn't lie. And before you next make the error of claiming the quality increases with bit size, that is usually false. So many people have fallen into this trap in both PRNG creation and crypto. When each choice in your "proofs" is smaller than you claim, often these accumulate faster than the space increases, and you can have catastrophic failure in behavior. Another way to see it: using your page 2 generator again as an example (the others have the same flaws): take the state, mult by your odd, then the last bit is still the same. Rotate by half the bits. Now a middle bit of the next state is always the same as the last bit of the previous state. This is not random, and your proof requires that each choice in it is allowed to choose from the entire remaining possible state values. But we just cut that in half. This problem happens at every bit - there are too many relations between them due to the simplicity of your method to use that proof. Another way to see it: take 64 bit numbers and consider cycles from some permutation. There are (2^64)! such permutations, a number which has ~10^20 digits. It's an astounding size. The proofs apply when you choose your permutation unifrmly from this space. The word "uniformly" has precise mathematical meaning, and you no where near satisfy it. If you don't have a clear understand of what the word means and why you don't meet this requirement then you need to learn what it means. Your simple ROMA has a 64 bit constant (2^64 choices) and a rotation (a generous 64 choices). The number of such choices has about 21 digits, off by around 20 orders of magnitude. You are choosing from an infinitesimally tiny, well-strucutred subset of all the permutations. The theorems do not apply. The "well-structured" part will kill you in practice, just like here. Another way to see it: your "proof" doesn't mention your choices, thus your "proof "should hold for any constant. But it doesn't, which is easy to check. Hopefully that's enough different directions on why your cannot conclude what you did that you see one. Of course the code example shows it without any question. Finally, your entire method is a weaker version of PCG. Your first step is a MCG, which the PCG paper uses in the same manner, then you do a fixed rotation, wheras they use a varying rotation. You cannot prove anything, like cycle lengths or any equidistribution, but they, using the superior structure of PCG, can prove both. You claim yours is faster, but you don't compare against the best PCG methods - choice or accident? Without timing, PCG is likely as fast as yours, with demonstrable quality RNGs. And here's the kicker - the main reason people want PRNGs this fast are things like Monte Carlo, where large cycles and k-equidistribution is of serious concern, and you cannot provide one and make demonstrably incorrect claims on the other. >Bob Jenkins ... which is similar to Romu except it uses additions instead of a multiplication Bob does not make the errors you make; he carefully avoids them. His uses an XOR in the middle of some add, subtract, and rotates. This is fundamentally different. He even states this in the description you recommended I read: "For example, + is linear mod 2^32 and XOR is linear in GF(2^32), but the combination of + and XOR isn't linear. You combine + and XOR, and linearity goes away." You should read it and understand it too. That you see a plus in his and claim it as a defense of yours without understanding what he did and why doesn't create much faith in your analysis. Your sequence overlap "proofs" suffer from the same errors - and you can check them with the 32-bit versions of the code where you can empirically compute all cycles and check odds. Part of this follows from (2) being wrong, as demonstrated with code empirically, and being used as a basis in section 3.2. Without proper proofs I'd recommend no one use this for serious work. There is no real benefit to using it and so many wrong things with it as demonstrated. >Let's not discuss the topic of permutations and cycle lengths any further; it won't be productive. Agreed. Maybe you can either provide a 32 bit ROMU that meets your claimed bounds in (2) or replace your "proofs" with correct ones that agree with exhaustive experiment, then we have progress.

ChrisLomont 7y ago

It also dawned on me your method is basically the same as vonNeumann's 1946 middle square method, which turned out to be terrible from short cycles. His was base 10; yours is base 2. His dropped the bottom and top "bits". Yours drops the top (during the mult). His permuted each time via a different number; yours uses a fixed number. Both use a mult to scramble, and then retain a subset of the bits. Adding more rotates and mults does not change the underlying issues. This type of PRNG has been pretty thoroughly mined over the past 70+ years. You should dig through this work and the following literature on why PRNGs of this structure fell out of favor. I suspect exactly yours appears somewhere following this work. https://en.wikipedia.org/wiki/Middle-square_method https://en.wikipedia.org/wiki/Middle-square_method