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.

Improve this question
$\endgroup$
8
  • 4
    $\begingroup$ Don't invent your own pseudorandom number generator. Use a standard one. $\endgroup$
    – Yuval Filmus
    Nov 10, 2016 at 12:56
  • $\begingroup$ while reading through this big list i saw this paper which might be of interest. Enjoy $\endgroup$
    – RyanRand
    Nov 10, 2016 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, 2016 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, 2016 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, 2016 at 19:53

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
4
$\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".

Improve this answer
$\endgroup$

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