3

I ran the following command to generate 1 billion random numbers:

time shuf -i 1-1000000000 > "SHUF TEST 1"

To my surprise it was able to do this in less than 10 mins. I then ran the output file through uniq -d to determine how many of the generated numbers were duplicate, and was again surprised when it turned out to be 0. I also ran the output file through uniq -u and sort -u to confirm these results.

How is it that the shuf command is able to generate a billion random numbers in such a relatively short amount of time, and can I depend on its randomness? Note that I don't need a cryptographically secure random number generator for my needs, just something good enough to always return a unique number.

Improve this question
6
  • 1
    to determine how many of the generated numbers were duplicate, and was again surprised when it turned out to be 0 – shuf does not generate random numbers, it generates random permutation, random order. With -i 1-1000000000 one should expect each integer from this range to appear exactly once. No surprise at all.
    – Kamil Maciorowski
    Jun 30, 2020 at 17:23
  • 1
    As @KamilMaciorowski states, a "shuffling" algorithm creates an array of number 1 to n, then randomly switches pairs of numbers. Does it matter if the order is exactly duplicated each time it's run? Some algorithms start the random number generator at the same pint each time.
    – DrMoishe Pippik
    Jun 30, 2020 at 19:29
  • 1
    I'm surprised that nobody mentioned the -r option. If it is given, shuf will generate random numbers; from 1 to 1000000000 inclusive in this case. There is also the --random-source option.
    – beroal
    Mar 28 at 11:27
  • 1
    "Careful, shuf is not cryptographically safe by default! You need to pass --random-source=/dev/urandom to get a proper RNG." news.ycombinator.com/item?id=14846285
    – beroal
    Mar 28 at 11:31
  • 1
    "The shuf, shred, and sort commands sometimes need random data to do their work. For example, sort -R must choose a hash function at random, and it needs random data to make this selection. By default, these commands use an internal pseudo-random generator initialized by a small amount of entropy, but can be directed to use an external source with the --random-source=file option." gnu.org/software/coreutils/manual/html_node/Random-sources.html
    – beroal
    Mar 28 at 11:33

1 Answer 1

Reset to default
1

The shuf utility shuffles its input by outputting a random permutation of its input lines. According to it's manpage, "Each output permutation is equally likely". An analogy would be to shuffle a deck of cards.

If the input lines contain duplicates, the output from shuf will also contain duplicates. Why? Because shuf performs a random permutation of it's input. If the input lines contain no duplicates, the output from shuf will contain no duplicates.

In your example, shuf -i 1-1000000000, the -i option causes shuf to act as if it's input came from a file containing the range of unsigned decimal integers 1 through 1000000000, one unsigned integer per line. In other words, shuf acts as if it had 1000000000 lines of input with each line containing a unique unsigned integer. Hence there are no duplicates to be found in the output.

Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .