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:
9:30AM to 10:45AM: Tuesday and Thursday, 301 Love Building
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:
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
Random Number Generation Bibliography:
Here is random number generation bibliography; this will be used to assign readings and presentations.
Paper Summaries:
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.
Professor of Computer Science
Professor of Mathematics (Courtesy)
Professor 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.6407 (Love 262) .3290 (DSL 498)
For the curious, here are links to a brief biography of the Professor, and the Professor's home page.
Office Hours:
TBD, in my DSL office, 262 Love Building or Dirac Science Library
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.
E-mail Policy:
All e-mail communication regarding this course must be sent and received from an fsu.edu e-mail address.
Academic Honor Policy:
The
Florida State University Academic Honor Policy outlines the
University’s expectations for the integrity of students’ academic work,
the procedures for resolving alleged violations of those expectations,
and the rights and responsibilities of students and faculty members
throughout the process. Students are responsible for reading the
Academic Honor Policy and for living up to their pledge to “. . . be
honest and truthful and . . . [to] strive for personal and
institutional integrity at Florida State University.” (Florida
State University Academic Honor Policy, found at http://dof.fsu.edu/honorpolicy.htm).
Americans with Disabilities Act:
Students with disabilities needing academic accommodation should:
(1) register with and provide documentation to the Student Disability Resource Center; and
(2)
bring a letter to the instructor indicating the need for accommodation
and what type. This should be done during the first week of class.
This syllabus and other class materials are available in alternative format upon request:
For more information about services available to FSU students with disabilities, contact the:
Student Disability Resource Center
97 Woodward Avenue, South
108 Student Services Building
Florida State University
Tallahassee, FL 32306-4167
(850) 644-9566 (voice)
(850) 644-8504 (TDD)
sdrc@admin.fsu.edu
http://www.disabilitycenter.fsu.edu/