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
0001107 [1003.1(2016/18)/Issue7+TC2] Base Definitions and Headers Editorial Omission 2016-12-08 15:09 2019-10-30 10:28
Reporter EdSchouten View Status public  
Assigned To ajosey
Priority normal Resolution Accepted As Marked  
Status Applied  
Name Ed Schouten
Organization Nuxi
User Reference
Section *rand48()
Page Number -
Line Number -
Interp Status ---
Final Accepted Text Note: 0004040
Summary 0001107: *rand48(): We don't explain how the LCG state is 'transformed into the returned value'
Description The article on *rand48() has the following description of how the return value of these functions is computed:

"The value returned by any of the drand48(), erand48(), jrand48(), lrand48(), mrand48(), or nrand48() functions is computed by first generating the next 48-bit Xi in the sequence. Then the appropriate number of bits, according to the type of data item to be returned, are copied from the high-order (leftmost) bits of Xi and transformed into the returned value."

Unfortunately, the article doesn't go on to mention how this transformation takes place. Is it simple bitshifting, or are implementations allowed to apply rotations, negations, etc? Especially for a deterministic/reproducible PRNG this is a pretty important property.

I've compared various implementations (the BSDs, macOS, Linux and Solaris) and it miraculously looks like all of them use the same scheme for translating the 48-bits LCG state to the return value. The implementations differ here and there, but they effectively do this:

drand48() and erand48(): ldexp(lcgstate, -48)
jrand48() and mrand48(): (int32_t)(lcgstate >> 16)
lrand48() and nrand48(): lcgstate >> 17
Desired Action Replace this sentence:

"Then the appropriate number of bits, according to the type of data item to be returned, are copied from the high-order (leftmost) bits of Xi and transformed into the returned value."

with:

"Xi is then converted to the return value as follows.

- For drand48() and erand48(): 2^-48 * Xi
- For jrand48() and mrand48(): floor(2^-16 * Xi), followed by a conversion to int32_t
- For lrand48() and nrand48(): floor(2^-17 * Xi)"

At the same time I'd suggest that we add an example to this article that contains some test vectors, so that it becomes easier for people to write compliant implementations. Attached to this bug report you'll find a source file.
Tags tc3-2008
Attached Files c file icon rand48-test-vectors.c [^] (2,409 bytes) 2016-12-08 15:09

- Relationships

-  Notes
(0004040)
geoffclare (manager)
2018-05-24 16:05
edited on: 2018-05-24 16:11

Replace this sentence on P749, L25537-25539:
Then the appropriate number of bits, according to the type of data item to be returned, are copied from the high-order (leftmost) bits of X<sub>i</sub> and transformed into the returned value.
with:
X<sub>i</sub> is then converted to the return value as follows:

- For drand48() and erand48() the value shall be 2<sup>-48</sup> times X<sub>i</sub>.
- For jrand48() and mrand48() the value shall be the largest integer not greater than 2<sup>-16</sup> times X<sub>i</sub>.
- For lrand48() and nrand48() the value shall be the largest integer not greater than 2<sup>-17</sup> times X<sub>i</sub>.

Change the EXAMPLES section on P750, L25571 from:
None.
to:
The following program tests that the required pseudo-random number generator is used by these functions.

and then add the contents of the file rand48-test-vectors.c attached to this bug, but with main() changed to main(void).


- Issue History
Date Modified Username Field Change
2016-12-08 15:09 EdSchouten New Issue
2016-12-08 15:09 EdSchouten Status New => Under Review
2016-12-08 15:09 EdSchouten Assigned To => ajosey
2016-12-08 15:09 EdSchouten File Added: rand48-test-vectors.c
2016-12-08 15:09 EdSchouten Name => Ed Schouten
2016-12-08 15:09 EdSchouten Organization => Nuxi
2016-12-08 15:09 EdSchouten Section => *rand48()
2016-12-08 15:09 EdSchouten Page Number => -
2016-12-08 15:09 EdSchouten Line Number => -
2016-12-08 15:24 geoffclare Project 1003.1(2008)/Issue 7 => 1003.1(2016/18)/Issue7+TC2
2018-05-24 16:05 geoffclare Note Added: 0004040
2018-05-24 16:09 geoffclare Interp Status => ---
2018-05-24 16:09 geoffclare Final Accepted Text => Note: 0004040
2018-05-24 16:09 geoffclare Status Under Review => Resolved
2018-05-24 16:09 geoffclare Resolution Open => Accepted As Marked
2018-05-24 16:11 geoffclare Note Edited: 0004040
2018-05-24 16:12 geoffclare Tag Attached: tc3-2008
2019-10-30 10:28 geoffclare Status Resolved => Applied


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