[jira] [Commented] (RNG-128) UnitBallSampler

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

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

Alex Herbert commented on RNG-128:
----------------------------------

I have constructed a JMH benchmark for sampling with an n-ball of dimension 1 to 5.

Dimension 1 methods to generate a double in the approximate range [-1, 1]:
{code:java}
// Baseline
rng.nextDouble()

// signedDouble:
// Sample uniformly from 2^54 dyadic rationals in [-1, 1).
// Equivalent to nextDouble() then subtracting 0 or 1 using an unused bit.
long bits = rng.nextLong();
((bits >>> 11) * 0x1.0p-53d) - ((bits >>> 10) & 0x1L);

// twoDoubles:
// Sample [-1, 1) excluding -0.0 but also missing the final 1.0 - 2^-53.
rng.nextDouble() + rng.nextDouble() - 1.0

// booleanDouble: 
// This will sample (-1, 1) including -0.0 and 0.0
rng.nextBoolean() ? -rng.nextDouble() : rng.nextDouble()
{code}
Dimension 2:
||Method||Description||
|Baseline|An array of rng.nextDouble()|
|Rejection|Sample in a 2D square of length 2 and reject x^2 + y^2 >= 1.0.
 This will reject approximately 
 2^2 / pi = 1.27 square positions per sample|
|DiskPoint|Use the [disk point picking|https://mathworld.wolfram.com/DiskPointPicking.html] method described in Wolfram|

Dimension 3-5:
||Method||Description||
|Baseline|An array of rng.nextDouble()|
|Rejection|Sample in a ND hypercube of length 2 and reject x^2 + y^2 + ... >= 1.0.
 This will reject approximately 2^3 / (4pi/3) = 1.91 cube positions per sample for 3D and more as dimensions increase|
|BallPoint|Use the [ball point picking|https://mathworld.wolfram.com/BallPointPicking.html] method described in Wolfram|

For dimension 3 I have included dedicated samplers that computes xyz without using arrays to view the performance gain.

The results are as follows using a XO_RO_SHI_RO_128_PP random source:
|Method|dimension|size|type|Score|Relative|
|create1D| |1|Baseline|8.854|1.00|
|create1D| |1|signedDouble|8.85|1.00|
|create1D| |1|twoDoubles|9.876|1.12|
|create1D| |1|booleanDouble|14.392|1.63|
|create1D| |100|Baseline|762.456|1.00|
|create1D| |100|signedDouble|774.765|1.02|
|create1D| |100|twoDoubles|881.637|1.16|
|create1D| |100|booleanDouble|1503.541|1.97|
|create2D| |1|Baseline|9.876|1.00|
|create2D| |1|Rejection|19.167|1.94|
|create2D| |1|DiskPoint|47.243|4.78|
|create2D| |100|Baseline|869.734|1.00|
|create2D| |100|Rejection|1833.306|2.11|
|create2D| |100|DiskPoint|4753.457|5.47|
|create3D| |1|Baseline|13.585|1.00|
|create3D| |1|Rejection|41.447|3.05|
|create3D| |1|BallPoint|52.409|3.86|
|create3D| |100|Baseline|1158.785|1.00|
|create3D| |100|Rejection|3994.783|3.45|
|create3D| |100|BallPoint|4900.946|4.23|
|createND|3|1|Baseline|17.307|1.00|
|createND|3|1|Rejection|45.327|2.62|
|createND|3|1|BallPoint|60.219|3.48|
|createND|3|100|Baseline|1569.775|1.00|
|createND|3|100|Rejection|4258.297|2.71|
|createND|3|100|BallPoint|5849.117|3.73|
|createND|4|1|Baseline|18.908|1.00|
|createND|4|1|Rejection|83.398|4.41|
|createND|4|1|BallPoint|64.528|3.41|
|createND|4|100|Baseline|1873.559|1.00|
|createND|4|100|Rejection|7979.563|4.26|
|createND|4|100|BallPoint|6585.013|3.51|
|createND|5|1|Baseline|21.459|1.00|
|createND|5|1|Rejection|134.776|6.28|
|createND|5|1|BallPoint|81.294|3.79|
|createND|5|100|Baseline|1986.237|1.00|
|createND|5|100|Rejection|13380.114|6.74|
|createND|5|100|BallPoint|7527.744|3.79|

For 1D the signed double method is almost as fast as the baseline generation of a double in [0, 1).

For 2D the rejection method is 2.6x faster than the disk point picking.

For 3D the dedicated non-array based rejection method is 1.46x faster than the generic 3D ball point picking.

For 4D and 5D the ball point picking is faster than the rejection method.

> UnitBallSampler
> ---------------
>
>                 Key: RNG-128
>                 URL: https://issues.apache.org/jira/browse/RNG-128
>             Project: Commons RNG
>          Issue Type: Improvement
>          Components: sampling
>            Reporter: Alex Herbert
>            Priority: Minor
>
> The *UnitSphereSampler* can generate isotropically distributed coordinates *on the surface* of a hypersphere of a given dimension.
> I propose to create a *UnitBallSampler* to generate isotropically distributed coordinates *within* a hypersphere of a given dimension.
> Wolfram describes a method that will work with any dimension and a method for 2 dimensions:
> [Ball Point Picking|https://mathworld.wolfram.com/BallPointPicking.html]
>  [Disk Point Picking|https://mathworld.wolfram.com/DiskPointPicking.html]
> It also suggests that a simple rejection method when sampling inside an n-cube of length 2 may be faster for small dimensions.
> Creating an abstract class with a factory method would allow the best performing sampler to be created for each dimension:
> {code:java}
> public abstract class UnitBallSampler implements
>         SharedStateSampler<UnitBallSampler> {
>     /**
>      * @return a random Cartesian coordinate within the unit n-ball.
>      */
>     public double[] next() {
>         // ...
>     }
>     /**
>      * Create a unit n-ball sampler for the given dimension.
>      *
>      * @param dimension Space dimension.
>      * @param rng Generator for the individual components of the coordinates. 
>      * A shallow copy will be stored in this instance.
>      * @throws IllegalArgumentException If {@code dimension <= 0}
>      */
>     public static UnitBallSampler of(int dimension,
>                                      UniformRandomProvider rng) {
>         // ...
>     }
> }
> {code}
> The UnitSphereSampler sample method is named {{nextVector}}. The corresponding method here could be:
>  * next
>  * nextVector
>  * nextCoordinate
>  * nextPoint
>  * sample
>  * ...



--
This message was sent by Atlassian Jira
(v8.3.4#803005)