Random Numbers and Computers

verfasst von: Prof. Ronald T. Kneusel

Verlag: Springer International Publishing

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book covers pseudorandom number generation algorithms, evaluation techniques, and offers practical advice and code examples. Random Numbers and Computers is an essential introduction or refresher on pseudorandom numbers in computer science.

The first comprehensive book on the topic, readers are provided with a practical introduction to the techniques of pseudorandom number generation, including how the algorithms work and how to test the output to decide if it is suitable for a particular purpose.

Practical applications are demonstrated with hands-on presentation and descriptions that readers can apply directly to their own work. Examples are in C and Python and given with an emphasis on understanding the algorithms to the point of practical application. The examples are meant to be implemented, experimented with and improved/adapted by the reader.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Random and Pseudorandom Sequences

Abstract

Randomness is a fuzzy and difficult concept. In this chapter we side-step the philosophical issues and instead focus on random and pseudorandom sequences. We discuss what we mean by a random sequence and give examples of processes that generate randomness. We then conduct an experiment that shows humans are bad at randomness. Pseudorandom sequences are introduced next, along with an experiment showing that the quality of a pseudorandom sequence matters. We conclude with a quick look at hardware random number generation as supported by modern CPUs.

Ronald T. Kneusel

Chapter 2. Generating Uniform Random Numbers

Abstract

Integers uniformly distributed over some interval are at the heart of pseudorandom number generators. This chapter examines techniques for generating pseudorandom integers: some historical, some useful for noncritical tasks such as games, and others which are workhorses and should be thought of as go-to methods. We will also take a look at how combining generators can increase their periods. We end the chapter with a brief look at quasirandom generators.

Ronald T. Kneusel

Chapter 3. Generating Nonuniform Random Numbers

Abstract

In this chapter we look at how to transform uniform random numbers into samples from other distributions. We only consider standard or commonly found distributions and develop a cookbook of transformations. We give code for the transformations and investigate the effects of different uniform generators on the output.

Ronald T. Kneusel

Chapter 4. Testing Pseudorandom Generators

Abstract

Testing pseudorandom number generators is not quite as straightforward as it might seem. In this chapter we consider classical tests of randomness and apply them to the generators discussed in Chap. 2. Next we investigate two popular test suites: dieharder (based on the older DIEHARD) and TestU01, and one quick test program (ent). These test suites are the benchmarks against which researchers generally measure new algorithms.

Ronald T. Kneusel

Chapter 5. Parallel Random Number Generators

Abstract

It is often the case that many separate threads or processes require independent streams of pseudorandom numbers. This chapter examines five methods for generating such streams: a pseudorandom number server process, separate per stream generators, partitioning a single stream into non-overlapping segments, random seeding that relies on the small likelihood of randomly picking overlapping streams, and merging two randomly initialized generator outputs. Implementations for certain generators will be developed and output streams tested.

Ronald T. Kneusel

Chapter 6. Cryptographically Secure Pseudorandom Number Generators

Abstract

Cryptographically secure pseudorandom number generators (CSPRNGs) are pseudorandom number generators that protect against attack while still providing high quality pseudorandom values. In this chapter, we explore four of these generators, one for historical purposes (Blum Blum Shub) and three that are considered secure and are in current use: ISAAC, Fortuna, and ChaCha20.

Ronald T. Kneusel

Chapter 7. Other Random Sequences

Abstract

Sequences of numbers that can be used as-is or transformed into random numbers are the topic of this chapter. We are not concerned here with the practicality of such sequences for use where pseudorandom generators are typically used, but instead present them for fun as they are interesting in their own right. We will look at the randomness of the digits in base 10 and base 16 expansions of numbers that are known to be normal or believed to be normal. We will consider the sequence of digits in factorials of different sizes. We will look at the sequence of bits generated by 1-D cellular automata, in particular Wolfram’s “Rule 30”. Lastly, we will consider how to use 1-D chaotic maps to generate a sequence of random numbers. In all cases we will test the sequences using either dieharder, TestU01, or ent. We conclude the chapter with a section on using genetic programming to evolve a simple pseudorandom number generator.

Ronald T. Kneusel

Backmatter

Titel: Random Numbers and Computers
verfasst von: Prof. Ronald T. Kneusel
Verlag: Springer International Publishing
Electronic ISBN: 978-3-319-77697-2
Print ISBN: 978-3-319-77696-5
DOI: https://doi.org/10.1007/978-3-319-77697-2