Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

On Melissa O’Neill’s PCG random number generator

lemire.me

Post reply on HN
Print view View original

41–50 of 90 posts

Re: On Melissa O’Neill’s PCG random number generator

#41

Post by bmm6o »

wadkar wrote: post #22
bmm6o wrote: post #19

It sounds like an interesting result, I look forward to reading the paper more carefully. That said, it's clearly not written for an academic journal. Section 2.4.3 is entitled "The Importance of Code Size", and explains why shorter code is better. I think you can argue that some academic papers are excessively concise, but this is a 58-page paper about an RNG. It is clearly not a journal paper and has a ton of extra…

> I wonder why she didn't write [two] versions. Because the reviewers took over 10 months to respond with a rejection mainly citing the length of the paper. And more importantly, "By that point, everyone who might have wanted to read it had almost certainly found it here and done so, so I saw little merit in drastically shortening the paper."[1] She has updated the blog post which discusses all the nuanced details of…

There is no excuse for the journal to take so long to provide a response. At the same time, it seems to me that their response was entirely predictable. Or does the journal usually post such long articles directed at a general audience?

Re: On Melissa O’Neill’s PCG random number generator

#42

Post by tptacek »

dsacco wrote: post #37
tptacek wrote: post #35

Earlier quoted context omitted.

Just to be clear: it's not a cryptography paper, is it? Did you figure out what journal it was submitted to?

She submitted it to ACM Transactions on Mathematical Software. I would personally consider it a cryptography paper, for three reasons: 1. She purports to introduce a novel result that bridges "medium-grade" performance characteristics and security characteristics in one primitive. In fact, if you look at the PCG Random website (pcg-random.org), she very clearly compares and emphasizes both performance and security ch…

If you stripped out all the (weird, random) cryptographic stuff from this paper, it would read pretty much the same and make pretty much the same points, which tells me: it's not a cryptographic paper.

Re: On Melissa O’Neill’s PCG random number generator

#43

Post by the_stc »

mathperson wrote: post #30
the_stc wrote: post #17

As a general comment, I dislike deliberately obtuse writing in papers. In my current work, I came across a very in-depth survey of our industry (sex work). Excellent study, very helpful. But some of the sentences seemed to over-complicate the math. Example: "Consider the set P {p1, p2, ... pN} representing providers and the set C {c1, c2, ... cN} representing customers". I am pretty sure this kind of stuff is filler…

are you joking? That is your example of abstruse mathematical notation? Some variables with names?!

No. I am saying that giving the definition of a set each time is just extra verbosity. The whole paper had that extra verbiage, everywhere. Kind of why-use-one-word-when-ten-will-do feeling.

Re: On Melissa O’Neill’s PCG random number generator

#44

Post by DonbunEf7 »

Animats wrote: post #33
tptacek wrote: post #15

Earlier quoted context omitted.

It's a weird paper. It's quite long and takes an eternity to reach this simple point. It's also littered with "security concerns" which are confusing at best and misleading at worst; in reality, none of the generators it discusses are suitable for "sensitive applications", even in the corner-case scenario it discusses of needing permutations of all the b-bit integers, a problem we already have cryptographic tools to…

