Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8302987

Add uniform and spatially equidistributed bounded double streams to RandomGenerator

    XMLWordPrintable

Details

    • Enhancement
    • Resolution: Fixed
    • P4
    • 22
    • None
    • core-libs
    • None
    • b07
    • generic
    • generic

    Description

      The method nextDouble(double origin, double bound) in RandomGenerator aims to generate a uniform and spatially equidistributed random double in the left-closed and right-open range [origin, bound). It does so by applying the affine transform origin + (bound - origin) * r to a uniform and spatially equidistributed random double r in the range [0, 1).

      While this is sound using unbounded precision arithmetic, it is less so with floating-point arithmetic. It is well-known that floating-point arithmetic suffers from small but noticeable rounding errors. This ends up deforming the distribution of r when applying the affine transform. The obtained distribution is not necessarily uniform nor equidistributed, even if the distribution in [0, 1) is.

      As shown by Goualard [1], this becomes quite visible and leads to problems in applications where the expectations for a uniform and spatial equidistribution is crucial.

      Moreover, there are only 2^53 equidistributed doubles in the range [0, 1). However, as an example, there are 2^54 equidistributed doubles in the range [-1, 1). Thus, even if arithmetic were performed exactly, it would still be impossible to map the 2^53 equidistributed doubles in [0, 1) to the 2^54 in [-1, 1).

      Following Goualard analysis and suggestions, it is proposed to add methods returning streams of doubles that behave better in this regard. It avoids any rounding errors altogether, mostly relying instead on long arithmetic and generating a double by just a single exact multiplication. Moreover, all 4 combinations of closed/open range boundaries are supported.

      In order to absorb unavoidable setup costs to ensure these properties, only methods returning streams are proposed, as opposed to methods returning individual random doubles. Once the stream is set up, generating the next double reduces to a few arithmetic instructions, in addition to the generation of a random long.

      ----

      [1] Goualard, "Drawing random floating-point numbers from an interval", ACM Transactions on Modeling and Computer Simulation, 2022, 32 (3) (https://hal.science/hal-03282794v4)

      Attachments

        Issue Links

          Activity

            People

              rgiulietti Raffaello Giulietti
              rgiulietti Raffaello Giulietti
              Votes:
              0 Vote for this issue
              Watchers:
              3 Start watching this issue

              Dates

                Created:
                Updated:
                Resolved: