optimization - Multiplying a huge number times random() (Python)

Question

Problem: Generate large binary strings (length 2000+). Do it quickly, as this generateRandom() function will be called 300,000 times in the algorithm.

Attempted Solutions: Generate 3 or 4 binary numbers and append them all together 500 times. This is awfully slow.

Make a single call to random.random() and multiply it by a huge number. Convert to binary once and be done. This works for smaller numbers, but because the binary string must be a certain length, the number to convert to binary must be truly enormous (2 ** len(binString)).

Current Code (works for smaller numbers):

binaryRepresentation = ''

binaryRepresentation += bin(int(random.random() * (2 ** binLength)))[2:].zfill(binLength)

Error that I need help fixing: This call throws a "long int too large to convert to float" with the large numbers. Is there a way to make the overall algorithm more efficient or to make this large number convert-able to a float?

Thank you!

Answer 1

Measure whether it is fast enough for your purposes, "randomness" might diminish the more you call it: os.urandom(250). It produces a binary string aka bytes.

To avoid "long int too large to convert to float" error don't use floats.

If you need an integer with k random bits instead of a binary string:

import random
r = random.SystemRandom()

n = r.getrandbits(2000) # uses os.urandom() under the hood

To get a string of "0"s and "1"s:

k = 2000
binstr = "{:0{}b}".format(r.getrandbits(k), k)

Note: you can't use randint/randrange for large numbers if getrandbits is not used:

import random

class R(random.Random):
    def random(self): # override random to suppress getrandbits usage
        return random.random()

r = R()
r.randrange(2**2000) # -> OverflowError: long int too large to convert to float

b2a_bin

b2a_bin() extension allows to create binary strings ("01") directly from bytestrings without creating an intermediate Python integer. It is 3-20 times faster than pure Python analogs:

def b2a_bin_bin(data):
    return bin(int.from_bytes(data, 'big', signed=False)
               )[2:].zfill(len(data)*8).encode('ascii', 'strict')

def b2a_bin_format(data):
    n = int.from_bytes(data, 'big', signed=False)
    return "{:0{}b}".format(n, len(data)*8).encode('ascii', 'strict')

Usage:

>>> import os
>>> from b2a_bin import b2a_bin
>>> b2a_bin.b2a_bin(b'x0a')
b'00001010'
>>> b2a_bin(os.urandom(5))
b'1001111011000011111001110010000101111010'