RFC [Discussion]: Randomizer Additions

On Tue, Oct 18, 2022 at 10:22 AM Tim Düsterhus <tim@bastelstu.be> wrote:

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/5d186eac99ceb98b089865099c2d7622428bfdaa/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

On Tue, Oct 18, 2022, at 12:22 PM, Tim Düsterhus wrote:

"Alphabet" here still, to me, implies a character set, not a byte stream. Maybe getBytesFromString? getBytesFromList? getBytesFrom() (because you're getting it "from" the string that's provided, so you don't need another noun there.)? I'm not opposed to the functionality, but "alphabet" doesn't seem like the right word for it. --Larry Garfield

Hi On 10/29/22 00:44, Jordan LeDoux wrote:

Yes, I agree this is a much better name for the enum itself and just adjusted the implementation and RFC.

But for the enum members I prefer the existing naming of (Closed|Open)(Closed|Open), unless someone has a good argument for a different naming scheme: - It's very explicit, which I consider useful for two reasons which are likely related: (a) I don't have to think about what "OpenRight" means for the left boundary. (b) As not-a-native-speaker-of English I find OpenRight or HalfOpenRight not completely obvious and would likely need to look up what exactly OpenRight means, whereas ClosedOpen is understandable more intuitively. Especially since a half-open interval is sometimes referred to as half-open and sometimes as half-closed. The preferred variant might even differ across languages. - It's nicely symmetric from the naming. - It's the naming used by Prof. Goualard in the Drawing Random Floating-Point Numbers from an Interval paper (though in a shortened CC, CO, OC, OO variant). Best regards Tim Düsterhus

On Sat, Nov 5, 2022 at 9:00 AM Tim Düsterhus <tim@bastelstu.be> wrote:

This is a much more subtle problem than many people realize, and I'm sure there are people who will vote or use this feature that don't have a deep understanding of either the float/double type, or of the math behind this, so I'm going to re-explain this using some analogies and examples. **NOTE**: This is mainly for historical record if someone looks back on this internals thread, not in response to any individual in the thread. I'm trying to lay out in language that any passer-by could follow what the issue is and why it is important. Accordingly, I'll be referencing base-10 numbers instead of base-2 numbers through most of this for clarity, but the ideas behind it apply to the base-2 numbers that are actually used, just with different boundaries at powers of 2 instead of powers of 10. Suppose you have a number type that can store exactly 10 digits. Well over the interval [0, 1] you can represent any number between 0.000 000 000 and 1.000 000 000 without issue. In fact, since you can store exactly 10 digits, you can represent any number between 0.000 000 000 and 9.999 999 999. But what happens if you want the interval [0, 10]? Well, at 10 you can only represent the digits 10.000 000 00, since you have to use one of the digits that used to represent the decimal part to represent the whole part, because you have a fixed amount of digits you can use. In order to represent larger numbers, you lose the ability to represent certain numbers that you used to be able to represent. The "density" of numbers has gone down. So if you tell the program "I want a random number, with decimal places, between 0 and 1000", it runs into the following dilemma: between [0, 10), (this means the interval that includes 0 but does not include 10), you have 1 billion values between each whole number which could be chosen. However, for the numbers between [10, 100), you only have 100 million values between each whole number that could be chosen, because you lost a digit after the decimal point. This means that if you do a naive multiplication or selection of your number, the intervals between 0 to 10 are individually 10 times more likely to be chosen than any of the individual intervals between 10 to 100, because those intervals have 10 times as many values mapped to them. The result would actually be nearly equally likely to be in the range [0, 10) as it would [10, 100), (because there are nearly as many possible values between [0, 10) as there are between [10, 100)), even though mathematically the second range is nearly 10 times the size of the first range. Each possible representable value would be equally likely to be chosen, but because the *density* of values is different at different parts of the range, this actually skews the probability of a number landing within an arbitrary part of the range of outputs. This means that if your code does something like `if ($rand->getFloat(0, 1000) < 500)`, you're NOT actually going to get a 50% chance of `true` and a 50% chance of `false`. In fact, using the naive way of mapping floats that Tim mentioned (with base-10 math instead of base-2), you'd get `true` *over two thirds of the time*. Accounting for this is not very easy. What proportion of your total result set has an expanded representable value? In my example, that might be easy to calculate, but the actual math for a program like this is done in base-2, not base-10. To actually calculate this, you need all sorts of logs you need to take to figure out how many powers of 2 you're spanning, and how that affects the probability of different intervals. It is *extremely* easy to get this math wrong, even if you know what you're doing. As Tim said, virtually no implementations that exist *actually* do this correctly. Also consider that the requested range may not nicely straddle a power of 2. What if you want a float for the interval [5, 10]? Neither 5 nor 10 sit cleanly on a power of 2, so how does that affect your math? Like cryptography and security, this is an area where very specific and very confident expertise is necessary, and it is highly preferable to have everyone use a single vetted solution than roll their own. This makes it very poor as something to leave to userland, and makes it *highly* desirable to include it in core. It's very difficult to do, but there is also only one actually correct result, which makes it perfect for inclusion in core. Jordan