# How to efficiently generate large, uniformly distributed, random integers in bash?

I have been wondering what would be the best way to get good randomness in bash, i.e., what would be a procedure to get a random positive integer between `MIN` and `MAX` such that

1. The range can be arbitrarily large (or at least, say, up to 232-1);
2. Values are uniformly distributed (i.e., no bias);
3. It is efficient.

An efficient way to get randomness in bash is to use the `\$RANDOM` variable. However, this only samples a value between 0 and 215-1, which may not be large enough for all purposes. People typically use a modulo to get it into the range they want, e.g.,

``````MIN=0
MAX=12345
rnd=\$(( \$RANDOM % (\$MAX + 1 - \$MIN) + \$MIN ))
``````

This, additionally, creates a bias unless `\$MAX` happens to divide 215-1=32767. E.g., if `\$MIN` is 0 and `\$MAX` is 9, then the values 0 through 7 are slightly more probable than the values 8 and 9, as `\$RANDOM` will never be 32768 or 32769. This bias gets worse as the range increases, e.g., if `\$MIN` is 0 and `\$MAX` is 9999, then the numbers 0 through 2767 have a probability of 4/32767, while the numbers 2768 through 9999 only have a probability of 3/32767.

So while the above method fulfills condition 3, it does not fulfill conditions 1 and 2.

The best method that I came up with so far in trying to satisfy conditions 1 and 2 was to use `/dev/urandom` as follows:

``````MIN=0
MAX=1234567890
while
rnd=\$(cat /dev/urandom | tr -dc 0-9 | fold -w\${#MAX} | head -1 | sed 's/^0*//;')
[ -z \$rnd ] && rnd=0
(( \$rnd < \$MIN || \$rnd > \$MAX ))
do :
done
``````

Basically, just collect randomness from `/dev/urandom` (might consider to use `/dev/random` instead if a cryptographically strong pseudorandom number generator is desired, and if you have lots of time, or else maybe a hardware random number generator), delete every character that's not a decimal digit, fold the output to the length of `\$MAX` and cut leading 0's. If we happened to only get 0's then `\$rnd` is empty, so in this case set `rnd` to `0`. Check if the result is outside our range and if so, then repeat. I forced the "body" of the while loop into the guard here so as to force execution of the body at least once, in the spirit of emulating a `do ... while` loop, since `rnd` is undefined to start with.

I think I fulfilled conditions 1 and 2 here, but now I screwed up condition 3. It's kinda slow. Takes up to a second or so (tenth of a second when I'm lucky). Actually, the loop is not even guaranteed to terminate (although the probability of termination converges to 1 as time increases).

Is there an efficient way to get unbiased random integers, within a pre-specified and potentially large range, in bash? (I'll continue to investigate when time allows, but in the meantime I thought someone here might have a cool idea!)

1. The most basic (and hence portable) idea is to generate a random bitstring just long enough. There are different ways of generating a random bitstring, either using bash's built-in `\$RANDOM` variable or using `od` and `/dev/urandom` (or `/dev/random`). If the random number is greater than `\$MAX`, start over.

2. Alternatively, it is possible to use external tools.

• The Perl solution
• Pro: quite portable, simple, flexible
• Contra: not for very large numbers above 232-1
• The Python solution
• Pro: simple, flexible, works even for large numbers
• Contra: less portable
• The zsh solution
• Pro: good for people who use zsh anyway
• Contra: probably even less portable
• Why pick out only integers, instead of base64-encoding the random bits, then converting a certain number of characters (depending on the range needed) from the encoded form to base10 from base64? – muru Sep 24 '14 at 14:14
• Does it need to be bash? Would something like `rand=\$(command)` do if `command` returns an iteger that fulfills your requirements? – terdon Sep 24 '14 at 14:18
• @muru It's a nice idea actually. I had spent some thought on a similar idea, using `dd if=/dev/urandom 2>/dev/null` and piping that through `od -t d` (avoids the detour through base64), but it's not clear to me how the conversion happens and whether it is indeed unbiased. If you can expand your idea to an efficient, working script and explain why there's no bias, it would make for a great answer. :) – Malte Skoruppa Sep 24 '14 at 14:21
• @terdon I would prefer bash. I mean, of course you can invoke `python` or `perl` or your favorite language, but this is not available everywhere. I'd prefer something more portable. Well, `awk`'s random function would be fine, I guess. But the more portable, the better :) – Malte Skoruppa Sep 24 '14 at 14:32
• Yes, I was thinking along the lines of `perl -e 'print int(rand(2**32-1))');`. That is pretty darn portable and will be very fast. Awk won't cut it since most implementations start from the same seed. So you get the same random number on subsequent runs. It only changes within the same run. – terdon Sep 24 '14 at 14:32

I see another interesting method from here.

``````rand=\$(openssl rand 4 | od -DAn)
``````

This one also seems to be a good option. It reads 4 bytes from the random device and formats them as unsigned integer between `0` and `2^32-1`.

``````rand=\$(od -N 4 -t uL -An /dev/urandom | tr -d " ")
``````
• you should use `/dev/urandom` unless you know that you need `/dev/random`; `/dev/random` blocks on Linux. – jfs Sep 24 '14 at 17:32
• why are `od` commands different. Both just print 4-bytes unsigned integers: 1st -- from openssl, 2nd -- from `/dev/random`. – jfs Sep 24 '14 at 17:42
• @Ramesh I edited to use `/dev/urandom` instead of `/dev/random` - I see no reason to use `/dev/random`, and it can be really expensive/slow, or slow down other parts of the system. (Feel free do edit back and explain if it is really needed.) – Volker Siegel Sep 25 '14 at 13:10
• No worries, it's really surprising that this simple difference has so complicated effects. That's why I insisted to change the example to the right one - people learn from examples. – Volker Siegel Sep 25 '14 at 14:51
• @MalteSkoruppa: `I` stands for `sizeof(int)` that may be less than `4` in principle. btw, `od -DAn` fails for `(2**32-1)` but `od -N4 -tu4 -An` continues to work. – jfs Sep 26 '14 at 10:20

Thank you all for all your great answers. I ended up with the following solution, that I would like to share.

Before I go into any more detail about the whys and hows, here's the tl;dr: my shiny new script :-)

``````#!/usr/bin/env bash
#
# Generates a random integer in a given range

# computes the ceiling of log2
# i.e., for parameter x returns the lowest integer l such that 2**l >= x
log2() {
local x=\$1 n=1 l=0
while (( x>n && n>0 ))
do
let n*=2 l++
done
echo \$l
}

# uses \$RANDOM to generate an n-bit random bitstring uniformly at random
#  (if we assume \$RANDOM is uniformly distributed)
# takes the length n of the bitstring as parameter, n can be up to 60 bits
get_n_rand_bits() {
local n=\$1 rnd=\$RANDOM rnd_bitlen=15
while (( rnd_bitlen < n ))
do
rnd=\$(( rnd<<15|\$RANDOM ))
let rnd_bitlen+=15
done
echo \$(( rnd>>(rnd_bitlen-n) ))
}

# alternative implementation of get_n_rand_bits:
# uses /dev/urandom to generate an n-bit random bitstring uniformly at random
#  (if we assume /dev/urandom is uniformly distributed)
# takes the length n of the bitstring as parameter, n can be up to 56 bits
get_n_rand_bits_alt() {
local n=\$1
local nb_bytes=\$(( (n+7)/8 ))
echo \$(( rnd>>(nb_bytes*8-n) ))
}

# for parameter max, generates an integer in the range {0..max} uniformly at random
# max can be an arbitrary integer, needs not be a power of 2
rand() {
local rnd max=\$1
# get number of bits needed to represent \$max
local bitlen=\$(log2 \$((max+1)))
while
# could use get_n_rand_bits_alt instead if /dev/urandom is preferred over \$RANDOM
rnd=\$(get_n_rand_bits \$bitlen)
(( rnd > max ))
do :
done
echo \$rnd
}

# MAIN SCRIPT

# check number of parameters
if (( \$# != 1 && \$# != 2 ))
then
cat <<EOF 1>&2
Usage: \$(basename \$0) [min] max

Returns an integer distributed uniformly at random in the range {min..max}
min defaults to 0
(max - min) can be up to 2**60-1
EOF
exit 1
fi

# If we have one parameter, set min to 0 and max to \$1
# If we have two parameters, set min to \$1 and max to \$2
max=0
while (( \$# > 0 ))
do
min=\$max
max=\$1
shift
done

# ensure that min <= max
if (( min > max ))
then
echo "\$(basename \$0): error: min is greater than max" 1>&2
exit 1
fi

# need absolute value of diff since min (and also max) may be negative
diff=\$((max-min)) && diff=\${diff#-}

echo \$(( \$(rand \$diff) + min ))
``````

Save that to `~/bin/rand` and you have at your availability a sweet random function in bash that can sample an integer in a given arbitrary range. The range may contain negative and positive integers and can be up to 260-1 in length:

``````\$ rand
Usage: rand [min] max

Returns an integer distributed uniformly at random in the range {min..max}
min defaults to 0
(max - min) can be up to 2**60-1
\$ rand 1 10
9
\$ rand -43543 -124
-15757
\$ rand -3 3
1
\$ for i in {0..9}; do rand \$((2**60-1)); done
777148045699177620
456074454250332606
95080022501817128
993412753202315192
527158971491831964
336543936737015986
1034537273675883580
127413814010621078
758532158881427336
924637728863691573
``````

All ideas by the other answerers were great. The answers by terdon, J.F. Sebastian, and jimmij used external tools to do the task in a simple and efficient manner. However, I preferred a true bash solution for maximum portability, and maybe a little bit, simply out of love for bash ;)

Ramesh's and l0b0's answers used `/dev/urandom` or `/dev/random` in combination with `od`. That's good, however, their approaches had the disadvantage of only being able to sample random integers in the range 0 to 28n-1 for some n, since this method samples bytes, i.e., bitstrings of length 8. These are quite big jumps with increasing n.

Finally, Falco's answer describes the general idea how this could be done for arbitrary ranges (not only powers of two). Basically, for a given range `{0..max}`, we can determine what the next power of two is, i.e., exactly how many bits are required to represent `max` as a bitstring. Then we can sample just that many bits and see whether this bistring, as an integer, is greater than `max`. If so, repeat. Since we sample just as many bits as are required to represent `max`, each iteration has a probability greater or equal than 50% of succeeding (50% in the worst case, 100% in the best case). So this is very efficient.

My script is basically a concrete implementation of Falco's answer, written in pure bash and highly efficient since it uses bash's built-in bitwise operations to sample bitstrings of the desired length. It additionally honors an idea by Eliah Kagan that suggests to use the built-in `\$RANDOM` variable by concatening bitstrings resulting from repeated invocations of `\$RANDOM`. I actually implemented both the possibilities to use `/dev/urandom` and `\$RANDOM`. By default the above script uses `\$RANDOM`. (And ok, if using `/dev/urandom` we need od and tr, but these are backed by POSIX.)

# So how does it work?

Before I get into this, two observations:

1. It turns out bash can't handle integers larger than 263-1. See for yourself:

``````\$ echo \$((2**63-1))
9223372036854775807
\$ echo \$((2**63))
-9223372036854775808
``````

It would appear that bash internally uses signed 64-bit integers to store integers. So, at 263 it "wraps around" and we get a negative integer. So we can't hope to get any range larger than 263-1 with whatever random function we use. Bash simply can't handle it.

2. Whenever we want to sample a value in an arbitrary range between `min` and `max` with possibly `min != 0`, we can simply sample a value between `0` and `max-min` instead and then add `min` to the final result. This works even if `min` and possibly also `max` are negative, but we need to be careful to sample a value between `0` and the absolute value of `max-min`. So then, we can focus on how to sample a random value between `0` and an arbitrary positive integer `max`. The rest is easy.

Step 1: Determine how many bits are needed to represent an integer (the logarithm)

So for a given value `max`, we want to know just how many bits are needed to represent it as a bitstring. This is so that later we can randomly sample only just as many bits as are needed, which makes the script so efficient.

Let's see. Since with `n` bits, we can represent up to the value 2n-1, then the number `n` of bits needed to represent an arbitrary value `x` is ceiling(log2(x+1)). So, we need a function to compute the ceiling of a logarithm to the base 2. It is rather self-explanatory:

``````log2() {
local x=\$1 n=1 l=0
while (( x>n && n>0 ))
do
let n*=2 l++
done
echo \$l
}
``````

We need the condition `n>0` so if it grows too great, wraps around and becomes negative, the loop is guaranteed to terminate.

Step 2: Sample a random a bitstring of length `n`

The most portable ideas are to either use `/dev/urandom` (or even `/dev/random` if there is a strong reason) or bash's built-in `\$RANDOM` variable. Let's look at how to do it with `\$RANDOM` first.

Option A: Using `\$RANDOM`

This uses the idea mentioned by Eliah Kagan. Basically, since `\$RANDOM` samples a 15-bit integer, we can use `\$((RANDOM<<15|RANDOM))` to sample a 30-bit integer. That means, shift a first invocation of `\$RANDOM` by 15 bits to the left, and apply a bitwise or with a second invocation of `\$RANDOM`, effectively concatening two independently sampled bitstrings (or at least as independent as bash's built-in `\$RANDOM` goes).

We can repeat this to obtain a 45-bit or 60-bit integer. After that bash can't handle it anymore, but this means we can easily sample a random value between 0 and 260-1. So, to sample an n-bit integer, we repeat the procedure until our random bitstring, whose length grows in 15-bit steps, has a length greater or equal than n. Finally, we cut off the bits that are too much by appropriately bitwise shifting to the right, and we end up with a n-bit random integer.

``````get_n_rand_bits() {
local n=\$1 rnd=\$RANDOM rnd_bitlen=15
while (( rnd_bitlen < n ))
do
rnd=\$(( rnd<<15|\$RANDOM ))
let rnd_bitlen+=15
done
echo \$(( rnd>>(rnd_bitlen-n) ))
}
``````

Option B: Using `/dev/urandom`

Alternatively, we can use `od` and `/dev/urandom` to sample an n-bit integer. `od` will read bytes, i.e., bitstrings of length 8. Similarly as in the previous method, we sample just so many bytes that the equivalent number of sampled bits is greater or equal than n, and cut off the bits that are too much.

The lowest number of bytes needed to get at least n bits is the lowest multiple of 8 that is greater or equal than n, i.e., floor((n+7)/8).

This only works up to 56-bit integers. Sampling one more byte would get us an 64-bit integer, i.e., a value up to 264-1, which bash can't handle.

``````get_n_rand_bits_alt() {
local n=\$1
local nb_bytes=\$(( (n+7)/8 ))
echo \$(( rnd>>(nb_bytes*8-n) ))
}
``````

Putting the pieces together: Get random integers in arbitrary ranges

We can sample `n`-bit bitstrings now, but we want to sample integers in a range from `0` to `max`, uniformly at random, where `max` may be arbitrary, not necessarily a power of two. (We can't use modulo as that creates a bias.)

The whole point why we tried so hard to sample just as many bits as are needed to represent the value `max`, is that we can now safely (and efficiently) use a loop to repeatedly sample an `n`-bit bitstring until we sample a value that is lower or equal to `max`. In the worst case (`max` is a power of two), each iteration terminates with a probability of 50%, and in the best case (`max` is a power of two minus one), the first iteration terminates with certainty.

``````rand() {
local rnd max=\$1
# get number of bits needed to represent \$max
local bitlen=\$(log2 \$((max+1)))
while
# could use get_n_rand_bits_alt instead if /dev/urandom is preferred over \$RANDOM
rnd=\$(get_n_rand_bits \$bitlen)
(( rnd > max ))
do :
done
echo \$rnd
}
``````

Wrapping things up

Finally, we want to sample integers between `min` and `max`, where `min` and `max` can be arbitrary, even negative. As previously mentioned, this is now trivial.

Let's put it all in a bash script. Do some argument parsing stuff... We want two arguments `min` and `max`, or only one argument `max`, where `min` defaults to `0`.

``````# check number of parameters
if (( \$# != 1 && \$# != 2 ))
then
cat <<EOF 1>&2
Usage: \$(basename \$0) [min] max

Returns an integer distributed uniformly at random in the range {min..max}
min defaults to 0
(max - min) can be up to 2**60-1
EOF
exit 1
fi

# If we have one parameter, set min to 0 and max to \$1
# If we have two parameters, set min to \$1 and max to \$2
max=0
while (( \$# > 0 ))
do
min=\$max
max=\$1
shift
done

# ensure that min <= max
if (( min > max ))
then
echo "\$(basename \$0): error: min is greater than max" 1>&2
exit 1
fi
``````

...and, finally, to sample uniformly at random a value between `min` and `max`, we sample a random integer between `0` and the absolute value of `max-min`, and add `min` to the final result. :-)

``````diff=\$((max-min)) && diff=\${diff#-}

echo \$(( \$(rand \$diff) + min ))
``````

Inspired by this, I might try to use dieharder to test and benchmark this PRNG, and put my findings in here. :-)

• your solution assumes that `sizeof(int) == 8` (64bit) due to `--format=u` – jfs Sep 27 '14 at 14:01
• your solution reminds me how random.py is written. `random.Random` class uses 53bit? generator to return arbitrary large random numbers (multiple invocations), `random.SystemRandom` does the same using `os.urandom()` that can be implemented using `/dev/urandom`. – jfs Sep 27 '14 at 14:05
• uL implies sizeof(long)>=8 for the range. It is not guaranteed. You could use u8 to assert that platform has such integer. – jfs Sep 27 '14 at 22:39
• @J.F.Sebastian I was thinking that so far my script does not hard-code any assumptions about the size of a long int. Potentially, it would work even if the size of a long signed int was greater (or lower) than 64 bits, e.g., 128 bits. However, if I use `--format=u8` then I hardcode the assumption `sizeof(int)==8`. On the other hand, if use `--format=uL` there's no problem: I don't think there is a platform that has 64-bit integers but still defines long ints as something lower. So basically I would argue `--format=uL` allows for more flexibility. What are your thoughts? – Malte Skoruppa Sep 29 '14 at 18:18
• there is `long long` that can be 64bit while int=long=32bit on some platforms. You should not claim 0..2**60 range if you can't guarantee it on all platforms. On the other hand bash might not support this range itself on such platforms (I don't know, perhaps it uses maxint_t and then u8 is more correct if you want to assert the fixed range (`od` doesn't support specifying maxint if yours range is whatever bash's platform-dependent? range is). If the bash range depends on sizeof long then uL might be more appropriate). Do you want the full range that bash supports on all OSes or a fixed range? – jfs Sep 30 '14 at 0:23

Can it be zsh?

``````max=1000
integer rnd=\$(( \$(( rand48() )) * \$max ))
``````

You may want to use seed as well with `rand48(seed)`. See `man zshmodules` and `man 3 erand48` for detailed description if interested.

• I personally don't use zsh, but this is a great addition :) – Malte Skoruppa Sep 24 '14 at 20:18
``````\$ python -c 'import random as R; print(R.randint(-3, 5**1234))'
``````

`python` is available on Redhat, Debian-based systems.

If you want a number from 0 through (2^n)-1 where n mod 8 = 0 you can simply get n / 8 bytes from `/dev/random`. For example, to get the decimal representation of a random `int` you could:

``````od --read-bytes=4 --address-radix=n --format=u4 /dev/random | awk '{print \$1}'
``````

If you want to take just n bits you can first take ceiling(n / 8) bytes and right shift to the amount you want. For example if you want 15 bits:

``````echo \$((\$(od --read-bytes=2 --address-radix=n --format=u4 /dev/random | awk '{print \$1}') >> 1))
``````

If you are absolutely sure that you don't care about the quality of the randomness and you want to guarantee a minimal run time you can use `/dev/urandom` instead of `/dev/random`. Make sure you know what you are doing before using `/dev/urandom`!

• Thank you. So, get `n` random bytes from `/dev/urandom` and format using `od`. Similar in spirit as this answer. Both are equally good :) Though both have the disadvantage of having a fixed range of 0 through 2^(n*8)-1 bits, where n is the number of bytes. I would prefer a method for an arbitrary range, up to 2^32-1, but also anything lower. This creates the bias difficulty. – Malte Skoruppa Sep 24 '14 at 20:11
• Edited to use `/dev/urandom` instead of `/dev/random` - I see no reason to use `/dev/random`, and it can be really expensive/slow, or slow down other parts of the system. (Feel free do edit back and explain if it is really needed.) – Volker Siegel Sep 25 '14 at 13:16
• It should be the exact opposite: use /dev/urandom unless you know that you need /dev/random. It is incorrect to assume that `/dev/urandom` results are so much worse than `/dev/random` that urandom is not usable in most cases. Once `/dev/urandom` is initialized (at the start of the system); its results are as good as `/dev/random` for almost all applications on Linux. On some systems random and urandom are the same. – jfs Sep 26 '14 at 9:20
• `--format=u` should be replaced with `--format=u4` because `sizeof(int)` may be less than `4` in theory. – jfs Sep 26 '14 at 10:23
• @J.F.Sebastian This paper has a very interesting discussion around this subject. Their conclusion seems to be that both `/dev/random` and `/dev/urandom` are unsatisfactory, and that "Linux should add a secure RNG that blocks until it has collected adequate seed entropy and thereafter behaves like `urandom`." – l0b0 Sep 26 '14 at 12:10

Assuming you don't object to using external tools, this should fulfill your requirements:

``````rand=\$(perl -e 'print int(rand(2**32-1))');
``````

It's using perl's `rand` function which takes an upper limit as a parameter. You can set it to whatever you like. How close this is to true randomness in the abstract mathematical definition is beyond the scope of this site but it should be fine unless you need it for extremely sensitive encryption or the like. Perhaps even there but I won't venture an opinion.

• this breaks for large numbers e.g., 5**1234 – jfs Sep 24 '14 at 19:14
• @J.F.Sebastian yes it does. I posted this since the OP specified `1^32-1` but you need to tweak it for larger numbers. – terdon Sep 24 '14 at 19:30

You should get the nearest (2^X)-1 equal or grater than your desired maximum and get the number of bits. Then just call /dev/random multiple times and append all the bits together until you have enough, truncating all bits which are too much. If the resulting number is bigger than your max repeat. In the worst case you have a greater than 50% chance of getting a random number below your Maximum so (for this worst case) you will take two calls on average.

• This is actually a pretty good idea in order to improve efficiency. Ramesh's answer and l0b0's answer both basically get random bits from `/dev/urandom`, but in both answers it's always a multiple of 8 bits. Truncating the bits which are too much for lower ranges before formatting to decimal with `od` is a good idea to improve efficiency, since the loop only has an expected number of 2 iterations, as you nicely explain. This, combined with either one of the mentioned answers, is probably the way to go. – Malte Skoruppa Sep 24 '14 at 20:23

If you want arbitrarily large numbers, then you could join multiple random numbers in a helper:

``````# \$1 - number of 'digits' of size base
function random_helper()
{
base=32768
random=0
for((i=0; i<\$1; ++i)); do
let "random+=\$RANDOM*(\$base**\$i)"
done
echo \$random
}
``````

If the problem is bias, then just remove it.

``````# \$1 - min value wanted
# \$2 - max value wanted
function random()
{
MAX=32767
min=\$1
max=\$((\$2+1))
size=\$((max-min))
bias_range=\$((MAX/size))
while
random=\$RANDOM
[ \$((random/size)) -eq \$bias_range ]; do :; done
echo \$((random%size+min))
}
``````

Joining these functions together

``````# \$1 - min value wanted
# \$2 - max value wanted
# \$3 - number of 'digits' of size base
function random()
{
base=32768
MAX=\$((base**\$3-1))
min=\$1
max=\$((\$2+1))
size=\$((max-min))
bias_range=\$((MAX/size))
while
random=\$(random_helper)
[ \$((random/size)) -eq \$bias_range ]; do :; done
echo \$((random%size+min))
}
``````