2

How many decimal places will rand() give?

I assume rand() value can't be any completely arbitrary number from 0 up to excluding 1 and that it's limited to a certain amount of decimal places or something like that. Is it based off the operating system or is there some random limit of X decimal places.

Equivalently, I want to know: how precise could rand() be?.

1
2

Take away

Beside the float limitations (no more than 15 decimal digits) explained in detail below, the source code has this additional limitations:

The original awk was limited to only 32768 (0..32767) different values in the rand() function.

/* #ifndef RAND_MAX */  
/* #define RAND_MAX     32767 */        /* all that ansi guarantees */  
/* #endif */

That is a little more than 4 digits, that's all you can trust in old awk.

The mawk implementation has several limits for rand(), form 16 bit up to 32 bit (0..4294967295). So, a bit more than 9 digits.

Oddily, GNU awk will return a 31 bit only from random() (read support/random.c) despite having arbitrary precision math built in. Still a bit more than 9 digits, but half of mawk's arc4random (from BSD) (0..2147483647).


Lets take a deeper look at the float representation in awk, one step at the time.

How many decimal places will rand() give?

Apparent

The apparent answer is: As many as you ask for (yes, most versions):

$ awk 'BEGIN{srand(11); printf("%.83f\n",rand())}'
0.37904318086255550657170942940865643322467803955078125000000000000000000000000000000

The srand(11) is being used to have a repeatable random number generated. Any user should get the same random number (in GNU awk, it may be different for different versions of awk, but stable over repeated calls and computers).

Yes, the count of digits could be much bigger than 83 and that much digits will be dutifully printed.

But it is obvious that after some count, all digits become zero, no matter how much more you ask for.

Effective

If you care to count them:

$ printf '%s' "  " $(seq 9)"_"{,,,,,}; echo; \
    awk 'BEGIN{srand(11); printf("%.63f\n",rand())}';\
    printf '  ';printf '^%.0s' $(seq 53); echo "<--- up to here"

  123456789_123456789_123456789_123456789_123456789_123456789_
0.379043180862555506571709429408656433224678039550781250000000000
  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^<--- up to here

You will find that there are 53 decimal digits (in Linux GNU at least).

Why 53?

That's exactly the same count of binary digits used in the mantissa of the binary floats used to represent numbers in awk. Well, at least with "double precision" floats (8 byte floats) as defined by IEEE 754

Q: Is that the reason? Is the number of binary bits is equal to the number of decimal digits?

A: In one word: yes.

proof

Any binary fraction, i.e. a zero followed by a dot, followed by several binary digits:

0.100110011

Could be written as:

a1×2-1 + a2×2-2 + a3×2-3 + ....

for some sequence of ai binary digits.

For example:

0.100110011
1×2-1 + 0×2-2 + 0×2-3 + 1×2-4 + 1×2-5 + ....

Remove zeros:

2-1 + 2-4 + 2-5 + 2-8 + 2-9

Factor out 2-9:

( 2+8 + 2+5 + 2+4 + 21 + 1 ) × 2-9

What is inside the parenthesis is an integer binary number:

100110011 # (307 in decimal)

This fraction is actually a binary fraction:

307 × 2-9
307 / 29

If we multiply both the numerator and the denominator by 59 we get:

307 × 59 / 29 × 59
307 × 59 / 109
307 × 1953125 / 109
599609375 / 109
0.599609375

A decimal fraction with the same number of digits as the binary fraction.

So, all binary fractions could be converted (exactly) into decimal fractions of the exact same number of digits after the dot (the exponent of the denominator is the same). The reverse is not true. Not all decimal fractions could be converted to binary fractions.

Now that we know how to do it: we could try a longer fraction:

0.10011001100110011001100110011001100110011001100110011
100110011001100110011001100110011001100110011001100112 / 253
540431955284459510 / 253
540431955284459510 × 553 / 1053
5404319552844595 × 11102230246251565404236316680908203125 / 1053
59999999999999997779553950749686919152736663818359375 / 1053
0.59999999999999997779553950749686919152736663818359375

Which is exactly the representation that awk gives to 0.6 in 53 bit:

$ awk 'BEGIN{printf("%.60g\n",0.6)}'
0.59999999999999997779553950749686919152736663818359375

So, the 53 decimal digits is the maximum that awk could give with floats of 53 bit mantissa.

Well, read that as 53 significant digits, as some numbers may have leading zeros:

$ awk 'BEGIN{printf("%.90f\n",3^-20)}'
0.000000000286797199079244134930566254988964884631297280748185585252940654754638671875000000

Free digits.

Q: But all floats (decimal fractions) end in a 5, is there some underlying force that makes the digits not random?

A: Yes.

Description

Any binary digit has an exact representation in decimal. As explained above a binary fraction is:

a1×2-1 + a2×2-2 + a3×2-3 + ....

for some sequence of ai. And the value of each exponent is perfectly known:

2-1 = 0.5
2-2 = 0.25
2-3 = 0.125
2-4 = 0.0625
2-5 = 0.03125
2-6 = 0.015625
2-7 = 0.0078125
2-8 = 0.00390625
2-9 = 0.001953125
2-10 = 0.0009765625
...

We can see why and how a number like 0.6 is being approximated with successive binary fractions.
Each successive fraction added has to be from below. All fractions are added, there is no way to go back to a smaller value.

2-1 = 0.5 ==> 0.5

