lemire / fastrand Goto Github PK

View Code? Open in Web Editor NEW

83.0 7.0 12.0 60 KB

Fast random number generation in an interval in Python: Up to 10x faster than random.randint.

License: Apache License 2.0

C 75.36% Python 6.29% Shell 18.35%

python prng performance

fastrand's Introduction

fastrand

Fast random number generation in an interval in Python using PCG: Up to 10x faster than random.randint.

Blog post: Ranged random-number generation is slow in Python

Usage... (don't forget to type the above lines in your shell!)

import fastrand

print("generate an integer in [0,1001)")
fastrand.pcg32bounded(1001) 
print("generate an integer in [100,1000]")
fastrand.pcg32randint(100,1000) # requires Python 3.7 or better
print("Generate a random 32-bit integer.")
fastrand.pcg32()

It is nearly an order of magnitude faster than the alternatives:


python3 -m timeit -s 'import fastrand' 'fastrand.pcg32bounded(1001)'
10000000 loops, best of 5: 23.6 nsec per loop

python3 -m timeit -s 'import fastrand' 'fastrand.pcg32randint(100,1000)'
10000000 loops, best of 5: 24.6 nsec per loop

python3 -m timeit -s 'import random' 'random.randint(0,1000)'
1000000 loops, best of 5: 216 nsec per loop

python3 -m timeit -s 'import numpy' 'numpy.random.randint(0, 1000)'
500000 loops, best of 5: 955 nsec per loop

If you have Linux, macOS or Windows, you should be able to do just pip install...

pip install fastrand

You may need root access (sudo on macOS and Linux).

It is sometimes useful to install a specific version, you can do so as follows;

pip install fastrand==1.2.4

Generally, you can build the library as follows (if you have root):

python setup.py build
python setup.py install

python setup.py build
python setup.py install --home=$HOME
export PYTHONPATH=$PYTHONPATH:~/lib/python

Changing the seed and multiple streams

You can change the seed with a function like pcg32_seed. The seed determines the random values you get. Be mindful that naive seeds (e.g., int(time.time())) can deliver poor initial randomness. A few calls to pcg32() may help to boost the improve the randomness. Or else you may try a better seed.
If you need to produce multiple streams of random numbers, merely changing the seed is not enough. You are better off using different increments by calling the pcg32inc. The increments should all be distinct. Note that the least significant bit of the increment is always set to 1 no matter which value you pass: so make sure your increments are distinct 31-bit values (ignoring the least significant bit).

future work

Also look at https://github.com/rkern/line_profiler

Reference

http://www.pcg-random.org
Daniel Lemire, Fast Random Integer Generation in an Interval, ACM Transactions on Modeling and Computer Simulation, Volume 29 Issue 1, February 2019

fastrand's People

Contributors

Stargazers

Watchers

Forkers

barjomet ksdme vishalbelsare eilifm fbarchi cartopy gpaolo ilayshp konstantinos-imagr moneytech vejmin multicomplex

fastrand's Issues

Support for Windows

I know this is not officially supported but is there any way to install this library on Windows?

Enhancment: Add option for bounded randoms such randint in numpy and python.random

Add an option to specify a lower bound for the random int generation.
Examples from numpy and the random lib in python below.

numpy.random.randint(950, 1000)
random.randint(100,1000)

This would make fastrand a better replacement for quickly generating random ints.

pcg32bounded argument check

To match pcg32bounded() doc-string (below), I propose to patch argument check.
Sorry, this should be a pull-request, but I don't know how to use it

generate random integer in the interval [0,range) using PCG.

Since pcg32bounded only allowed 1 argument, the code can be optimized
without overhead of parsing tuple. Just go straight for the number.

This is the full patch:

56,58c56,58
<      int n;
<     if (!PyArg_ParseTuple(args, "i", &n))
<         return NULL;
---
>     int n = PyLong_AsLong(args);   // 1 argument, ok for Python 2 or 3
>     if (n <= 0) return PyErr_Occurred() ? NULL : (Py_INCREF(Py_None), Py_None);
>
98c98
<      {"pcg32bounded", pcg32bounded, METH_VARARGS, "generate random integer in
the interval [0,range) using PCG."},
---
>      {"pcg32bounded", pcg32bounded, METH_O, "generate random integer in the in
terval [0,range) using PCG."},

With the patch, this is benchmark on my laptop:

> python -m timeit -s "import fastrand" "fastrand.pcg32bounded(1001)"
1000000 loops, best of 3: 0.208 usec per loop   -- original
10000000 loops, best of 3: 0.144 usec per loop  -- patched

Error messages now as expected:

>>> from fastrand import *
>>> print pcg32bounded(1001)
82
>>> print pcg32bounded(0)       
None                          # should not return anything
>>> print pcg32bounded(2**31-1), pcg32bounded(-2**31)
20852737 None                 # max input limits
>>> print pcg32bounded(2**31) # overflow 
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: long int too large to convert to int
>>> print pcg32bounded('Hi')  # bad integer
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: an integer is required
>>>

On latest python 2.7 your library is faster

python -m timeit -s 'import fastrand' 'fastrand.pcg32bounded(1001)'
10000000 loops, best of 3: 0.0994 usec per loop

python -m timeit -s 'import numpy' 'numpy.random.randint(0, 1000)'
1000000 loops, best of 3: 1.07 usec per loop

so, I think this should be removed from readme :)

David Andersen points out that
python -m timeit -s 'import numpy' 'numpy.random.randint(0, 1000)'
is much faster.

Add package to pip for macos

Following this issue...
#9

We should now be able to do "pip install fastrand" on Linux and Windows. However, macOS remains unsupported.

Add package to pip

It would be great if you could upload the package so that it can be installed via pip install fastrand. The current process is a bit tedious.

Is it possible to have a seed?

it seems that the numbers that are generated are the same every time a program is run.

How to Guess Upper/Lower bound of a fastrand ?

Hi,

I'm a little novice, who would like to solve the following little problem:

Say I can control when to generate a number using fastrand (bounded for instance by 1001).
How can I guess at best its interval?

I mean:

suppose now, fastrand generate the number 989.
is there a way to figure out a lower/upper bound, such as 900 to 1000, please?

Regards,

Seeding many generators causes fastrand to crash

To reproduce:

python -m timeit -s 'import fastrand' 'fastrand.pcg32_seed(13)'

Fatal Python error: deallocating None

Current thread 0x00000001183f3dc0 (most recent call first):
  File "<timeit-src>", line 6 in inner
  File "/usr/local/Cellar/python/3.7.6_1/Frameworks/Python.framework/Versions/3.7/lib/python3.7/timeit.py", line 176 in timeit
  File "/usr/local/Cellar/python/3.7.6_1/Frameworks/Python.framework/Versions/3.7/lib/python3.7/timeit.py", line 222 in autorange
  File "/usr/local/Cellar/python/3.7.6_1/Frameworks/Python.framework/Versions/3.7/lib/python3.7/timeit.py", line 324 in main
  File "/usr/local/Cellar/python/3.7.6_1/Frameworks/Python.framework/Versions/3.7/lib/python3.7/timeit.py", line 374 in <module>
  File "/usr/local/Cellar/python/3.7.6_1/Frameworks/Python.framework/Versions/3.7/lib/python3.7/runpy.py", line 85 in _run_code
  File "/usr/local/Cellar/python/3.7.6_1/Frameworks/Python.framework/Versions/3.7/lib/python3.7/runpy.py", line 193 in _run_module_as_main
zsh: abort      python -m timeit -s 'import fastrand' 'fastrand.pcg32_seed(13)'

Or from within python:

import fastrand; rngs = [fastrand.pcg32_seed(i) for i in range(100000)]

Fatal Python error: deallocating None

Current thread 0x0000000116acadc0 (most recent call first):
  File "<stdin>", line 1 in <module>
zsh: abort      python

Verified that it happens on multiple OSes (MacOS, ScientificLinux).

"pip install fastrand" prefers to install version1.1 instead of 1.2

Hi to all,

We tried to download latest version of fastrand 1.2.
However "pip install fastrand" ended up installing 1.1
"pip install fastrand --upgrade" also ended up installing 1.1
What can be the reason for that?

Best,
Burcak Otlu

Python3 installation

When installing for Python3.5, at import time it gives an error:

undefined symbol: PyInt_AsUnsignedLongLongMask

to solve it, I had to modify the .c file from:

#if PY_MAJOR_VERSION >= 3
#define PyInt_AsLong(x) PyLong_AsLong(x)
#endif

#if PY_MAJOR_VERSION >= 3
#define PyInt_AsLong(x) PyLong_AsLong(x)
#define PyInt_AsUnsignedLongLongMask(x) PyLong_AsUnsignedLongLongMask(x)
#endif

Seeding

Is there a way to set our own seed for reproducibility purposes? Similarly for ensuring different streams while parallelizing code...

How pcg32_random_bounded_divisionless() work ?

I peek at the code pcg32_random_bounded_divisionless().
Why variable 'leftover' able to reject unbiased randoms ?

No bias if leftover >= range or leftover(updated) >= threshold.
I don't follow above logic ...

Does this produce unbiased ranged number ?
Or, is it an approximation, using your idea in another blog:

https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/

Should the result of pcg32() be signed?

The C function pcg32_random() returns an unsigned uint32_t, but the pcg32() function exposed to Python calls Py_BuildValue() with "i", which causes it to return a signed int (docs). Is this a bug or was it intentional? I don't see this explicitly mentioned anywhere, but I assumed it would give me unsigned 32-bit integers, and I was surprised to see it giving me negative numbers.

How to generate random number 58 bit length ?

Subj.

Thank you for your really fast random number generator.

;)

Error when installing from pip/building

Error:

Collecting fastrand
  Downloading https://files.pythonhosted.org/packages/4a/c9/84ae3fa10cb24bd5ac88845a55ddddc572d165218e29613063763f12d8c4/fastrand-1.7.0.tar.gz
    Complete output from command python setup.py egg_info:
    Traceback (most recent call last):
      File "<string>", line 1, in <module>
      File "/tmp/pip-build-lr57d0c2/fastrand/setup.py", line 9, in <module>
        long_description=open('README.md', 'r').read(),
      File "/usr/lib/python3.5/encodings/ascii.py", line 26, in decode
        return codecs.ascii_decode(input, self.errors)[0]
    UnicodeDecodeError: 'ascii' codec can't decode byte 0xe2 in position 124: ordinal not in range(128)
    
    ----------------------------------------
Command "python setup.py egg_info" failed with error code 1 in /tmp/pip-build-lr57d0c2/fastrand/

Any way to fix this?