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. In addition, a very short book by this author with many of the essentials of nonuniform generation is available here.
Meeting Place:
103 LoveOffice Hours:
I am either in my 498 DSL office or my Love 207A office and my office hours are 9:30-10:30AM on Mondays and Wednesdays.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. Students from Mathematics would benefit from a Number Theory course, and Computer Science students would as well. However, having taken my "Monte Carlo Methods" course, or COT 5507: Analytic Methods in Computer Science: A Foundation for Computer Science, will have the necessary background.
Course Outline:
Here is an outline of the material to be covered in the course.
Lecture Notes:
Introductory
Lecture
Random
Number Generation Overview
Testing
Random Numbers
Finding
Outliers in Monte Carlo Computations
Results
from
Number Theory
Geometry
of
Numbers
Theoretical
Tests
and the Spectral Test
Irregularities
of
Distribution
Generating
Nonuniform
Random Numbers
Random Number Generation Bibliography:
Here is random number generation bibliography; this will be used to assign readings and presentations.
Paper Summaries and Friday Discussions:
The paper summaries need to be a few paragraphs long (3, 4, 5), and should provide the main points of the papers; the technical highlights of the paper, and the way in which the technical information makes the main points. It is not assumed that you can understand every paper thoroughly, but by reading the paper you should also have uncovered topics and other issues that you need to understand. The Friday discussions will take the summaries as a starting point, and use the questions that naturally arise in the papers as the topics for discussion and discovery. Each student should put up a "Random Number Generation" homepage of their own. Each week, these will be used by the Professor to grade the summaries.
Instructor:
Michael Mascagni, Ph.D.
Director of Graduate Studies and Professor of Computer Science
Professor of Mathematics (Courtesy)
Professor of Scientific Computing (Courtesy)
Faculty in the Graduate Program in Molecular Biophysics
Florida State University
Tallahassee, FL 32306-4530
E-mail: mascagni@fsu.edu
Office: Dirac Science Library 498/Love 207A
Telephone: +1.850.644.3290
For the curious, here are links to a brief biography of the Professor, and the Professor's home page. Also, here's a tribute to one of the authors of our textbook.
Office Hours:
I am either in my 498 DSL office or
my Love 262 office and my office hours are 9-10AM on Mondays and
Fridays.
Teaching Assistant:
Warning and Encouragement:
The students are warned that by taking this course they are implicitly submitting themselves in the role of instructional "Guinea Pigs." As such, your constant input is not only permitted, but strongly encouraged. Feel free to speak up in class, to visit me in my office with your opinions and criticisms, or to e-mail me with ideas on how to improve this class.
Grading Policy:
The students will be graded based on their presentation of papers from the literature and 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.
Academic Honor Code:
Students are expected to uphold the Academic Honor Code published in The Florida State University Bulletin and the Student Handbook. The Academic Honor System of The Florida State University is based on the premise that each student has the responsibility (1) to uphold the highest standards of academic integrity in the student's own work, (2) to refuse to tolerate violations of academic integrity in the university community, and (3) to foster a high sense of integrity and social responsibility on the part of the university community.
Please see the following web site for a complete explanation of
the Academic Honor Code.
http://www.fsu.edu/Books/Student-Handbook/codes/honor.html
http://www.fsu.edu/Books/Student-Handbook/
Americans with Disabilities Act:
Students with disabilities needing academic accommodation should:
(1) register with and provide documentation to the
For more information about services available to FSU students with disabilities, contact the
Student Disability Resource Center
Dean of Students Department
08 Kellum Hall
Florida State University
Tallahassee, FL 32306-4400
+1.850.644.9566 (voice)
+1.850.644.8504 (TDD)
SDRC@admin.fsu.edu
http://www.fsu.edu/~staffair/dean/StudentDisability/(This syllabus and other class materials are available in alternative format upon request.)