**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:**

Meeting Time:

8:00AM to 9:15AM: Tuesdays and Thursdays

**Office Hours:**

**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.)