The reference implementation of the "Drawing Random Floating-Point Numbers from
an Interval" paper contains two mistakes that will result in erroneous values
being returned under certain circumstances:
- For large values of `g` the multiplication of `k * g` might overflow to
infinity.
- The value of `ceilint()` might exceed 2^53, possibly leading to a rounding
error when promoting `k` to double within the multiplication of `k * g`.
This commit updates the implementation based on Prof. Goualard suggestions
after reaching out to him. It will correctly handle inputs larger than 2^-1020
in absolute values. This limitation will be documented and those inputs
possibly be rejected in a follow-up commit depending on performance concerns.
* random: Add `max_offset` local to Randomizer::getBytesFromString()
* random: Use branchless implementation for mask generation in Randomizer::getBytesFromString()
This was benchmarked against clzl with a standalone script with random inputs
and is slightly faster. clzl requires an additional branch to handle the
source_length = 1 / max_offset = 0 case.
* Improve comment for masking in Randomizer::getBytesFromString()
With a single byte we can choose offsets between 0x00 and 0xff, thus 0x100
different offsets. We only need to use the slow path for sources of more than
0x100 bytes.
The previous version was correct with regard to the output expectations, it was
just slower than necessary. Better fix this now while we still can before being
bound by our BC guarantees with regard to emitted sequences.
This also adds a test to verify the behavior: For powers of two we never reject
any values during rejection sampling, we just need to mask off the unneeded
bits. Thus we can specifically verify that the number of calls to the engine
match the expected amount. We also verify that all the possible values are
emitted to make sure the masking does not remove any required bits. For inputs
longer than 0x100 bytes we need trust the `range()` implementation to be
unbiased, but still verify the number of engine calls and perform a basic
output check.
* random: Randomizer::getFloat(): Fix check for empty open intervals
The check for invalid parameters for the IntervalBoundary::OpenOpen variant was
not correct: If two consecutive doubles are passed as parameters, the resulting
interval is empty, resulting in an uint64 underflow in the γ-section
implementation.
Instead of checking whether `$min < $max`, we must check that there is at least
one more double between `$min` and `$max`, i.e. it must hold that:
nextafter($min, $max) != $max
Instead of duplicating the comparatively complicated and expensive `nextafter`
logic for a rare error case we instead return `NAN` from the γ-section
implementation when the parameters result in an empty interval and thus underflow.
This allows us to reliably detect this specific error case *after* the fact,
but without modifying the engine state. It also provides reliable error
reporting for other internal functions that might use the γ-section
implementation.
* random: γ-section: Also check that that min is smaller than max
This extends the empty-interval check in the γ-section implementation with a
check that min is actually the smaller of the two parameters.
* random: Use PHP_FLOAT_EPSILON in getFloat_error.phpt
Co-authored-by: Christoph M. Becker <cmbecker69@gmx.de>
* random: Add Randomizer::nextFloat()
* random: Check that doubles are IEEE-754 in Randomizer::nextFloat()
* random: Add Randomizer::nextFloat() tests
* random: Add Randomizer::getFloat() implementing the y-section algorithm
The algorithm is published in:
Drawing Random Floating-Point Numbers from an Interval. Frédéric
Goualard, ACM Trans. Model. Comput. Simul., 32:3, 2022.
https://doi.org/10.1145/3503512
* random: Implement getFloat_gamma() optimization
see https://github.com/php/php-src/pull/9679/files#r994668327
* random: Add Random\IntervalBoundary
* random: Split the implementation of γ-section into its own file
* random: Add tests for Randomizer::getFloat()
* random: Fix γ-section for 32-bit systems
* random: Replace check for __STDC_IEC_559__ by compile-time check for DBL_MANT_DIG
* random: Drop nextFloat_spacing.phpt
* random: Optimize Randomizer::getFloat() implementation
* random: Reject non-finite parameters in Randomizer::getFloat()
* random: Add NEWS/UPGRADING for Randomizer’s float functionality
* Unify structure for ext/random's engine tests (2)
This makes adjustments that were missed in
2d6a883b3a.
* Add `engines.inc` for ext/random tests
* Unify structure for ext/random's randomizer tests
