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

The Art of Computer Programming: Random Numbers

informit.com

Post reply on HN
Print view View original

11–20 of 29 posts

Re: The Art of Computer Programming: Random Numbers

#11

Post by abecedarius »

thegeomaster wrote: post #10

This reminds me of a (somewhat) funny situation that happened to me one time. My parents bought some Lotto tickets and wanted to play, so they filled most of the combinations themselves and left two of them for me. I was annoyed by having to do that, so I take the tickets, and ask my dad, "So, you know that every combination is equally likely to win?", and he casually replies something like, "Yeah, sure, I'm not dumb…

I ran through the same script with my dad once, except he answered "Yeah, but you'll have to split the pot with more smartasses like you."

Re: The Art of Computer Programming: Random Numbers

#12

Post by adolgert »

Do the Monte Carlo people all know about Barash and Shchur's work? They made an RNGSSELIB and PRAND (using NVIDIA cards), but the main contribution is that they incorporated a new way to generate multiple streams not by re-seeding the generator but by skipping ahead, even with Mersenne twisters. It is the only simple way to get parallel streams, and it didn't exist just a few years ago. You still need to be careful in various ways, but this helps a lot. A lot, a lot.

[1] http://arxiv.org/pdf/1307.5866.pdf

Re: The Art of Computer Programming: Random Numbers

#13

Post by [deleted] »

adolgert wrote: post #12

Do the Monte Carlo people all know about Barash and Shchur's work? They made an RNGSSELIB and PRAND (using NVIDIA cards), but the main contribution is that they incorporated a new way to generate multiple streams not by re-seeding the generator but by skipping ahead, even with Mersenne twisters. It is the only simple way to get parallel streams, and it didn't exist just a few years ago. You still need to be careful i…

[deleted]

Re: The Art of Computer Programming: Random Numbers

#14

Post by pbsd »

adolgert wrote: post #12

Do the Monte Carlo people all know about Barash and Shchur's work? They made an RNGSSELIB and PRAND (using NVIDIA cards), but the main contribution is that they incorporated a new way to generate multiple streams not by re-seeding the generator but by skipping ahead, even with Mersenne twisters. It is the only simple way to get parallel streams, and it didn't exist just a few years ago. You still need to be careful i…

Skipping ahead is not new; it is a well-known fact that any linearly recurrent generator, such as WELL, Xorshift, or Mersenne Twister can skip ahead via matrix exponentiation.

And it is not the only way to get good independent streams either; hooking a cipher with a counter is arguably a superior way to do it, cf [1].

[1] http://www.thesalmons.org/john/random123/papers/random123sc1...

Re: The Art of Computer Programming: Random Numbers

#15

Post by brudgers »

antics wrote: post #6

When you step back to think about it, a huge amount of CS theory papers rely on this hand-wavy definition of "randomness" to prove something. Oddly, though, if you actually press a CS theory person for a mathematical definition of this concept, they virtually always draw a blank. As a student I remember thinking that this was incredibly alarming. Without a good understanding of this concept, how can we be sure any of…

Semi-Numerical Algorithms is Knuth's Silmarillion to his jaunty Hobbit of Volume I and the serious Lord of the Rings questing that is Volume III. OK, I know it's a stretch, but Semi-Numerical Algorithms is more of a back story...these days writing a floating point implementation is much less likely than a linked list or a binary search.

But picking up a like new used copy from Amazon for less than $10 with shipping made it to good to pass up, and like the rest of Knuth, every time I read a few pages I learn something new.

Re: The Art of Computer Programming: Random Numbers

#16

Post by sidww2 »

antics wrote: post #6

When you step back to think about it, a huge amount of CS theory papers rely on this hand-wavy definition of "randomness" to prove something. Oddly, though, if you actually press a CS theory person for a mathematical definition of this concept, they virtually always draw a blank. As a student I remember thinking that this was incredibly alarming. Without a good understanding of this concept, how can we be sure any of…

