Austin Group Defect Tracker

Aardvark Mark IV


Viewing Issue Simple Details Jump to Notes ] Issue History ] Print ]
ID Category Severity Type Date Submitted Last Update
0000743 [1003.1(2013)/Issue7+TC1] Base Definitions and Headers Objection Error 2013-08-29 16:08 2019-06-10 08:55
Reporter eblake View Status public  
Assigned To
Priority normal Resolution Accepted As Marked  
Status Closed  
Name Eric Blake
Organization Red Hat
User Reference ebb.RAND_MAX
Section stdlib.h
Page Number 358
Line Number 12038
Interp Status ---
Final Accepted Text See Note: 0001836.
Summary 0000743: RAND_MAX should guarantee even distribution over a power of 2
Description The current definition of RAND_MAX is too weak to be easily useful. Random numbers are most useful if you can easily combine a small number of random bits into a larger random number; but for that to be easy, the random numbers need to be evenly distributed over a complete power-of-2 range.

FreeBSD 10 recently experimented with changing RAND_MAX to be a non power-of-2 bitmask:
http://lists.freebsd.org/pipermail/svn-src-head/2013-July/049068.html [^]
with the result that it causes compilation failures in programs that had previously been able to exploit the fact that random numbers were evenly distributed over a power of 2 and could be concatenated:
https://www.redhat.com/archives/libvir-list/2013-August/msg01546.html [^]

There is a related XSI requirement that rand() have a period of at least 2**32 (line 56191), but there appears to be no requirement between the period of rand and the size of RAND_MAX (other than the implicit requirement that on a non-XSI system, a period of 2**16 would be permitted, and that RAND_MAX probably ought not to be larger than the period).
Desired Action At page 358 line 12038 (XBD <stdlib.h> RAND_MAX), change:

Maximum value returned by rand( ); at least 32 767.

to

Maximum value returned by rand( ); at least 32 767, and shall be one less than a power of two.
Tags tc2-2008
Attached Files

- Relationships
related to 0000859Closed Add posix_random family of interfaces 

-  Notes
(0001772)
eblake (manager)
2013-08-29 16:11

Since rand() comes from C99, we may need CX shading on the proposed addition; we probably also ought to involve the C committee.
(0001774)
dalias (reporter)
2013-08-29 17:34

Regarding this:

"Random numbers are most useful if you can easily combine a small number of random bits into a larger random number..."

Doing so is not so easy, and rand() does not provide sufficient quality to facilitate this use. Combining a small number of pseudorandom bits to make a larger pseudorandom number does not produce a uniform distribution. In particular, if rand() has period 2^N, then no matter how you combine the bits, it can never produce a uniform distribution on the range [0,2^(M-1)] for any value of M larger than N without additional state external to rand(), simply because the period cannot be increased.

As a degenerate example (obviously non-conforming, but instructive), take RAND_MAX=1 where rand() alternatively 0 and 1 and suppose you want to generate numbers in the range [0,3]. No matter how you combine the output bits of rand(), you will get at most two output values. If you use the most naive combination (simple concatenation), you halve the period and only get one output value.

I think POSIX should just discourage use of rand(). It's not thread-safe, and the rand_r variant is even worse in that its period is bounded by UINT_MAX+1 which is way too small to be useful. The other PRNG functions random() and *rand48() are much better (but still fairly low quality) choices.
(0001775)
eblake (manager)
2013-08-29 17:43

Is it worth considering the standardization of glibc's random_r(), which allows thread-safe use of random()?
(0001776)
dalias (reporter)
2013-08-29 18:06

random() already is thread-safe. The only limitation is that it does not easily facilitate having independent/reproducible random number sequences on a per-thread/per-context basis. I guess the question is whether this is a sufficiently restrictive limitation to merit adding random_r() to the standard.

[ejn]rand48() are fully thread-safe and use caller-provided context, but unfortunately 48 bits of state is on the very low end of what I would call usable quality for a LCG-based PRNG. Now that C and POSIX require the existence of 64-bit types, you can write a superior LCG-based PRNG with period 2^64 as a one-line function; adding a simple tempering operation onto the result yields sufficient statistical quality that such a PRNG is usable for basically anything but cryptographic purposes. And just including your own such implementation has the advantage of producing identical results everywhere, and being fully portable.
(0001777)
eblake (manager)
2013-08-29 18:49

