Purpose of the course:
This course provides a graduate level examination of all aspects of random number generation as used in simulation. Random number generation has two main applications, simulation and cryptography. While there are many similarities to the computational random numbers used in simulation and cryptography, the ultimate standard used to assess quality is very different. Thus, in this course we will concentrate on pseudorandom number generation and quasirandom number generation. To understand both, students need to have familiarity with certain mathematical and statistical concepts. These will be reviewed in this course, and will be used extensively.
The course will begin present the theory of pseudo- and quasirandom number generation, discuss the implementational issues, and consider aspects as they relate to current application and architectural developments. The format of the course will be lecture-based, but after a basic foundation is developed, book chapters, research papers, and other primary material will be discussed in class in presentations lead by students. The students will be graded based on their presentation of these topics as well as a final project. The final project will include a written component, and depending on time and the number of students in the course, may also include oral presentations.
Textbooks:
There are no textbooks required for this course, but here are a list of several books that cover important material for this course. The books are listed in the order of relevance as determined by the instructor:
D. E. Knuth, The Art of Computer Programming, Volume 2, Seminumerical Algorithms, Third Edition, Addison Wesley, Reading, MA, 1998.
The first section, pages 1-193, is a comprehensive introduction to random number generation, and statistical and theoretical testing of random numbers. This is holy scripture in the random number generation literature, and we will be spending a significant part of the course on uniform and nonuniform random number generation.
S. Tezuka, Uniform Random Numbers: Theory and Practice, Kluwer Academic Publishers, Boston, Dordrecht, London, 1995
This book covers both pseudorandom and quasirandom number generation in a very modern way. The background material in this book on number theory is one of the best in the sense that it goes over exactly that number theory that is required to understand the theory in a mature way.
H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods, SIAM, Philadelphia, 1992.
This book is a great, in depth, review of quasirandom number generation based on 10 lectures given at a special meeting held in Fairbanks, Alaska, which the course instructor attended. This book is written from the perspective of number theory, and is a great reference, but requires a level of mathematical maturity to fully appreciate.
L. Devroye, Nonuniform Variate Generation, Springer-Verlag, Berlin, Heidelberg, New York, 1986.
This is the standard reference on the production of nonuniform random numbers. The assumptions are that "easy" distributions, like U[0,1), are readily available, and this book deals with the myriad number of ways to transform the easy random numbers into anything else you might want. Luc Devroye has posted this book on the web here, and we have made the book available as a single PDF document here.
Meeting Time/Place:
1300-1400, Building 9, Room 2325
Prerequisites:
The students taking this course should be either Computer Science or Mathematics students interested in the subject of random number generation. Students should be mathematically mature, and should know something about number theory.
Course Outline:
Here is an outline of the material to be covered in the course if we had a real full term!!
Lecture Notes:
Random
Number Generation Overview
Testing Random Numbers
Results
from Number Theory
Geometry of Numbers
Theoretical Tests and the Spectral Test
Irregularities of Distribution
Generating Nonuniform
Random Numbers
Scalable Parallel Random Number Generators (SPRNG) Library Overview
Random Number Generation Bibliography:
Here is random number generation bibliography; this will be used to assign readings and presentations. We are looking at papers 114, 137, 138, 120, and 196.
Are You Paying Attention:
Here is a problem set to see if you are.
Instructor:
Michael Mascagni, Ph.D.
Professor of Computer Science
Professor of Mathematics (Courtesy)
Professof of Scientific Computing (Courtesy)
Florida State University
Tallahassee, FL 32306-4530
E-mail: mascagni@fsu.edu
Office: Dirac Science Library 498/Love 172
Telephone: +1.850.644.3290
Cell@KAUST: 0562.923.124
For the curious, here are links to a brief biography of the Professor, and the Professor's home page.