Hacker News Reader

Comment by Retr0id | Hacker News Reader

By the way, the example snippet given to "echo a random number between 1 and 10" is incorrect, pedantically speaking. It's random, but not uniformly so. It's biased towards lower numbers (1-6).

View on HN

Why? Wiki doesn't say anything about it and when I run it, the result looks fine

> $ for((i=1;i<10000;i+=1)); do cat /dev/urandom | od -N 1 -An -i | awk '{print $1 % 10 + 1}' >> rand.txt ; done

> $ cat rand.txt | sort | uniq -c

`cat /dev/urandom | od -N 1 -An -i` gives you a uniform random number between 0 and 255. The following mod 10 in the awk command introduces "modulo bias", which you can read about here https://research.kudelskisecurity.com/2020/07/28/the-definit...

You can see it quite intuitively if you iterate over all possible numbers between 0 and 255:

  $ (for i in {0..255}; do; echo $i | awk '{print $1 % 10 + 1}'; done) | sort -n | uniq -c
     26 1
     26 2
     26 3
     26 4
     26 5
     26 6
     25 7
     25 8
     25 9
     25 10

But that is not how /dev/(u)random works and does not give U(255). Generally speaking, it gives some hash of some user/device activity, from these resources:

https://linuxhint.com/dev_random_vs_dev_urandom/

https://en.wikipedia.org/wiki//dev/random

I know how urandom works (consider reading the articles you linked). The number between 0 and 255 is produced by the `od` command:

https://man7.org/linux/man-pages/man1/od.1.html

> does not give U(255)

What do you think each byte from /dev/(u)random is?

Just to be clear, cryptographic hashes and other outputs of cryptographic primitives are designed to be uniform random. If you find a detectable bias from uniform on the outputs of /dev/urandom then you should consider the underlying primitive (the ChaCha20 stream cipher, in the case of modern Linux urandom) to be broken.

So, is there a correct way to do it in bash?

If you sum the occurrences of numbers 1-6, you get 1051 + 1012 + 1042 + 983 + 1015 + 1042 = 6145. The expected count (if the numbers were uniformly random) is only 6000, on average. If you repeat your experiment, you will find that this sum is greater than 6000 more often than not.

Could someone explain how? I don't grok the command. My best guess is this relates to hexadecimal.

`od -N 1 -An -i` reads one byte from stdin (urandom in this case) and prints it as a decimal string (with value between 0 and 255). The awk command receives that number and prints it back out modulo 10.

Thanks for the explanation!

The calculation maps a random number R in range 0..255 to numbers 1..10 via

    R % 10 + 1

The problem is that 10 does not evenly divide 256, hence for large R, the mapping will be incomplete. Specifically,

with no more random numbers available to yield results 7, 8, 9 and 10.

Thanks for the explanation!

To add to this: (one of) the correct solution(s) is

  R * 10 / 256 + 1

EDIT: I am wrong, this still has bias.

Yeah, an easy solution to all these things is “find a uniformly random source that outputs in a range larger but close to what you want and then try again if it’s outside your range.

And indeed this is how Python does it

https://github.com/python/cpython/blob/e37ac5fbb6de593521cf2...

Reply on news.ycombinator.com