aboutsummaryrefslogtreecommitdiffstats
path: root/util/random/lcg_engine.cpp
diff options
context:
space:
mode:
authorEvgeny Grechnikov <diamondaz@yandex.ru>2022-02-10 16:46:20 +0300
committerDaniil Cherednik <dcherednik@yandex-team.ru>2022-02-10 16:46:20 +0300
commit6e38f52f898d7c077ddd319800b4014967a5ca76 (patch)
treef0b2473cfc98506158b8f1d3d387c4f478ade18e /util/random/lcg_engine.cpp
parentbd085aee9b4f7a0bee302ce687964ffb7098f986 (diff)
downloadydb-6e38f52f898d7c077ddd319800b4014967a5ca76.tar.gz
Restoring authorship annotation for Evgeny Grechnikov <diamondaz@yandex.ru>. Commit 1 of 2.
Diffstat (limited to 'util/random/lcg_engine.cpp')
-rw-r--r--util/random/lcg_engine.cpp50
1 files changed, 25 insertions, 25 deletions
diff --git a/util/random/lcg_engine.cpp b/util/random/lcg_engine.cpp
index e1469104fa..e875705bcf 100644
--- a/util/random/lcg_engine.cpp
+++ b/util/random/lcg_engine.cpp
@@ -1,30 +1,30 @@
#include "lcg_engine.h"
-
-namespace NPrivate {
- template <typename T>
+
+namespace NPrivate {
+ template <typename T>
T LcgAdvance(T seed, T lcgBase, T lcgAddend, T delta) noexcept {
- // seed[n+1] = A * seed[n] + B, A = lcgBase, B = lcgAddend
- // seed[n] = A**n * seed[0] + (A**n - 1) / (A - 1) * B
- // (initial value of n) = m * 2**k + (lower bits of n)
- T mask = 1;
- while (mask != (1ULL << (8 * sizeof(T) - 1)) && (mask << 1) <= delta) {
- mask <<= 1;
- }
- T apow = 1; // A**m
- T adiv = 0; // (A**m-1)/(A-1)
- for (; mask; mask >>= 1) {
- // m *= 2
- adiv *= apow + 1;
- apow *= apow;
- if (delta & mask) {
- // m++
- adiv += apow;
- apow *= lcgBase;
- }
- }
- return seed * apow + lcgAddend * adiv;
- }
-
+ // seed[n+1] = A * seed[n] + B, A = lcgBase, B = lcgAddend
+ // seed[n] = A**n * seed[0] + (A**n - 1) / (A - 1) * B
+ // (initial value of n) = m * 2**k + (lower bits of n)
+ T mask = 1;
+ while (mask != (1ULL << (8 * sizeof(T) - 1)) && (mask << 1) <= delta) {
+ mask <<= 1;
+ }
+ T apow = 1; // A**m
+ T adiv = 0; // (A**m-1)/(A-1)
+ for (; mask; mask >>= 1) {
+ // m *= 2
+ adiv *= apow + 1;
+ apow *= apow;
+ if (delta & mask) {
+ // m++
+ adiv += apow;
+ apow *= lcgBase;
+ }
+ }
+ return seed * apow + lcgAddend * adiv;
+ }
+
template ui32 LcgAdvance<ui32>(ui32, ui32, ui32, ui32) noexcept;
template ui64 LcgAdvance<ui64>(ui64, ui64, ui64, ui64) noexcept;
}