[jira] [Comment Edited] (RNG-79) Benchmark methods for producing nextDouble

["Alex D Herbert (JIRA)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/RNG-79?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16783327#comment-16783327 ] 

Alex D Herbert edited comment on RNG-79 at 3/5/19 10:45 AM:
------------------------------------------------------------

{quote}Does it mean that the implementation is different in {{java.util.Random}}?
{quote}
In my version of Open JDK 1.8 {{java.util.Random}} is using 53 bits for creating the double.
{code:java}
return (((long)(next(26)) << 27) + next(27)) * 0x1.0p-53; // 1.0 / (1L << 53)
{code}
The javadoc states:
{noformat}
[In early versions of Java, the result was incorrectly calculated as:

 return (((long)next(27) << 27) + next(27))
     / (double)(1L << 54);
This might seem to be equivalent, if not better, but in fact it introduced
a large nonuniformity because of the bias in the rounding of floating-point 
numbers: it was three times as likely that the low-order bit of the 
significand would be 0 than that it would be 1! This nonuniformity 
probably doesn't matter much in practice, but we strive for perfection.]
{noformat}
So they actually used to use 54 bits to create the double but have corrected.

I'll add the benchmark which I expect may not be able to measure a difference. If so then we can create a Jira ticket to change it.

The interesting thing is the current use of 52-bits to create the double from two int values using 26 bits from each. A change to using 53 bits would then require 27 bits from one and 26 from the other which is uneven. But if the int provider is truly random above 27-bits of state then this will not matter. The change should be made ensuring the extra bit is the least significant bit in the output long which is converted to a double. This should minimise the effect of a non-random 27-th bit rather then have it halfway along the 53-bit long. This is what the version above is doing: 26-bits of state prepended to 27-bits of state.


was (Author: alexherbert):
{quote}Does it mean that the implementation is different in {{java.util.Random}}?
{quote}
In my version of Open JDK 1.8 {{java.util.Random}} is using 53 bits for create the double.
{code:java}
return (((long)(next(26)) << 27) + next(27)) * 0x1.0p-53; // 1.0 / (1L << 53)
{code}
The javadoc states:
{noformat}
[In early versions of Java, the result was incorrectly calculated as:

 return (((long)next(27) << 27) + next(27))
     / (double)(1L << 54);
This might seem to be equivalent, if not better, but in fact it introduced a large nonuniformity because of the bias in the rounding of floating-point numbers: it was three times as likely that the low-order bit of the significand would be 0 than that it would be 1! This nonuniformity probably doesn't matter much in practice, but we strive for perfection.]
{noformat}
So they actually used to use 54 bits to create the double but have corrected.

I'll add the benchmark which I expect may not be able to measure a difference. If so then we can create a Jira ticket to change it.

The interesting thing is the current use of 52-bits to create the double from two int values using 26 bits from each. A change to using 53 bits would then require 27 bits from one and 26 from the other which is uneven. But if the int provider is truly random above 27-bits of state then this will not matter. The change should be made ensuring the extra bit is the least significant bit in the output long which is converted to a double. This should minimise the effect of a non-random 27-th bit rather then have it halfway along the 53-bit long. This is what the version above is doing: 26-bits of state prepended to 27-bits of state.

> Benchmark methods for producing nextDouble
> ------------------------------------------
>
>                 Key: RNG-79
>                 URL: https://issues.apache.org/jira/browse/RNG-79
>             Project: Commons RNG
>          Issue Type: New Feature
>          Components: core
>    Affects Versions: 1.3
>            Reporter: Alex D Herbert
>            Assignee: Alex D Herbert
>            Priority: Minor
>          Time Spent: 40m
>  Remaining Estimate: 0h
>
> Benchmark the speed of methods for producing a {{double}} from a {{long}}:
> {code:java}
> long v;
> double d1 = Double.longBitsToDouble(0x3FFL << 52 | v >>> 12) - 1.0;
> double d2 = (v >>> 12) * 0x1.0p-52d; // 1.0 / (1L << 52);
> double d3 = (v >>> 11) * 0x1.0p-53d; // 1.0 / (1L << 53);
> {code}
> Method d1 and d2 are both currently employed in the {{NumberFactory}} (makeDouble(int,int) and makeDouble(long)). However they suffer from producing a double whose least significant bit is always 0, i.e. they produce half of all possible double values from 0-1. This is discussed in the reference for the [XorShiRo generators|http://xoshiro.di.unimi.it/].
> This task will benchmark the methods using JMH. A switch to method d3 may be appropriate as it generates more values. This is the method employed in JDK 1.7 ThreadLocalRandom.
> A similar analysis can be made for producing a float:
> {code:java}
> int v;
> double f1 = Float.intBitsToFloat(0x7f << 23 | v >>> 9) - 1.0f;
> double f2 = (v >>> 9) * 0x1.0p-23f; // 1.0f / (1 << 23);
> double f3 = (v >>> 8) * 0x1.0p-24f; // 1.0f / (1 << 24)
> {code}
> Method f2 is currently used in the {{NumberFactory}}.



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)