The first binary digit contributes with 0.5, we are 0.1 away from 0.6. The next: 0.25 and the one following 0.125 are bigger than what needs to be added. So, they could not be used. The next two could be added. The first one 2-4 (0.0625) is smaller than the 0.1 difference and could be added. The second 2-5 (0.03125) is smaller than the 0.375 difference left by the first and also could be added.

2<sup>-1</sup>   = 0.5                     ==> 0.5
2<sup>-4</sup>   = 0.0625                  ==> 0.5625
2<sup>-5</sup>   = 0.03125                 ==> 0.59375
----------------------^ <== digit being approximated
-----------------------*** <== trailing digits of each fraction.

And with each successive binary bit added to the representation of 0.6 the result becomes closer to that value:

2<sup>-8</sup>   = 0.00390625              ==> 0.59765625
2<sup>-9</sup>   = 0.001953125             ==> 0.599609375

2<sup>-12</sup>  = 0.000244140625          ==> 0.599853515625
2<sup>-13</sup>  = 0.0001220703125         ==> 0.5999755859375

2<sup>-16</sup>  = 0.0000152587890625      ==> 0.5999908447265625
2<sup>-17</sup>  = 0.00000762939453125     ==> 0.59999847412109375

2<sup>-20</sup>  = 0.00000095367431640625  ==> 0.59999942779541015625
2<sup>-21</sup>  = 0.000000476837158203125 ==> 0.599999904632568359375    
digit being approximated-------------------------------| <==
Accumulated trailing digits. ---------------------------^^^^^^^^^^^^^^ 

So, by the time we have set the first 6 digits, we have used 21 binary digits, and, by the result above, have generated 21 decimal digits. But those digits are not free. They are tied to the values of the first 6 decimal digits.

However, trying to generate a general rule from specific example is not possible.

In General:

Using higher level math we can say:

Q: How many decimal digits are "valid" for a truncated number of bits?

A: 2^(b-1) >= 10^d - 1

That's the Matula formula from his 1967 paper: D._W.Matula,"Base_conversion_mappings,"_1967_Spring_Joint_Computer_Conf.,_AFIPS_Proc.,_vol._30.,_pp._311-318

applied to decimal digits (d) converted to binary digits (b)

As we usually know how many binary bits a float is able to store, we could solve for d (decimal digits that round trip through b binary digits):

2^(b-1) >= 10^d - 1 # using the > only (remove the - 1)
2^(b-1) > 10^d # Apply log
log10(2) × (b-1) > d

So (max integer):

d = int( log10(2) × (b-1) )
d = int( 0.30102999566 * (b-1) ) # close enough.

 Bits  5 9 13 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73 77 81 85 89 93 97 101 105 109 113  
digits 1 2  3  4  6  7  8  9 10 12 13 14 15 16 18 19 20 21 22 24 25 26 27 28  30  31  32  33

As shown above 21 binary bits generate 0.599999904632568359375, but only 6 (rounded) digits could be trusted. The 0.599999 must be rounded up to 0.6 as the next digit is 9.

So: 0.6 round trips to binary and becomes 0.6 again.
With 21 binary bits: up to 6 decimal digits are converted reliably.

Final

So, how many (valid) digits could rand generate:

As many as the float used could convert back from binary. (use above table).

No more than 15 digits could be trusted for a 53 bit binary.

Use:

$ awk -M -vPREC=101 'BEGIN{printf("%.33g\n",0.6)}'
0.599999999999999999999999999999921

If you require at least 30 decimal digits from a float.

But there are other limiting issues, like the number of bits used in the LFSR code. That is the limit mentioned at the start of this answer.

1

I'm in GNU Awk 4.1.3, API: 1.1 (GNU MPFR 3.1.4, GNU MP 6.1.0)

I created a million random numbers to 10-digit accuracy, and got 999744 unique values. The values don't cut off that I can see. However, the high values seem to duplicate more than the low ones, and to reduce quicker than the low ones grow, so I'm not sure the distribution is linear.

Paul--) echo 1000000 | 
> awk 'BEGIN { srand();}
> { for (j = 0; j < $1; j++) 
>   printf ("%12.10f\n", rand()); }' > foo.rand
Paul--) wc foo.rand
 1000000  1000000 13000000 foo.rand
Paul--) sort foo.rand | uniq | wc -l
999744
Paul--) sort foo.rand | uniq -c | sort -n | head -n 5
  1 0.0000011418
  1 0.0000023860
  1 0.0000025611
  1 0.0000035479
  1 0.0000037365
Paul--) sort foo.rand | uniq -c | sort -nr | head -n 5
  2 0.9966602395
  2 0.9950194126
  2 0.9909849539
  2 0.9852069067
  2 0.9822554230
3
  • FWIW with val=sprintf("%.100f",rand()); sub(/0+$/,"",val); printf "%s\n", val I got max 42 decimal places on a 1 million sample with gawk 5.01 with cygwin. idk how useful that is, just throwing it out there. – Ed Morton Feb 1 '20 at 21:22
  • The GNU Awk Users Guide (believed to be generally authoritative) refers to an alternative randomiser method: www.gnu.org/software/gawk/manual/gawk.html#Cliff-Random-Function – Paul_Pedant Feb 8 '20 at 13:36
  • You are looking only at the lowest non-dupe and highest dupe values; if you look at all 256 dupes you will find them spread across the whole range, and if you look at all the non-dupes you will find them also covering the whole range but 4000 times more densely. – dave_thompson_085 Oct 27 '20 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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