Linear congruential generators (x = k1*x + k2, unsigned with truncation on overflow) have some strange properties, some of which the paper explores. If you repeatedly take three sequential values from one and treat them as 3D coordinates, the points line up in parallel planes. (There's an explanation of why in Knuth.) Something has to be done to destroy that order. The solution here is to XOR the upper and lower halv…

The paper is really two papers. The first paper is a thoughtful and careful explanation of how we should consider judging pseudorandomness, and how to measure various criteria, along with a survey of many popular ten-lines-or-less PRNGs which PCG competes with. I found it interesting.

Re: On Melissa O’Neill’s PCG random number generator

#45

Post by mathperson »

the_stc wrote: post #43
mathperson wrote: post #30

Earlier quoted context omitted.

are you joking? That is your example of abstruse mathematical notation? Some variables with names?!

No. I am saying that giving the definition of a set each time is just extra verbosity. The whole paper had that extra verbiage, everywhere. Kind of why-use-one-word-when-ten-will-do feeling.

Could you share the paper? I mean if they were making a mathematical argument...it is kind of hard to do that without defining things..

Re: On Melissa O’Neill’s PCG random number generator

#46

Post by dsacco »

tptacek wrote: post #42
dsacco wrote: post #37

Earlier quoted context omitted.

She submitted it to ACM Transactions on Mathematical Software. I would personally consider it a cryptography paper, for three reasons: 1. She purports to introduce a novel result that bridges "medium-grade" performance characteristics and security characteristics in one primitive. In fact, if you look at the PCG Random website (pcg-random.org), she very clearly compares and emphasizes both performance and security ch…

If you stripped out all the (weird, random) cryptographic stuff from this paper, it would read pretty much the same and make pretty much the same points, which tells me: it's not a cryptographic paper.

That's a fair point; it was mostly the presence of the random crypto that annoyed me :)

Re: On Melissa O’Neill’s PCG random number generator

#47

Post by msla »

marze wrote: post #18
Animats wrote: post #14

Here's the site for the random number generator.[1] It's basically a simple linear congruential random number generator (well known, but not very good) fed into a mixer. The mixer is new. Most of the analysis is about the LCG or the final output. The suggested mixer is just output = rotate64(uint64_t(state ^ (state >> 64)), state >> 122); That's simple, and the insight in this paper is that something that simple help…

>linear congruential random number generator (well known, but not very good) Relevant quotes from the paper: "But if you began reading the section with the belief that “linear congruential generators are bad” (a fairly widely-held belief amongst people who know a little about random number generation), you may have been surprised by how well they performed. We’ve seen that they are fast, fairly space efficient, and a…

Two-to-the-forty-seven nanoseconds is a little over thirty-nine hours.

(Let's see HN mangle that!)

Re: On Melissa O’Neill’s PCG random number generator

#48

Post by mathperson »

thanatropism wrote: post #36
lowmagnet wrote: post #4

I like this because she is a professor at Harvey Mudd. They took steps to make CS more inclusive, with great results. I appreciate her attitude on accessibility, which is in keeping with that institution's philosophy. That she ran into a paper wall doesn't bother her because she's openly publishing is even better.

There's room for accessible and for abstruse literature. Usually what happens with novel work is that initial publications are abstruse but met with excitement by the scholarly community and gradually more accessible works (as the number of collaborators/coauthors grows too) are published. That said, even if multi-culti math means that top-line researchers are going to be spending time with song-and-dance introductio…

What is multi-culti?

Re: On Melissa O’Neill’s PCG random number generator

#49

Post by eridius »

fwdpropaganda wrote: post #25

Physicist here. Off-topic > And it is not even entirely clear what “really random” would mean. It is not clear that we live in a randomized universe… At the quantum level it really is clear that we live in a really random universe. What's the meaning of really random? The outcome of a quantum process. On-topic. Yeah, you have to know your audience. As OP mentions, just because the paper wasn't published doesn't preve…

A quantum process is a random process, but isn't it still an open philosophical question as to whether the "random process" we observe is truly random, or is instead governed by deterministic hidden state?

Re: On Melissa O’Neill’s PCG random number generator

#50

Post by tptacek »

mathperson wrote: post #48
thanatropism wrote: post #36

Earlier quoted context omitted.

There's room for accessible and for abstruse literature. Usually what happens with novel work is that initial publications are abstruse but met with excitement by the scholarly community and gradually more accessible works (as the number of collaborators/coauthors grows too) are published. That said, even if multi-culti math means that top-line researchers are going to be spending time with song-and-dance introductio…

What is multi-culti?

"Physics for poets".
Post reply on HN