5
$\begingroup$

I'm a rank amateur in the area of pseudo-random number generation. I've recently found out that certain generators are better than others (e.g. mt19337 vs rand in C++) and learned what modulo bias is.

My Request

I'm looking for an introductory book on pseudo-random number generation. Does one exist?

My Requirements

The book must be understandable by someone with the following mathematics background:

  • calculus
  • discrete math (combinatorics, logic and proofs, set theory, mathematical induction, functions and relations, inclusion-exclusion, generating functions, recurrence relations, graphs/graph algorithms)
  • linear algebra (vectors,matrix algebra, eigenvalues, transformations, diagonalization)
  • introductory numerical analysis (computer arithmetic and errors, root-finding algorithms, computational techniques for matrices, numerical integration and differentiation)

I would prefer a book that does not require knowledge of any specific programming language:

  • Would like algorithms to be presented in a pseudocode style (e.g. Introduction to Algorithms by Cormen)
  • If the book isn't language neutral, I know the following languages: Python, Java, C++,C,Ruby.

I'm looking for a book that is accessible to a fairly inexperienced CS undergraduate:

  • I have a basic understanding of stacks, linked lists, trees, heaps, hash tables and graphs
  • I'm comfortable with basic programming concepts

The book should cover pseudorandom number generation at an introductory level:

  • I'm not looking for a complete encyclopedic treatment on every research paper ever published in the area, but enough content to gain an entry level understanding in the area that you'd expect someone to learn in a first undergraduate course on pseudo-random number generation. For example if someone asked you for a book on introductory calculus you'd probably recommend a book that covers limits, differentiation, related rates, approximation of derivatives, L'Hopital's Rule and some basic continuous optimization. I'm looking for something similar in the area of PRNG. It's hard for me to specify exactly what I'm looking for because I know next to nothing about the area, but try and think of what you'd expect a complete amateur in the area to be able to reasonably learn in a semester.

What I've Tried

I'm looking at Chapter 3 of Donald Knuth's art of computer programming volume 2. The book seems quite old and uses some kind of assembly that I don't understand. If this is the authoritative reference, I'll find my way around these issues, but other books would be nice.

$\endgroup$
  • 4
    $\begingroup$ Don't invent your own pseudorandom number generator. Use a standard one. $\endgroup$ – Yuval Filmus Nov 10 '16 at 12:56
  • $\begingroup$ while reading through this big list i saw this paper which might be of interest. Enjoy $\endgroup$ – Ryan Nov 10 '16 at 13:34
  • 3
    $\begingroup$ @YuvalFilmus definitely don't plan on implementing my own, just curious about how they work. I think it could be interesting for me in the same way learning about sorting algorithms is interesting even though I'll always use the professionally engineered sort package in practice. $\endgroup$ – Dunka Nov 10 '16 at 20:47
  • $\begingroup$ @Raphael I'd love to comply with what you said, but I know almost nothing about the area. It's hard to clarify because I don't know how to get more specific. What does one generally learn in a first course on PRNG and what book or note set would someone use to gain that knowledge? $\endgroup$ – Dunka Nov 10 '16 at 21:30
  • 1
    $\begingroup$ TestU01 implements the Mersenne Twister algorithm I believe and contains some test cases for testing their random number generator. $\endgroup$ – BlazePascal Nov 15 '16 at 19:53
2
$\begingroup$

This isn't a book, and it's not a complete introduction, but Melissa O'Neill's tech report, PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation, doubles as one of the best surveys of general-purpose PRNGs and how to test them. It's also extremely accessible for a beginner.

It doesn't cover cryptographically strong PRNGs, so it's not a complete introduction by itself.

$\endgroup$
3
$\begingroup$

The book Random numbers and computers by Ronald T. Kneusel, recently published by Springer, contains pseudorandom number generation algorithms, evaluation techniques, and code examples in C and Python. It is aimed at "anyone who develops software, including software engineers, scientists, engineers, and students of those disciplines".

$\endgroup$

protected by Community Nov 15 '16 at 21:29

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.