But obviously there is a (rather large) proportion of programmers that DON'T know how to write a proper PRNG, and having a standardized generator with a tempering function atop a 2^64 period and per-thread user-selectable seeding, along with both strongly encouraging it in preference over the existing standardized functions, as well as strongly documenting its pitfalls when compared with truly random data, is something that will at least cause non-experts in the field to have a decent chance of not screwing themselves over by using the wrong random source for their needs.
(0001778)
philip-guenther (reporter)
2013-08-29 20:06

> ... along with both strongly encouraging it in preference over the existing
> standardized functions, as well as strongly documenting its pitfalls when
> compared with truly random data, is something that will at least cause non-experts
> in the field to have a decent chance of not screwing themselves over by using
> the wrong random source for their needs.

I find it depressing that effort would be spent on adding *new* PRNGs to the standard when the standard provides no way for programs to get the system's best approximation of *real* random data, not even to seed those long-cycle PRNGs.

An application that needs a better PRNG _can_ provide it itself. Contrast that with getting real random data, which generally requires special privileges for hardware or instruction-set access and therefore can only be reliably provided by the OS/system.

I guess we'll end up with programs using PRNGs with 2^64 period...and seeded with the traditional getpid()^time(NULL). WOMBAT.
(0001836)
Don Cragun (manager)
2013-09-19 16:21
edited on: 2013-09-19 16:22

In rand() on P1749 L56250, change:
The drand48( ) function provides a much more elaborate random 
number generator.

to:
The drand48() and random() functions provide much more elaborate
pseudo-random number generators.


On P1749, L56253-56254, change:
Therefore this function should be avoided whenever non-trivial
requirements (including safety) have to be fulfilled.

to a new paragraph:
These functions should be avoided whenever non-trivial requirements
(including safety) have to be fulfilled.


In P1750, L56273 "see also" section, add random()

In drand48() on P744 L25096 application usage, change "none" to:
These functions should be avoided whenever non-trivial requirements
(including safety) have to be fulfilled.


In P744 L25102 "see also" section of drand48(), add random()

In initstate() on P1128 add a new paragraph after L37891:
These functions should be avoided whenever non-trivial requirements
(including safety) have to be fulfilled.



- Issue History
Date Modified Username Field Change
2013-08-29 16:08 eblake New Issue
2013-08-29 16:08 eblake Name => Eric Blake
2013-08-29 16:08 eblake Organization => Red Hat
2013-08-29 16:08 eblake User Reference => ebb.RAND_MAX
2013-08-29 16:08 eblake Section => stdlib.h
2013-08-29 16:08 eblake Page Number => 358
2013-08-29 16:08 eblake Line Number => 12038
2013-08-29 16:08 eblake Interp Status => ---
2013-08-29 16:11 eblake Note Added: 0001772
2013-08-29 16:11 eblake Tag Attached: c99
2013-08-29 17:34 dalias Note Added: 0001774
2013-08-29 17:43 eblake Note Added: 0001775
2013-08-29 18:06 dalias Note Added: 0001776
2013-08-29 18:49 eblake Note Added: 0001777
2013-08-29 20:06 philip-guenther Note Added: 0001778
2013-09-19 16:21 Don Cragun Note Added: 0001836
2013-09-19 16:22 Don Cragun Note Edited: 0001836
2013-09-19 16:23 Don Cragun Final Accepted Text => See Note: 0001836.
2013-09-19 16:23 Don Cragun Status New => Resolved
2013-09-19 16:23 Don Cragun Resolution Open => Accepted As Marked
2013-09-19 16:23 Don Cragun Tag Attached: tc2-2008
2013-09-19 16:24 Don Cragun Tag Detached: c99
2014-12-02 00:27 eblake Relationship added related to 0000859
2019-06-10 08:55 agadmin Status Resolved => Closed


Mantis 1.1.6[^]
Copyright © 2000 - 2008 Mantis Group
Powered by Mantis Bugtracker