MarkOverton

I have given this question (and my paper) to a PhD who works heavily with probability and has a track-record of accomplishments. Also, I have another idea on empirical verification. So hang on...

> 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), 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) 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.

I've changed the license to Apache version 2.0. Thanks for suggesting it!

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!

I mention this idea in the paper (which is linked at the top of the website). The problem is that this technique increases register pressure when the generator is inlined, which in turn increases spills, which reduces performance.

Yes, the output latency is zero clock cycles. The paper contains ILP tables that detail what happens in each clock cycle. The generator computes its next output while the application is running. But you are correct in that the statement (and ILP table) assumes that the application is not using all available issue-slots.

That's why I pointed out that the probability of a too-short cycle or sequence-overlap is no higher than that of randomly selecting one snowflake out of all snowflakes in Earth's history. Also, the paper has a graph and accompanying discussion of what happens with the shorter cycles.

I'm easy-going about this. I want anybody to be able to copy and modify the code, but not claim credit for inventing it. - Mark Overton