veyepar: Fast random number generation in Python and NumPy

Author(s):	Bernardt Duvenhage
Location	Cedarwood
Date	oct Fri 12	Days Raw Files
Start	13:30	First Raw Start	13:01
Duration	00:55:00	Offset	0:28:58
End	14:25	Last Raw End	14:31
Chapters	00:00 0:00:03 0:21:49
Total cuts_time	39 min.

https://za.pycon.org/talks/53-fast-random-number-generation-in-python-and-numpy/
raw-playlist raw-mp4-playlist encoded-files-playlist host archive tweet mp4 svg png

assets release.pdf An_introduction_to_concurrent_programming_with_asyncio.json
logs
Admin: episode episode list cut list raw files day marks day marks day image_files

State:

Locked:

clear this to unlock

Locked by:

user/process that locked.

Start:

initially scheduled time from master, adjusted to match reality

Duration:

length in hh:mm:ss

Name:

Video Title (shows in video search results)

Emails:

email(s) of the presenter(s)

Released:

has someone authorised pubication

Normalise:

Channelcopy:

m=mono, 01=copy left to right, 10=right to left, 00=ignore.

Thumbnail:

filename.png

Description:

markdown

A fast Random Number Generator (RNG) is key to doing Monte Carlo simulations, efficiently initialising machine learning models, shuffling long sequences of numbers and many tasks in scientific computing. CPython and NumPy use implementations of the Mersenne Twister RNG and rejection sampling to generate random numbers in an interval. The NumPy implementation trades more samples for cheaper division by a power of two. The implementation is very efficient when the random interval is a power of two, but on average generate many more samples compared to the GNU C or Java algorithms. The Python RNG uses an algorithm similar to GNU C.

A recent paper by Daniel Lemire (https://arxiv.org/abs/1805.10941) discusses an efficient division light method to generate uniform random numbers in an interval. This method is apparently used in the Go language. On 64-bit platforms there are also fast alternative RNGs that perform comparatively on statistical examinations passing tests like BigCrush. The splitmix64 (part of the standard Java API) and lehmer64 RNGs, for example, require approximately 1.5 cycles to generate 32 random bits (without using SIMD) while the 32-bit Mersenne Twister requires approximately 10 cycles per 32 bits.

This talk will discuss the inclusion of Lemire's method in NumPy as an alternative to the current rejection sampling implementation. My implementation results in a 2x - 3x improvement in the performance of generating a sequence of random numbers. Using splitmix64 or lehmer64 RNGs in NumPy instead of the Mersenne Twister results in a further 2x performance improvement.

The random module in Python does not do the rejection sampling in C like NumPy does. Much of the time to get a random number is therefore spent in the Python code. This talk will also discuss a fast random Python module that implements Lemire's method instead of the current rejection sampling, provides alternative RNGs and moves more of the code into C.

I'm considering doing pull requests for both the NumPy modification and the Python fast random module and will present a detailed analysis of the proposed modifications.

Comment:

production notes