0
$\begingroup$

When I try to generate decimal numbers in the range 0-18446744073709551616 using a hash function I always get big numbers like this:

$ A=$(date | b2sum -l 64 | awk '{ print $1 }'); echo $(calc 0x$A)
16324260068905187599
$ A=$(date | b2sum -l 64 | awk '{ print $1 }'); echo $(calc 0x$A)
5500525113920202581
$ A=$(date | b2sum -l 64 | awk '{ print $1 }'); echo $(calc 0x$A)
2795550665156396173
$ A=$(date | b2sum -l 64 | awk '{ print $1 }'); echo $(calc 0x$A)
467185138969171643

But I never get small numbers like 10, 98345, 20999, 111 and so on. Is there a way to make a pseudorandom function generate decimal numbers in a specified range being them small or large and not only generate that big numbers as showed above?

Is there a pseudorandom function made specifically for doing this?

$\endgroup$
2
  • $\begingroup$ Please define what are "truly decimal numbers", and explain how under that definition, 16324260068905187599, 5500525113920202581, 2795550665156396173 and 467185138969171643 aren't "truly decimal numbers". $\endgroup$
    – swineone
    Mar 12, 2023 at 23:55
  • $\begingroup$ @swineone Pardon me, I reformulated the question. $\endgroup$
    – alpominth
    Mar 13, 2023 at 0:28

1 Answer 1

2
$\begingroup$

In a good hash function, any output is as likely as any other. It just turns out that there are many more large numbers than small numbers.

To illustrate, you're generating 64-bit numbers, which you could simulate by tossing a coin 64 times and filling in the binary expansion of your random number: say heads is 0 and tails is 1.

Now pick the largest "small number" that you gave as an example, 98345. Its binary expansion, with a fixed 64-bit width, is:

00000000 00000000 00000000 00000000 00000000 00000001 10000000 00101001

Note the 47 leading zeros. It means that, in order to generate numbers as small as 98345 (and in fact up to 131071) your coin would have to land heads for the first 47 throws. Hopefully it's intuitive that this would be really unlikely. In fact, half the time your first throw would land tails, and as such half the time your output will be larger than $2^{63} = 9,223,372,036,854,775,808$.

As for how to generate small numbers, just reduce your 64-bit number modulo a desired value. Say your definition of "small" is numbers with at most 5 decimal digits, i.e. < 100,000; then, all you need to do is reduce your 64-bit numbers modulo 100,000, e.g. using the % operator in awk.

Note that, assuming your 64-bit numbers are uniformly distributed (i.e. every 64-bit number is as likely as every other), then reducing modulo anything but a power of 2 will introduce some bias. In most applications this is not likely to be a problem, but in cryptography it often is. There are techniques to eliminate this bias if you need to; have a look at the answers to this question, for instance.

$\endgroup$
2
  • $\begingroup$ Thank you man, your last link is very interesting. $\endgroup$
    – alpominth
    Mar 13, 2023 at 2:10
  • $\begingroup$ I am sure you meant 2^63, fixed it $\endgroup$
    – kodlu
    Mar 13, 2023 at 2:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.