Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:118844
MIME-Version: 1.0
References: <5ceebae4-a3fb-5d29-cdb7-dceed7b07c78@wcflabs.de>
 <CA+kxMuQECpLyt_D63jzBB1T4K57eVCCHD7JToA==bbHojkhb9w@mail.gmail.com> <a0ee88b7-8fc6-ad67-4aec-811beebdc58a@bastelstu.be>
In-Reply-To: <a0ee88b7-8fc6-ad67-4aec-811beebdc58a@bastelstu.be>
Date: Tue, 18 Oct 2022 11:14:05 -0700
Message-ID: <CAMrTa2Exu4kE1KejC4zDU1+tKJd2YP1akmzfZL0mJroa=W2WOg@mail.gmail.com>
To: =?UTF-8?Q?Tim_D=C3=BCsterhus?= <tim@bastelstu.be>
Cc: Dan Ackroyd <Danack@basereality.com>, =?UTF-8?Q?Joshua_R=C3=BCsweg?= <josh@wcflabs.de>, 
	internals@lists.php.net
Content-Type: multipart/alternative; boundary="00000000000074a93b05eb530f1f"
Subject: Re: [PHP-DEV] RFC [Discussion]: Randomizer Additions
From: jordan.ledoux@gmail.com (Jordan LeDoux)

--00000000000074a93b05eb530f1f
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

On Tue, Oct 18, 2022 at 10:22 AM Tim D=C3=BCsterhus <tim@bastelstu.be> wrot=
e:

>
> 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.
>

To add to this, I'm going to link to a userland implementation I wrote for
my Fermat library. A couple of notes:

1. I am not at all claiming to be a subject matter expert, and this was my
first pass at the feature, not a fully researched and optimized version.
2. The main issue at hand for me was that my 'numbers' could be arbitrary
precision, which would require me to directly ask for bytes and then pull
out numbers from them depending on the number of integer digits possible
within the range.

https://github.com/JordanRL/Fermat/blob/5d186eac99ceb98b089865099c2d7622428=
bfdaa/src/Samsara/Fermat/Provider/RandomProvider.php#L128

Now again, this was my first pass, but the way I tackled this was to get a
string of bytes that fully contained the integer range. The issue of
debiasing the numbers with that approach is *so* difficult, that I opted
instead to simply recursively call the operation until a number within the
desired range was generated. This avoids introducing bias, but is obviously
less than optimal. Some kind of ability to directly provide a set of
possible characters and generating from bytes directly would at least
reduce the recursion space further in my case, though my particular
algorithm still needs additional improvement obviously.

Generating random numbers that have an arbitrary range is not easy,
particularly if your range might exceed PHP_INT_MAX. *Any* utilities that
core can provide to improve performance and reduce the number of places
that bias might be introduced in such a situation would be much
appreciated. Personally, I decided for my implementation that introducing
bias was a greater concern than performance.

Jordan

--00000000000074a93b05eb530f1f--