View Issue Details
| ID | Project | Category | View Status | Date Submitted | Last Update |
|---|---|---|---|---|---|
| 0000743 | 1003.1(2013)/Issue7+TC1 | Base Definitions and Headers | public | 2013-08-29 16:08 | 2019-06-10 08:55 |
| Reporter | eblake | Assigned To | |||
| Priority | normal | Severity | Objection | Type | Error |
| Status | Closed | Resolution | Accepted As Marked | ||
| 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 0000743: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 | ||||
| related to | 0000859 | Closed | Add posix_random family of interfaces |
|
|
Since rand() comes from C99, we may need CX shading on the proposed addition; we probably also ought to involve the C committee. |
|
|
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. |
|
|
Is it worth considering the standardization of glibc's random_r(), which allows thread-safe use of random()? |
|
|
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. |
|
|
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. |
|
|
> ... 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. |
|
|
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. |
| 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 0000743: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 |
