RFC [Discussion]: Randomizer Additions

Hi

For completeness, it would be good to have nextBool() as well.

I'm just wondering if that's really necessary. Generating a boolean is
trivial with the nextFloat method (see example 1. Simulate a coinflip
from the RFC).

No, IMO. Mathematically it doesn't really make sense and talking about
floats, it will also be a very corner case not reached in tests that
might happen in production rarely and break things.

Why does it not make mathematical sense? With the nextFloat method, I
can understand the argument, because that is otherwise opaque,
especially when you work with probabilities. With the getFloat method,
however, I can imagine a few cases in which this makes sense. In our
example, for example, we calculate a random longitude and latitude with
the method. However, the value of Lat: +90.0 Lng: +180.0 cannot be
generated, although it is a valid value. However, the value of Lat:
-90.0 Lng: -180.0 is included. Am I missing something, or is there
currently no simple mathematical way to implement this with an
open-right interval?

I am having another small issue.
As the Randomizer class is final, I guess this will not be perfectly
polyfillable in userland.
So... , if accepted, would it be completely wrong to have these new
methods in PHP 8.2? What can it break?

I am relatively new and have little to no experience with contributing
PHP functions, but I don't think this should be done. There is a good
reason why this is not done and it only causes confusion if any
functions are introduced after the feature freeze. In the end, however,
I think it is the release manager who decides.

Cheers

Joshua Rüsweg

2022年10月14日(金) 13:33 Alexandru Pătrănescu drealecs@gmail.com:

On Thu, Oct 13, 2022, 22:37 Joshua Rüsweg via internals <
internals@lists.php.net> wrote:

Hi

Tim Düsterhus and I have created an RFC to add new methods that solve
commonly encountered use cases to \Random\Randomizer. Specifically
creating a random string consisting of specific bytes and generating
random floating point values.

You can find the RFC at:

https://wiki.php.net/rfc/randomizer_additions

Proof of concept implementation is in:

• https://github.com/php/php-src/pull/9664
• https://github.com/php/php-src/pull/9679

Some open questions to start the discussion:

• Are you missing other commonly useful operations that are also useful
  to have in core?

For completeness, it would be good to have nextBool() as well.

• Do you agree with the method names? Within the PR we received comments

that "alphabet" might not be an appropriate term.

Yes, alphabet is fine by me but I can suggest also: character set,
character list, character dictionary, byte set, byte list, byte dictionary
or some shortcuts of it, like charset.

• Shall an option be added to getFloat() that changes the logic to

select from [$min, $max] (i.e. allowing the maximum to be returned)? And
how should that look like? Boolean parameter? Enum?

No, IMO. Mathematically it doesn't really make sense and talking about
floats, it will also be a very corner case not reached in tests that might
happen in production rarely and break things.

---

We're looking forward to your feedback.

Cheers

Joshua Rüsweg

--

To unsubscribe, visit: https://www.php.net/unsub.php

I am having another small issue.
As the Randomizer class is final, I guess this will not be perfectly
polyfillable in userland.
So... , if accepted, would it be completely wrong to have these new methods
in PHP 8.2? What can it break?

As the Randomizer class is final, I guess this will not be perfectly
polyfillable in userland.

What case do you envision for this? Probably, most cases can be polyfilled
by code: https://3v4l.org/JludD

And it seems that someone has already done such an implementation (which is
very nice and I would like to express my utmost appreciation).

https://github.com/arokettu/php-random-polyfill

Regards
Go Kudo

Hi

Shall an option be added to getFloat() that changes the logic to
select from [$min, $max] (i.e. allowing the maximum to be returned)? And
how should that look like? Boolean parameter? Enum?

An enum would probably be nice, and possibly be for all four cases of
min_(inclusive|exclusive)max(inclusive|exclusive) unless there is a
technical reason to not include all of them.

No technical reason. The paper for the γ-section algorithm by Prof.
Goualard includes implementations for all four combinations.

The [closed, open) and [closed, closed] variants together are the most
useful combination, though. The former can be cleanly split into
subintervals, whereas the latter is symmetric which is useful if your
use case is as well.

With rejection sampling the [closed, closed] variant can also be turned
into any of the other three without introducing any bias.

Generating a random string containing specific characters...thus requires multiple lines of code for what effectively is a very simple operation.

Yeah, though those lines of code add distinction and emphasis for is
meant by character.

In particular, users might be surprised when they give this string
"abc😋👨‍👩‍👦"* and get a non-ascii result.

