delight-im / delight-im/PHP-Random

Consider GMP implementation

Open
#1 0 comments 0 reactions 0 assignees View on GitHub
enhancement
Dominant language
PHP
Stars
21
Forks
3
PR merge metrics
No merged PRs in 30d

Description

Making use of the GMP (GNU Multiple Precision) extension (`gmp`) can potentially speed up the generation of long random strings:

```php
public static function stringFromAlphabet(string $alphabet, int $length): string {
// determine the base of the alphabet
$base = \strlen($alphabet);
// calculate the size of the range that random values are to be returned from, which can then be used as an upper bound (exclusive) with a lower bound (inclusive) of zero
$desiredRangeGmp = \gmp_pow(\gmp_init($base, 10), $length);
// calculate (log_2) the number of bits required (as a minimum) so that every integer in the range can be represented
$bitsNeededGmp = \strlen(\gmp_strval($desiredRangeGmp, 2));
// calculate the number of bytes required
$bytesNeeded = \gmp_intval(\gmp_div_q($bitsNeededGmp, \gmp_init(8, 10), \GMP_ROUND_PLUSINF));
// determine the maximum available range of random integers that the chosen number of bytes will provide
$maximumRangeGmp = \gmp_pow(\gmp_pow(\gmp_init(2, 10), 8), $bytesNeeded);
// extend the desired range to the largest whole multiple of its own that will still be within the maximum available range provided by the bytes, as an optimization so that many more numbers fall into the range that is used and significantly fewer numbers have to be discarded
$extendedRangeGmp = \gmp_sub($maximumRangeGmp, \gmp_mod($maximumRangeGmp, $desiredRangeGmp));
// determine the maximum decimal that falls into the extended range and can thus be accepted
$maxDecimalGmp = \gmp_sub($extendedRangeGmp, \gmp_init(1, 10));

// until bytes in the desired (extended) range have been found, perform rejection sampling and discard any bytes outside the range to achieve a uniform distribution
do {
// generate a sequence of random bytes with the required length
$bytes = \Delight\Random\Random::bytes($bytesNeeded);
} while (\gmp_cmp(\gmp_import($bytes), $maxDecimalGmp) === 1);

// the bytes from the extended range can safely be converted to the target alphabet via a base conversion (without introducing bias)
$str = \Delight\BaseConvert\Alphabet::convert($bytes, \Delight\BaseConvert\Alphabet::BYTE, $alphabet);
// the modulo operation can be applied safely on numbers from the extended range (without introducing bias)
$str = \substr($str, -$length);
// pad the number with zeros at the left
$str = \str_pad($str, $length, $alphabet[0], \STR_PAD_LEFT);

return $str;
}
```

But this doesn’t seem to be faster for many *short* strings. So the question becomes *when* to use this. A draft implementation for deciding this is the following:

```php
private static function shouldUseGmpInsteadOfMultipleRandomInts() {
if (!\extension_loaded('gmp')) {
return false;
}

if (\strncasecmp(\PHP_OS, 'WIN', 3) === 0) {
if (\Delight\Alphabets\Alphabet::isStandardAlphabet($alphabet)) {
return $length >= 8;
}
else {
return $length >= 20;
}
}
else {
if (\Delight\Alphabets\Alphabet::isStandardAlphabet($alphabet)) {
return $length >= 13;
}
else {
return false;
}
}
}
```

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.