What? The modern definition of pseudorandomness (https://en.wikipedia.org/wiki/Pseudorandomness#Pseudorandomn...) was figured out in the 80s through the works of Blum, Goldwasser, Micali, Goldreich, etc. and is not hand-wavy at all. It's pretty rigorous and reliable.

Re: The Art of Computer Programming: Random Numbers

#17

Post by antics »

sidww2 wrote: post #16
antics wrote: post #6

When you step back to think about it, a huge amount of CS theory papers rely on this hand-wavy definition of "randomness" to prove something. Oddly, though, if you actually press a CS theory person for a mathematical definition of this concept, they virtually always draw a blank. As a student I remember thinking that this was incredibly alarming. Without a good understanding of this concept, how can we be sure any of…

What? The modern definition of pseudorandomness ( https://en.wikipedia.org/wiki/Pseudorandomness#Pseudorandomn... ) was figured out in the 80s through the works of Blum, Goldwasser, Micali, Goldreich, etc. and is not hand-wavy at all. It's pretty rigorous and reliable.

You are 100% mistaken that this implies we had a good definition of random sequences before Knuth. In the article you link, they discuss the uniform distribution, but any distribution (and the modern notion of probability in general) absolutely depends on a mathematically precise notion of random sequences.

If you don't believe me, read the chapter. Early probability theorists (e.g., von Mises, Kolmogorov) literally started thinking about randomness in order to define probability.

EDIT: And, I don't suppose it's worth pointing out that pseudorandomness is not at all the same thing as randomness. The fact that you seem to use them interchangeably is not a good sign IMHO.

EDIT 2: Why the unexplained downvote, HN? :(

Re: The Art of Computer Programming: Random Numbers

#18

Post by adolgert »

pbsd wrote: post #14
adolgert wrote: post #12

Do the Monte Carlo people all know about Barash and Shchur's work? They made an RNGSSELIB and PRAND (using NVIDIA cards), but the main contribution is that they incorporated a new way to generate multiple streams not by re-seeding the generator but by skipping ahead, even with Mersenne twisters. It is the only simple way to get parallel streams, and it didn't exist just a few years ago. You still need to be careful i…

Skipping ahead is not new; it is a well-known fact that any linearly recurrent generator, such as WELL, Xorshift, or Mersenne Twister can skip ahead via matrix exponentiation. And it is not the only way to get good independent streams either; hooking a cipher with a counter is arguably a superior way to do it, cf [1]. [1] http://www.thesalmons.org/john/random123/papers/random123sc1...

I like that paper. Thank you. It has references which criticize the skipahead technique. I need to look into whether I believe that paper, though. There are lots of ideas about how to do this, and subtle flaws abound. While many generators are known to skipahead, there is a quite new technique for MT that makes it much faster, not by Barash and Shchur, but they used it. Again, thanks.

Re: The Art of Computer Programming: Random Numbers

#19

Post by sidww2 »

antics wrote: post #17
sidww2 wrote: post #16

Earlier quoted context omitted.

What? The modern definition of pseudorandomness ( https://en.wikipedia.org/wiki/Pseudorandomness#Pseudorandomn... ) was figured out in the 80s through the works of Blum, Goldwasser, Micali, Goldreich, etc. and is not hand-wavy at all. It's pretty rigorous and reliable.

You are 100% mistaken that this implies we had a good definition of random sequences before Knuth. In the article you link, they discuss the uniform distribution, but any distribution (and the modern notion of probability in general) absolutely depends on a mathematically precise notion of random sequences. If you don't believe me, read the chapter. Early probability theorists (e.g., von Mises, Kolmogorov) literally…

I skimmed through the extract presented (didn't have time to go into detail) but I don't see a formal definition of any kind presented in the extract. Could you point me to where it is? And if it's not in the extract, then could you quote it here?

Pseudorandomness is not the same thing as randomness but most algorithms today work on pseudorandom numbers so the concept is important. My impression was that that's what you were referring to.

PS :- FYI I didn't downvote your comment. Actually upvoted as your post made me discover some new math (various notions of randomness by kolmogorov, von mises, martin-lof) :)

Re: The Art of Computer Programming: Random Numbers

#20

Post by wtracy »

pbsd wrote: post #14
adolgert wrote: post #12

Do the Monte Carlo people all know about Barash and Shchur's work? They made an RNGSSELIB and PRAND (using NVIDIA cards), but the main contribution is that they incorporated a new way to generate multiple streams not by re-seeding the generator but by skipping ahead, even with Mersenne twisters. It is the only simple way to get parallel streams, and it didn't exist just a few years ago. You still need to be careful i…

Skipping ahead is not new; it is a well-known fact that any linearly recurrent generator, such as WELL, Xorshift, or Mersenne Twister can skip ahead via matrix exponentiation. And it is not the only way to get good independent streams either; hooking a cipher with a counter is arguably a superior way to do it, cf [1]. [1] http://www.thesalmons.org/john/random123/papers/random123sc1...

A million times thank you for that link! I've been needing something exactly like that for a pet project of mine.
Post reply on HN