That's why the method includes 'bytes' in its name. This term is also
used in ->shuffleBytes() which was renamed in
https://wiki.php.net/rfc/random_extension_improvement due to this exact
problem.

In fact ->shuffleBytes() can be considered the companion method to the
proposed ->getBytesFromAlphabet():

->shuffleBytes() allows to simulate a Multivariate hypergeometric
distribution ("sampling without replacement") by shuffling the input
string and then using 'substr' on the result to select a number of bytes
'n'.

->getBytesFromAlphabet() directly maps to a Multinomial distribution
("replacement sampling").

You're going to need to be really precise on the naming and I'm not at
all sure there is a single version that would be useful enough to
belong in core.

Personally I believe the proposed ->getBytesFromAlphabet() to be useful
enough to belong in core. There are quite a few use cases that are
naturally restricted to ASCII: Basically everything that can be
considered an identifier.

Arbitrary numeric strings alone likely provide plenty of use cases:

• Backup codes for multi-factor authentication (restricting the input to
  digits allows you to leverage a numeric keyboard, reducing the chance
  for input errors).
• Random phone numbers for testing purposes.
• Random credit card numbers (you just need to calculate the checksum
  yourself).

While hexadecimal strings can easily be generated by applying bin2hex to
the output of ->getBytes(), that is also unintuitive, because the result
length is twice the number of bytes.

whereas a 64 Bit engine could generate randomness for 8 characters at once.

I'm really not sure that many programs are going to be speed limited
by random number generation.

The syscall cost to retrieve bytes from the 'Secure' engine (which is
the default engine) can be expensive. Especially on older operating
system versions and depending on how many more Meltdown/Spectre-style
vulnerabilities they find.

A userland implementation that generates 1000 random numeric strings
with 100 characters each using the 'Secure' engine requires 146ms on my
computer. The native implementation without optimization requires 101ms
and the optimized native implementation 26ms.

For Xoshiro256** (the fastest engine) the numbers are 89ms, 7ms and 3ms
respectively.

Benchmark attached.

For those that are, writing their own generator to consume all 64 bits
of randomness for each call sounds reasonably sensible, unless a
useful general api can be thought of.

This cannot be reasonably done in userland, because you pay an increased
cost to turn the bytes into numbers and then to perform the necessary
bit fiddling to debias the numbers.

For the float side of the RFC, as there are technical limitations on
which platforms it would be usable on, there needs to be a way of
determining whether the nextFloat and getFloat methods are going to
work. The way this is done on Imagick is to put appropriate defines in
the stub file and in the C code implementations so that the methods
aren't available on the class for the platforms where it isn't going
to function correctly.

I made a PR for that to Tim's repo, though I don't know of an
environment where it can be tested.

I've seent he PR and we shortly discussed this in chat. I would defer
this to the code review, because this amounts to an implementation
detail. Especially since all reasonable server platforms use IEEE 754.

Best regards
Tim Düsterhus

On Fri, Oct 28, 2022 at 12:23 PM Joshua Rüsweg via internals <
internals@lists.php.net> wrote:

Hi

You can find the RFC at:

https://wiki.php.net/rfc/randomizer_additions

Tim Düsterhus and I have updated the RFC and have broadly adopted the
proposals.

Firstly we have renamed the getBytesFromAlphabet to
getBytesFromString as Larry Garfield suggested.

Secondly, we have extended the getFloat method with a parameter that
specifies which type of interval should be generated (Open, Closed,
Right Half-Open and Left Half-Open).

Are you happy with the enum names? Have you any other suggestions?

I had a discussion with Tim about this naming topic as well, and want to
convey my suggestion along with the reasoning.

I think the enum should be Random\IntervalBoundary with the enum cases:

IntervalBoundary::Open
IntervalBoundary::Closed
IntervalBoundary::OpenRight or IntervalBoundary::HalfOpenRight
IntervalBoundary::OpenLeft or IntervalBoundary::HalfOpenLeft

First, I think the enum should be IntervalBoundary because an enum is
used to explicitly represent a program state in a human readable format.
Because of this, I think that the readability for enums should be the
highest priority, even above brevity. Additionally, it should describe the
thing that has the properties, in this case the interval itself. These
interval settings are not a property of floats, it's just that interval
boundary types don't usually matter outside of floats.

The enum should be in the Random\ namespace, because we are only
guaranteeing that this is a complete list of interval boundary properties
in the domain of random numbers. It should not be in the
Random\Randomizer namespace, even though that's the only place it would
be used, because these properties of an interval boundary would be shared
by anything that has interval properties in the domain of random numbers.
Enums don't describe a hierarchy, like interfaces do, so it doesn't make
sense to me to do it the same way the engines are done, for example.

