6 ms·

I'd stay away from this work. There are ample math and reasoning errors in the paper, and the claims are dubious. One prime example: the algo for ROMU is of th

I'd stay away from this work. There are ample math and reasoning errors in the paper, and the claims are dubious. One prime example: the algo for ROMU is of the form new_state64 = ROTATE_LEFT(old_state64,32) * constant, which decomposes the space {1,2,..,2^64-1} into a permutation. From a given start seed, your cycle may be short, and you won't know this until it bites you. The author incorrectly addresses this using the theory of random permutations, but his is most definitely NOT a random permutation chosen uniformly from S_n. His analysis most does not follow. The proofs he cites are not applicable to his since he has a fixed permutation. Among all cycles, among all permutations, the results hold. They do not hold for a fixed permutation. For example his results fail for the n-cycle and they fail for the identity permutation. They similarly fail for many, many other permutations, and he has no proof that his is not a badly chosen one. Based on the structure of it (rotate and mult), I suspect from past experience that his permutation has lots of structure that leads to all sorts of pathologies for this use.This is a basic math error, and the paper is full of such basic errors. For why to listen (somewhat) to me, check out my name - I've done a bit of writing (and a lot of teaching) on PRNGs for decades. I've followed the field for quite some time, and am well aware of much of the research in it. There is no need with all the good choices out there to choose a PRNG that cannot provide a solid proof of cycle length (or at least correct bounds) for any seed value. This one fails this basic test. If I get time (and remember) later, I've written some SAT solver code to explicitly find holes in PRNGs, and I'll try to dig it out and analyze the cycles in this fixed permutation. If anyone else wants to try it the idea is you can assign variables to bit positions in the state, represent the permutation as boolean expressions in these bits, and find cycles using SAT solvers without having to run through steps incrementally. I suspect in this case it will break this PRNG pretty quickly.

clarry 7y ago
> The proofs he cites are not applicable to his since he has a fixed permutation. This is something I'm concerned about (hence https://news.ycombinator.com/item?id=22451307 https://news.ycombinator.com/item?id=22451307), but I lack the know-how to demonstrate the difference. > I get time (and remember) later, I've written some SAT solver code to explicitly find holes in PRNGs, and I'll try to dig it out and analyze the cycles in this fixed permutation. Thanks, I would love to see this. Can I expect to see the results on your blog or here or somewhere else? Presumably you've done this for other PRNGs in the past. If you've got links to share, I'd like to take a look, and hopefully learn a thing or two. :-)
- ChrisLomont 7y ago
  I’ve done it for crypto work, and to find or prove impossible certain mixing functions for PRNG work. Knuth fascicles on Boolean Functions and SAT solvers give a good foundation for this type of work. Do all or most of his related exercises to get going. Unfortunately, I rarely write stuff up. Too busy doing :) Writing up well takes considerable time away from making things.
MarkOverton 7y ago
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.

clarry 7y ago

> The proofs he cites are not applicable to his since he has a fixed permutation. This is something I'm concerned about (hence https://news.ycombinator.com/item?id=22451307 https://news.ycombinator.com/item?id=22451307), but I lack the know-how to demonstrate the difference. > I get time (and remember) later, I've written some SAT solver code to explicitly find holes in PRNGs, and I'll try to dig it out and analyze the cycles in this fixed permutation. Thanks, I would love to see this. Can I expect to see the results on your blog or here or somewhere else? Presumably you've done this for other PRNGs in the past. If you've got links to share, I'd like to take a look, and hopefully learn a thing or two. :-)

ChrisLomont 7y ago
I’ve done it for crypto work, and to find or prove impossible certain mixing functions for PRNG work. Knuth fascicles on Boolean Functions and SAT solvers give a good foundation for this type of work. Do all or most of his related exercises to get going. Unfortunately, I rarely write stuff up. Too busy doing :) Writing up well takes considerable time away from making things.

MarkOverton 7y ago

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.