I think OpenRight and OpenLeft are clear enough, since it clearly
describes something that is only half open, but I wouldn't argue strongly
against HalfOpenRight and HalfOpenLeft if someone else felt strongly
about it.

Anyway, that's my notes. :)

Jordan

2022年11月6日(日) 0:34 Go Kudo zeriyoshi@gmail.com:

2022年10月14日(金) 4:38 Joshua Rüsweg via internals internals@lists.php.net:

Hi

Tim Düsterhus and I have created an RFC to add new methods that solve
commonly encountered use cases to \Random\Randomizer. Specifically
creating a random string consisting of specific bytes and generating
random floating point values.

You can find the RFC at:

https://wiki.php.net/rfc/randomizer_additions

Proof of concept implementation is in:

• https://github.com/php/php-src/pull/9664
• https://github.com/php/php-src/pull/9679

---

Some open questions to start the discussion:

• Are you missing other commonly useful operations that are also useful
  to have in core?
• Do you agree with the method names? Within the PR we received comments
  that "alphabet" might not be an appropriate term.
• Shall an option be added to getFloat() that changes the logic to
  select from [$min, $max] (i.e. allowing the maximum to be returned)? And
  how should that look like? Boolean parameter? Enum?

---

We're looking forward to your feedback.

Cheers

Joshua Rüsweg

--

To unsubscribe, visit: https://www.php.net/unsub.php

(I made a mistake in replying to your message, so I will reply again here.)

Hi

I have read the RFC. I think the content is generally good and adequately
compensates for the areas that could not be completed.

I am skeptical only about getFloat(). The use cases are limited and seem
somewhat excessive. Do you have examples of how this is supported in other
languages?

Regards
Go Kudo

Sorry, I did not read the updated RFC. The latitude and longitude samples
were very clear and even my limited understanding of floating point numbers
helped me understand why they were necessary.

I am so far in favor of this RFC and positive about both features. I also
agree that as a member of the maintainer I will maintain it properly.

Thank you for your very coherent writing and implementation.

Best Regards
Go Kudo

Hi

I am skeptical only about getFloat(). The use cases are limited and seem
somewhat excessive. Do you have examples of how this is supported in other
languages?

Yes, unfortunately getFloat() became pretty complex, but that is because
"generating random floats correctly" is pretty complicated, due to how
floats work.

The getFloat() method as proposed implements the γ-section algorithm as
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

This publication is just 7 months old and explains how the
implementation in every other programming language is broken in one way
or another and proposes the γ-section algorithm as a not-broken algorithm.

As floats are not uniformly dense and do not allow representing all
values, it is very easy to introduce a bias or generate incorrect values.

An example taken from the publication:

php > $r = new Random\Randomizer();

We generate a random float in [0, 1) (allowing 0, but not 1), by
dividing a random int between 2^53 - 1 by 2^53. This is effectively what
->nextFloat() does. This creates a uniformly distributed float with as
many different values as possible, because a double (the underlying
representation) has 53 bits of precision.

The nextFloat() method is often the only thing that is available in
other languages, e.g. JavaScript with Math.random() [1]

php > $f = $r->getInt(0, (253 - 1)) / (253);
php > var_dump($f);
float(0.6942225382038698)

Now we want to turn this into a random float between [3.5, 4.5) (not
allowing 4.5), because that's what we need. It's also the formula given
in MDN for JavaScript's Math.random():

php > $min = 3.5;
php > $max = 4.5;
php > var_dump($min + ($max - $min) * $f);
float(4.19422253820387)

The simple formula appears to do the correct thing and it would be
correct if floats could represent all value values. But what happens if
the random integer is 2^53 - 1 (i.e. the maximum integer we allowed to
generate)?

php > $f = (253 - 1) / (253);
php > var_dump($f);
float(0.9999999999999999)
php > var_dump($min + ($max - $min) * $f);
float(4.5)

In this case the result was rounded to 4.5, because the exact result was
not representable. Now an invalid value was generated!

Likewise if you generate a random float between 0 and 1000 with this
method, some values will appear more often than others due to rounding
and the changing density of floats for each power of two.

With the γ-section algorithm by Prof. Goualard all these issues are
eliminated and that's what is used for getFloat(). The getFloat() method
supports all 4 possible boundary combinations to ensure that users have
a safe solution for all possible use cases, so that they don't need to
build an unsafe solution in userland.

Best regards
Tim Düsterhus

[1]
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/random