Fix two numerical defects in `absl::gaussian_distribution`'s Ziggurat implementation: 1. Disjoint strip/variate bit extraction near x = 0 (`gaussian_distribution.h`): Previously, `zignor()` extracted strip index `i = bits & 0x7f` and passed the same `bits` to `GenerateRealFromBits<double, GenerateSignedTag, false>`. Whenever `|j| < 2^-4` (`clz >= 5`, 6.25% of draws near the mode `x = 0`), the low mantissa bits overlapped `i`, locking small variates to wide strips (`+31.8%` density error on `P(|Z| < 2^-56)` and `-52.4%` on `P(|Z| < 2^-59)`), while `IncludeZero = false` made `0.0` (and `(-2.01e-19, +2.01e-19)`) unreachable even for `gaussian_distribution<float>`. `zignor()` now extracts completely disjoint bitfields from a single `uint64_t`: `bits[0..6]` for strip `i` in `[0, 127]` and `bits[10..63]` as a signed 54-bit integer `s = static_cast<int64_t>(bits) >> 10` scaled by `0x1p-53` to an exact double `j` in `[-1.0, 1.0)`. Compared to a sign-magnitude encoding (`+/-mag * 2^-53`), the signed arithmetic-shift encoding avoids double-weighting `0.0` (exact single-grid weight `2^-54`, never produces `-0.0`), eliminates truncation-toward-zero bias on `E[|j|]` and `E[j^2]`, and compiles to `sar` + `cvtsi2sd` + `mulsd`. At the sole asymmetric endpoint `j = -1.0` (`s = -2^53`), every strip `i > 0` enters the wedge test at `f(x) = f[i]` (rejected up to ~1 ULP libm `exp()` rounding), and `i == 0` routes to the negative tail fallback (net mean shift `~ -1.6e-18`). 2. Full 53-bit IEEE-754 Ziggurat constants and consistent `f[i]` table (`gaussian_distribution.h`, `gaussian_distribution_gentables.cc`, `gaussian_distribution.cc`): Previously, `kR` and `kV` were truncated to 12-15 digits (5,287 and 42,826 ULPs off the exact 128-strip solution), accumulating a `+1.20e-9` area bias on strip `i = 127`, and `tables_.f[i]` stored recurrence `v` rather than `std::exp(-0.5 * x[i] * x[i])` (up to 8 ULPs drift in wedge checks). Updated `kR`, `kRInv`, and `kV` to full 53-bit IEEE-754 precision (`kR = 3.44261985589665212`, `kRInv = 0.29047645161494128`, `kV = 9.91256303533646108e-3`), updated `TableGenerator` to advance the recurrence via running `v` while storing `f(tables_.x[i])`, and regenerated `gaussian_distribution.cc`. All 128 strip areas now match `kV` within `2.68e-14` relative error (`1.61e-14` on strip 127) and `f[i]` matches `std::exp(-0.5 * x[i] * x[i])` to 0 ULPs. Note: This change intentionally alters `absl::gaussian_distribution` output sequences (which are documented as not guaranteed to be stable) due to the disjoint bit extraction and regenerated Ziggurat tables. PiperOrigin-RevId: 1022881797
diff --git a/absl/random/BUILD.bazel b/absl/random/BUILD.bazel index 42b59d3..fa71cea 100644 --- a/absl/random/BUILD.bazel +++ b/absl/random/BUILD.bazel
@@ -384,10 +384,12 @@ deps = [ ":distributions", ":random", + "//absl/base:config", "//absl/base:core_headers", "//absl/log", "//absl/numeric:representation", "//absl/random/internal:distribution_test_util", + "//absl/random/internal:pcg_engine", "//absl/random/internal:sequence_urbg", "//absl/strings", "//absl/strings:str_format",
diff --git a/absl/random/CMakeLists.txt b/absl/random/CMakeLists.txt index b2c3fa2..69053be 100644 --- a/absl/random/CMakeLists.txt +++ b/absl/random/CMakeLists.txt
@@ -441,11 +441,13 @@ LINKOPTS ${ABSL_DEFAULT_LINKOPTS} DEPS + absl::config absl::core_headers absl::log absl::numeric_representation absl::random_distributions absl::random_internal_distribution_test_util + absl::random_internal_pcg_engine absl::random_internal_sequence_urbg absl::random_random absl::str_format
diff --git a/absl/random/gaussian_distribution.cc b/absl/random/gaussian_distribution.cc index 30ad3f0..55c5a4e 100644 --- a/absl/random/gaussian_distribution.cc +++ b/absl/random/gaussian_distribution.cc
@@ -2,6 +2,7 @@ // clang-format off #include "absl/random/gaussian_distribution.h" + #include "absl/base/config.h" namespace absl { @@ -10,92 +11,92 @@ const gaussian_distribution_base::Tables gaussian_distribution_base::zg_ = { - {3.7130862467425505, 3.442619855899000214, 3.223084984581141565, - 3.083228858216868318, 2.978696252647779819, 2.894344007021528942, - 2.82312535054891045, 2.761169372387176857, 2.706113573121819549, - 2.656406411261359679, 2.610972248431847387, 2.56903362592493778, - 2.530009672388827457, 2.493454522095372106, 2.459018177411830486, - 2.426420645533749809, 2.395434278011062457, 2.365871370117638595, - 2.337575241339236776, 2.310413683698762988, 2.284274059677471769, - 2.25905957386919809, 2.234686395590979036, 2.21108140887870297, - 2.188180432076048731, 2.165926793748921497, 2.144270182360394905, - 2.123165708673976138, 2.102573135189237608, 2.082456237992015957, - 2.062782274508307978, 2.043521536655067194, 2.02464697337738464, - 2.006133869963471206, 1.987959574127619033, 1.970103260854325633, - 1.952545729553555764, 1.935269228296621957, 1.918257300864508963, - 1.901494653105150423, 1.884967035707758143, 1.868661140994487768, - 1.852564511728090002, 1.836665460258444904, 1.820952996596124418, - 1.805416764219227366, 1.790046982599857506, 1.77483439558606837, - 1.759770224899592339, 1.744846128113799244, 1.730054160563729182, - 1.71538674071366648, 1.700836618569915748, 1.686396846779167014, - 1.6720607540975998, 1.657821920954023254, 1.643674156862867441, - 1.629611479470633562, 1.615628095043159629, 1.601718380221376581, - 1.587876864890574558, 1.574098216022999264, 1.560377222366167382, - 1.546708779859908844, 1.533087877674041755, 1.519509584765938559, - 1.505969036863201937, 1.492461423781352714, 1.478981976989922842, - 1.465525957342709296, 1.452088642889222792, 1.438665316684561546, - 1.425251254514058319, 1.411841712447055919, 1.398431914131003539, - 1.385017037732650058, 1.371592202427340812, 1.358152454330141534, - 1.34469275175354519, 1.331207949665625279, 1.317692783209412299, - 1.304141850128615054, 1.290549591926194894, 1.27691027356015363, - 1.263217961454619287, 1.249466499573066436, 1.23564948326336066, - 1.221760230539994385, 1.207791750415947662, 1.193736707833126465, - 1.17958738466398616, 1.165335636164750222, 1.150972842148865416, - 1.136489852013158774, 1.121876922582540237, 1.107123647534034028, - 1.092218876907275371, 1.077150624892893482, 1.061905963694822042, - 1.046470900764042922, 1.030830236068192907, 1.014967395251327842, - 0.9988642334929808131, 0.9825008035154263464, 0.9658550794011470098, - 0.9489026255113034436, 0.9316161966151479401, 0.9139652510230292792, - 0.8959153525809346874, 0.8774274291129204872, 0.8584568431938099931, - 0.8389522142975741614, 0.8188539067003538507, 0.7980920606440534693, - 0.7765839878947563557, 0.7542306644540520688, 0.7309119106424850631, - 0.7064796113354325779, 0.6807479186691505202, 0.6534786387399710295, - 0.6243585973360461505, 0.5929629424714434327, 0.5586921784081798625, - 0.5206560387620546848, 0.4774378372966830431, 0.4265479863554152429, - 0.3628714310970211909, 0.2723208648139477384, 0}, - {0.001014352564120377413, 0.002669629083880922793, 0.005548995220771345792, - 0.008624484412859888607, 0.01183947865788486861, 0.01516729801054656976, - 0.01859210273701129151, 0.02210330461592709475, 0.02569329193593428151, - 0.02935631744000685023, 0.03308788614622575758, 0.03688438878665621645, - 0.04074286807444417458, 0.04466086220049143157, 0.04863629585986780496, - 0.05266740190305100461, 0.05675266348104984759, 0.06089077034804041277, - 0.06508058521306804567, 0.06932111739357792179, 0.07361150188411341722, - 0.07795098251397346301, 0.08233889824223575293, 0.08677467189478028919, - 0.09125780082683036809, 0.095787849121731522, 0.1003644410286559929, - 0.1049872554094214289, 0.1096560210148404546, 0.1143705124488661323, - 0.1191305467076509556, 0.1239359802028679736, 0.1287867061959434012, - 0.1336826525834396151, 0.1386237799845948804, 0.1436100800906280339, - 0.1486415742423425057, 0.1537183122081819397, 0.1588403711394795748, - 0.1640078546834206341, 0.1692208922373653057, 0.1744796383307898324, - 0.1797842721232958407, 0.1851349970089926078, 0.1905320403191375633, - 0.1959756531162781534, 0.2014661100743140865, 0.2070037094399269362, - 0.2125887730717307134, 0.2182216465543058426, 0.2239026993850088965, - 0.229632325232116602, 0.2354109422634795556, 0.2412389935454402889, - 0.2471169475123218551, 0.2530452985073261551, 0.2590245673962052742, - 0.2650553022555897087, 0.271138079138385224, 0.2772735029191887857, - 0.2834622082232336471, 0.2897048604429605656, 0.2960021568469337061, - 0.3023548277864842593, 0.3087636380061818397, 0.3152293880650116065, - 0.3217529158759855901, 0.3283350983728509642, 0.3349768533135899506, - 0.3416791412315512977, 0.3484429675463274756, 0.355269384847918035, - 0.3621594953693184626, 0.3691144536644731522, 0.376135469510563536, - 0.3832238110559021416, 0.3903808082373155797, 0.3976078564938743676, - 0.404906420807223999, 0.4122780401026620578, 0.4197243320495753771, - 0.4272469983049970721, 0.4348478302499918513, 0.4425287152754694975, - 0.4502916436820402768, 0.458138716267873114, 0.4660721526894572309, - 0.4740943006930180559, 0.4822076463294863724, 0.4904148252838453348, - 0.4987186354709807201, 0.5071220510755701794, 0.5156282382440030565, - 0.5242405726729852944, 0.5329626593838373561, 0.5417983550254266145, - 0.5507517931146057588, 0.5598274127040882009, 0.5690299910679523787, - 0.5783646811197646898, 0.5878370544347081283, 0.5974531509445183408, - 0.6072195366251219584, 0.6171433708188825973, 0.6272324852499290282, - 0.6374954773350440806, 0.6479418211102242475, 0.6585820000500898219, - 0.6694276673488921414, 0.6804918409973358395, 0.6917891434366769676, - 0.7033360990161600101, 0.7151515074105005976, 0.7272569183441868201, - 0.7396772436726493094, 0.7524415591746134169, 0.7655841738977066102, - 0.7791460859296898134, 0.7931770117713072832, 0.8077382946829627652, - 0.8229072113814113187, 0.8387836052959920519, 0.8555006078694531446, - 0.873243048910072206, 0.8922816507840289901, 0.9130436479717434217, - 0.9362826816850632339, 0.9635996931270905952, 1}}; + {3.713086246740365137, 3.442619855896652314, 3.223084984578618695, + 3.083228858214213552, 2.97869625264501714, 2.894344007018670784, + 2.823125350545966583, 2.761169372384153942, 2.706113573118722471, + 2.656406411258192435, 2.610972248428613085, 2.569033625921639086, + 2.53000967238546659, 2.493454522091950842, 2.459018177408350159, + 2.42642064553021175, 2.39543427800746711, 2.365871370113987737, + 2.337575241335530851, 2.31041368369500244, 2.284274059673657042, + 2.259059573865329629, 2.23468639558705684, 2.211081408874727927, + 2.188180432072020842, 2.165926793744840761, 2.144270182356261323, + 2.123165708669790153, 2.102573135184998776, 2.082456237987724723, + 2.062782274503963453, 2.043521536650669379, 2.024646973372933978, + 2.006133869958966809, 1.987959574123060902, 1.970103260849713323, + 1.952545729548889053, 1.935269228291900179, 1.918257300859732117, + 1.901494653100317844, 1.884967035702869387, 1.868661140989542169, + 1.852564511723087115, 1.836665460253384063, 1.82095299659100518, + 1.805416764214048841, 1.790046982594619251, 1.774834395580769497, + 1.75977022489423196, 1.744846128108376693, 1.730054160558243792, + 1.715386740708116697, 1.700836618564301128, 1.686396846773486446, + 1.672060754091852397, 1.657821920948207683, 1.643674156856982815, + 1.629611479464678325, 1.615628095037132894, 1.601718380215277016, + 1.587876864884400829, 1.574098216016749596, 1.560377222359840665, + 1.546708779853503302, 1.533087877667556054, 1.519509584759370702, + 1.505969036856550147, 1.492461423774615215, 1.478981976983097857, + 1.465525957335794605, 1.452088642882216396, 1.438665316677461448, + 1.425251254506861631, 1.411841712439760199, 1.398431914123606346, + 1.385017037725148503, 1.371592202419732232, 1.35815245432242282, + 1.344692751745713011, 1.331207949657676526, 1.317692783201342976, + 1.304141850120421608, 1.290549591917873107, 1.276910273551699726, + 1.263217961446028159, 1.249466499564333644, 1.235649483254481096, + 1.221760230530962499, 1.207791750406757458, 1.19373670782377217, + 1.179587384654460669, 1.165335636155046872, 1.150972842138975993, + 1.136489852003075507, 1.121876922572254021, 1.107123647523535093, + 1.092218876896553503, 1.07715062488193758, 1.061905963683619225, + 1.046470900752580091, 1.030830236056455407, 1.014967395239299242, + 0.9988642334806433487, 0.982500803502760256, 0.965855079388130533, + 0.9489026254979118224, 0.9316161966013536411, 0.9139652510088016601, + 0.8959153525662384432, 0.8774274290977156499, 0.8584568431780507103, + 0.8389522142812072536, 0.8188539066833174784, 0.7980920606262745798, + 0.7765839878761481296, 0.7542306644345097011, 0.7309119106218809891, + 0.7064796113136078137, 0.6807479186459040044, 0.6534786387150421927, + 0.6243585973090879371, 0.5929629424419777806, 0.5586921783755176563, + 0.5206560387251445432, 0.4774378372537874116, 0.4265479863033045382, + 0.3628714310284174571, 0.2723208647046623798, 0}, + {0.001014352564128608242, 0.002669629083902501886, 0.005548995220816465949, + 0.008624484412930472771, 0.01183947865798230976, 0.01516729801067204057, + 0.01859210273716579986, 0.02210330461611158606, 0.02569329193614960233, + 0.02935631744025383322, 0.03308788614650515908, 0.03688438878696878587, + 0.04074286807479061273, 0.04466086220087242542, 0.04863629586028403451, + 0.05266740190350314293, 0.05675266348153861634, 0.06089077034856634624, + 0.06508058521363185855, 0.06932111739418020391, 0.07361150188475484857, + 0.07795098251465469585, 0.08233889824295743953, 0.0867746718955429569, + 0.09125780082763466916, 0.0957878491225781642, 0.1003644410295455452, + 0.1049872554103545019, 0.1096560210158177701, 0.114370512449888273, + 0.119130546708718546, 0.1239359802039817493, 0.1287867061971039451, + 0.1336826525846476765, 0.1386237799858509867, 0.1436100800919329623, + 0.1486415742436969223, 0.1537183122095865939, 0.1588403711409350494, + 0.1640078546849276508, 0.1692208922389246972, 0.1744796383324022648, + 0.179784272124962119, 0.1851349970107134257, 0.1905320403209136981, + 0.1959756531181103822, 0.2014661100762031587, 0.20700370944187374, + 0.2125887730737360815, 0.2182216465563705243, 0.2239026993871337801, + 0.2296323252343026589, 0.2354109422657276185, 0.2412389935477512459, + 0.2471169475146966499, 0.2530452985097657592, 0.2590245673987107144, + 0.2650553022581619289, 0.2711380791410252789, 0.2772735029218977298, + 0.2834622082260124243, 0.2897048604458105636, 0.2960021568498558686, + 0.3023548277894798075, 0.308763638009251884, 0.3152293880681575344, + 0.3217529158792086785, 0.3283350983761524899, 0.3349768533169711904, + 0.3416791412350137502, 0.3484429675498725287, 0.355269384851547021, + 0.3621594953730332134, 0.3691144536682751665, 0.3761354695144544236, + 0.3832238110598837344, 0.3903808082413894875, 0.3976078564980425889, + 0.4049064208114883656, 0.4122780401070246237, 0.4197243320540382516, + 0.4272469983095623647, 0.4348478302546619489, 0.4425287152802466206, + 0.450291643686926979, 0.4581387162728720042, 0.4660721526945710291, + 0.4740943006982496488, 0.4822076463348387576, 0.4904148252893216209, + 0.4987186354765843488, 0.5071220510813045923, 0.5156282382498721395, + 0.5242405726789928222, 0.5329626593899876585, 0.5417983550317243546, + 0.5507517931210554885, 0.5598274127106949161, 0.5690299910747217416, + 0.5783646811267023624, 0.5878370544418206611, 0.5974531509518123951, + 0.6072195366326049726, 0.6171433708265625651, 0.6272324852578146093, + 0.637495477343144934, 0.6479418211185509202, 0.6585820000586537493, + 0.669427667357706202, 0.6804918410064143552, 0.6917891434460359257, + 0.7033360990258175072, 0.7151515074204771727, 0.7272569183545060101, + 0.7396772436833383146, 0.7524415591857039898, 0.7655841739092361653, + 0.7791460859417033147, 0.7931770117838593537, 0.8077382946961212395, + 0.8229072113952621281, 0.8387836053106473289, 0.8555006078850644347, + 0.8732430489268537821, 0.892281650802302928, 0.9130436479920382986, + 0.9362826817083713671, 0.963599693155767989, 1}}; } // namespace random_internal ABSL_NAMESPACE_END
diff --git a/absl/random/gaussian_distribution.h b/absl/random/gaussian_distribution.h index d14de0b..ccf314e 100644 --- a/absl/random/gaussian_distribution.h +++ b/absl/random/gaussian_distribution.h
@@ -52,15 +52,17 @@ private: friend class TableGenerator; + friend class GaussianDistributionTestPeer; template <typename URBG> inline double zignor_fallback(URBG& g, // NOLINT(runtime/references) bool neg); - // Constants used for the gaussian distribution. - static constexpr double kR = 3.442619855899; // Start of the tail. - static constexpr double kRInv = 0.29047645161474317; // ~= (1.0 / kR) . - static constexpr double kV = 9.91256303526217e-3; + // Constants used for the gaussian distribution (full 53-bit IEEE-754 + // precision for the 128-strip Ziggurat recurrence). + static constexpr double kR = 3.44261985589665212; // Start of the tail. + static constexpr double kRInv = 0.29047645161494128; // 1.0 / kR. + static constexpr double kV = 9.91256303533646108e-3; static constexpr uint64_t kMask = 0x07f; // The ziggurat tables store the pdf(f) and inverse-pdf(x) for equal-area @@ -231,17 +233,22 @@ URBG& g) { // NOLINT(runtime/references) using random_internal::GeneratePositiveTag; using random_internal::GenerateRealFromBits; - using random_internal::GenerateSignedTag; while (true) { - // We use a single uint64_t to generate both a double and a strip. - // These bits are unused when the generated double is > 1/2^5. - // This may introduce some bias from the duplicated low bits of small - // values (those smaller than 1/2^5, which all end up on the left tail). - uint64_t bits = fast_u64_(g); - int i = static_cast<int>(bits & kMask); // pick a random strip - double j = GenerateRealFromBits<double, GenerateSignedTag, false>( - bits); // U(-1, 1) + // Extract disjoint bitfields from a single uint64_t: + // bits[0..6] (7 bits): strip index i in [0, 127]. + // bits[10..63] (54 bits): signed integer s in [-2^53, 2^53 - 1]. + // bits[7..9] (3 bits): unused. + // Scaling s by 2^-53 produces an exact double j in [-1.0, 1.0) that is + // independent of i, includes +0.0 with exact single-grid weight 2^-54 (no + // -0.0), and avoids truncation-toward-zero bias. At the sole asymmetric + // endpoint j = -1.0 (s = -2^53), strips i > 0 enter the wedge test at + // f(x) = f[i] (rejected up to ~1 ULP libm rounding), and i == 0 falls back + // to the negative tail. + const uint64_t bits = fast_u64_(g); + const int i = static_cast<int>(bits & kMask); // pick a random strip + const int64_t s = static_cast<int64_t>(bits) >> 10; + const double j = static_cast<double>(s) * 0x1p-53; // U[-1, 1) const double x = j * zg_.x[i]; // Rectangular box. Handles >97% of all cases.
diff --git a/absl/random/gaussian_distribution_test.cc b/absl/random/gaussian_distribution_test.cc index 65fd85a..eec40ad 100644 --- a/absl/random/gaussian_distribution_test.cc +++ b/absl/random/gaussian_distribution_test.cc
@@ -18,6 +18,7 @@ #include <cmath> #include <cstddef> #include <cstdint> +#include <initializer_list> #include <ios> #include <iterator> #include <limits> @@ -25,15 +26,18 @@ #include <sstream> #include <string> #include <type_traits> +#include <utility> #include <vector> #include "gmock/gmock.h" #include "gtest/gtest.h" +#include "absl/base/config.h" #include "absl/base/macros.h" #include "absl/log/log.h" #include "absl/numeric/internal/representation.h" #include "absl/random/internal/chi_square.h" #include "absl/random/internal/distribution_test_util.h" +#include "absl/random/internal/pcg_engine.h" #include "absl/random/internal/sequence_urbg.h" #include "absl/random/random.h" #include "absl/strings/str_cat.h" @@ -41,10 +45,32 @@ #include "absl/strings/str_replace.h" #include "absl/strings/strip.h" +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace random_internal { + +class GaussianDistributionTestPeer { + public: + static constexpr double kR = gaussian_distribution_base::kR; + static constexpr double kRInv = gaussian_distribution_base::kRInv; + static constexpr double kV = gaussian_distribution_base::kV; + static constexpr size_t kNumStrips = gaussian_distribution_base::kMask + 1; + + static double x(size_t i) { return gaussian_distribution_base::zg_.x[i]; } + static double f(size_t i) { return gaussian_distribution_base::zg_.f[i]; } +}; + +} // namespace random_internal +ABSL_NAMESPACE_END +} // namespace absl + namespace { +using absl::random_internal::GaussianDistributionTestPeer; using absl::random_internal::kChiSquared; +MATCHER(IsPositiveZero, "is +0.0") { return arg == 0 && !std::signbit(arg); } + template <typename RealType> class GaussianDistributionInterfaceTest : public ::testing::Test {}; @@ -391,26 +417,48 @@ // NOTE: absl::gaussian_distribution is not guaranteed to be stable. TEST(GaussianDistributionTest, StabilityTest) { // absl::gaussian_distribution stability relies on the underlying zignor - // data, absl::random_interna::RandU64ToDouble, std::exp, std::log, and - // std::abs. - absl::random_internal::sequence_urbg urbg( - {0x0003eb76f6f7f755ull, 0xFFCEA50FDB2F953Bull, 0xC332DDEFBE6C5AA5ull, - 0x6558218568AB9702ull, 0x2AEF7DAD5B6E2F84ull, 0x1521B62829076170ull, - 0xECDD4775619F1510ull, 0x13CCA830EB61BD96ull, 0x0334FE1EAA0363CFull, - 0xB5735C904C70A239ull, 0xD59E9E0BCBAADE14ull, 0xEECC86BC60622CA7ull}); + // data, bit extraction, std::exp, std::log, and std::abs. + absl::random_internal::sequence_urbg urbg({ + 0x0003eb76f6f7f755ull, + 0xFFCEA50FDB2F953Bull, + 0xC332DDEFBE6C5AA5ull, + 0x6558218568AB9702ull, + 0x2AEF7DAD5B6E2F84ull, + 0x1521B62829076170ull, + 0xECDD4775619F1510ull, + 0x13CCA830EB61BD96ull, + 0x0334FE1EAA0363CFull, + 0xB5735C904C70A239ull, + 0xD59E9E0BCBAADE14ull, + 0xEECC86BC60622CA7ull, + // Wedge accept (strip 59, j ~= +0.995, v ~= 0.875) -> 2 calls. + 0x7F5C28F5C28F5C3Bull, + 0xE000000000000001ull, + // Wedge reject (strip 59, j ~= -0.9985, v ~= 0.0625) + retry -> 3 calls. + 0x80315AF024D06A3Bull, + 0x1000000000000001ull, + 0x4000000000000020ull, + // Tail fallback (strip 0, j = -0.9375): reject then accept -> 5 calls. + 0x8800000000000000ull, + 0x0000100000000001ull, + 0xC000000000000001ull, + 0x13CCA830EB61BD96ull, + 0x00000076F6F7F755ull, + }); - std::vector<int> output(11); + std::vector<int> output(15); { absl::gaussian_distribution<double> dist; std::generate(std::begin(output), std::end(output), [&] { return static_cast<int>(10000000.0 * dist(urbg)); }); - EXPECT_EQ(13, urbg.invocations()); - EXPECT_THAT(output, // - testing::ElementsAre(1494, 25518841, 9991550, 1351856, - -20373238, 3456682, 333530, -6804981, - -15279580, -16459654, 1494)); + EXPECT_EQ(22, urbg.invocations()); + EXPECT_THAT( + output, // + testing::ElementsAre(1494, -24125, -9192725, 25518841, 9991550, 1351856, + -3581104, 3456682, 333530, -9491133, -7563160, + -2555292, 15937097, 10123234, -41861012)); } urbg.reset(); @@ -419,18 +467,17 @@ std::generate(std::begin(output), std::end(output), [&] { return static_cast<int>(1000000.0f * dist(urbg)); }); - EXPECT_EQ(13, urbg.invocations()); + EXPECT_EQ(22, urbg.invocations()); EXPECT_THAT( output, // - testing::ElementsAre(149, 2551884, 999155, 135185, -2037323, 345668, - 33353, -680498, -1527958, -1645965, 149)); + testing::ElementsAre(149, -2412, -919272, 2551884, 999155, 135185, + -358110, 345668, 33353, -949113, -756316, -255529, + 1593709, 1012323, -4186101)); } } // This is an implementation-specific test. If any part of the implementation // changes, then it is likely that this test will change as well. -// Also, if dependencies of the distribution change, such as RandU64ToDouble, -// then this is also likely to change. TEST(GaussianDistributionTest, AlgorithmBounds) { absl::gaussian_distribution<double> dist; @@ -443,21 +490,22 @@ // for i in range(0, len(X)-1): // print i, X[i+1]/X[i], (X[i+1]/X[i] > 0.984375) // - // 0.125 <= |values| <= 0.75 + // 0.125 <= |values| <= 0.75. Positive values have bit 63 == 0; negative + // values use two's complement (0xa000... == -0.75, 0xf000... == -0.125). const uint64_t kValues[] = { 0x1000000000000100ull, 0x2000000000000100ull, 0x3000000000000100ull, 0x4000000000000100ull, 0x5000000000000100ull, 0x6000000000000100ull, - // negative values - 0x9000000000000100ull, 0xa000000000000100ull, 0xb000000000000100ull, - 0xc000000000000100ull, 0xd000000000000100ull, 0xe000000000000100ull}; + // negative values (-0.75 to -0.125) + 0xa000000000000100ull, 0xb000000000000100ull, 0xc000000000000100ull, + 0xd000000000000100ull, 0xe000000000000100ull, 0xf000000000000100ull}; // 0.875 <= |values| <= 0.984375 const uint64_t kExtraValues[] = { 0x7000000000000100ull, 0x7800000000000100ull, // 0x7c00000000000100ull, 0x7e00000000000100ull, // - // negative values - 0xf000000000000100ull, 0xf800000000000100ull, // - 0xfc00000000000100ull, 0xfe00000000000100ull}; + // negative values (-0.875 to -0.984375) + 0x9000000000000100ull, 0x8800000000000100ull, // + 0x8400000000000100ull, 0x8200000000000100ull}; auto make_box = [](uint64_t v, uint64_t box) { return (v & 0xffffffffffffff80ull) | box; @@ -517,7 +565,7 @@ { // -0.9375 absl::random_internal::sequence_urbg urbg( - {make_fallback(0xf800000000000000ull), 0x13CCA830EB61BD96ull, + {make_fallback(0x8800000000000000ull), 0x13CCA830EB61BD96ull, 0x00000076f6f7f755ull}); tail[1] = dist(urbg); EXPECT_EQ(3, urbg.invocations()); @@ -541,7 +589,7 @@ { // -0.9921875, 0.875 absl::random_internal::sequence_urbg urbg( - {make_box(0xff00000000000000ull, 120), 0xe000000000000001ull, + {make_box(0x8100000000000000ull, 120), 0xe000000000000001ull, 0x13CCA830EB61BD96ull}); tail[1] = dist(urbg); EXPECT_EQ(2, urbg.invocations()); @@ -554,11 +602,192 @@ { // -0.9921875, 0.0625 absl::random_internal::sequence_urbg urbg( - {make_box(0xff00000000000000ull, 120), 0x1000000000000001, + {make_box(0x8100000000000000ull, 120), 0x1000000000000001, make_box(0x1000000000000100ull, 50), 0x13CCA830EB61BD96ull}); dist(urbg); EXPECT_EQ(3, urbg.invocations()); } } +TEST(GaussianDistributionTest, ZeroReachableAndPositiveSign) { + auto sample_double = [](std::initializer_list<uint64_t> words) { + absl::gaussian_distribution<double> dist; + absl::random_internal::sequence_urbg urbg(words); + double value = dist(urbg); + return std::pair<double, size_t>{value, urbg.invocations()}; + }; + auto sample_float = [](std::initializer_list<uint64_t> words) { + absl::gaussian_distribution<float> dist; + absl::random_internal::sequence_urbg urbg(words); + float value = dist(urbg); + return std::pair<float, size_t>{value, urbg.invocations()}; + }; + + // s == 0 across fast-path strips [0, 126], including unused bits [7..9]. + EXPECT_THAT(sample_double({0x0000000000000000ull}), + testing::Pair(IsPositiveZero(), 1)); + EXPECT_THAT(sample_double({0x0000000000000040ull}), + testing::Pair(IsPositiveZero(), 1)); + EXPECT_THAT(sample_double({0x000000000000007eull}), + testing::Pair(IsPositiveZero(), 1)); + EXPECT_THAT(sample_double({0x00000000000003aaull}), + testing::Pair(IsPositiveZero(), 1)); + + // Top strip i == 127 has zg_.x[128] == 0.0, so 0.0 passes through the wedge. + EXPECT_THAT(sample_double({0x000000000000007full, 0x8000000000000000ull}), + testing::Pair(IsPositiveZero(), 2)); + + // Exact +0.0f is reachable for float as well. + EXPECT_THAT(sample_float({0x0000000000000000ull}), + testing::Pair(IsPositiveZero(), 1)); + EXPECT_THAT(sample_float({0x000000000000007full, 0x8000000000000000ull}), + testing::Pair(IsPositiveZero(), 2)); +} + +TEST(GaussianDistributionTest, DisjointStripAndMantissaNearZero) { + absl::gaussian_distribution<double> dist; + + // Smallest positive and negative non-zero variates j = +/-2^-53 must be + // completely independent of strip index i across all 128 strips. + std::vector<double> pos_ratios; + std::vector<double> neg_ratios; + pos_ratios.reserve(GaussianDistributionTestPeer::kNumStrips); + neg_ratios.reserve(GaussianDistributionTestPeer::kNumStrips); + + constexpr uint64_t kPlusOne = uint64_t{1} << 10; + constexpr uint64_t kMinusOne = ~uint64_t{0x3ff}; + for (size_t i = 0; i < GaussianDistributionTestPeer::kNumStrips; ++i) { + // Provide a mid-range wedge draw in case i == 127. + absl::random_internal::sequence_urbg pos_urbg( + {kPlusOne | i, 0x8000000000000000ull}); + absl::random_internal::sequence_urbg neg_urbg( + {kMinusOne | i, 0x8000000000000000ull}); + const double pos = dist(pos_urbg); + const double neg = dist(neg_urbg); + const double expected = 0x1p-53 * GaussianDistributionTestPeer::x(i); + pos_ratios.push_back(pos / expected); + neg_ratios.push_back(neg / -expected); + } + EXPECT_THAT(pos_ratios, testing::Each(testing::DoubleEq(1.0))); + EXPECT_THAT(neg_ratios, testing::Each(testing::DoubleEq(1.0))); + + // At the sole asymmetric endpoint j = -1.0 (s = -2^53): + // - strip 0 routes to the negative tail fallback (< -kR); + // - strips 1..127 enter the wedge test at f(x) = f[i], rejecting for any v + // bounded away from 1 by more than libm's ~1 ULP exp() tolerance. + { + absl::random_internal::sequence_urbg urbg( + {0x8000000000000000ull, 0x13CCA830EB61BD96ull, 0x00000076f6f7f755ull}); + EXPECT_THAT(dist(urbg), testing::Lt(-GaussianDistributionTestPeer::kR)); + EXPECT_THAT(urbg.invocations(), testing::Eq(3)); + } + // v = 1 - 2^-32 keeps zg_.f[i+1] + v * (zg_.f[i] - zg_.f[i+1]) at least + // ~6.7e-13 above zg_.f[i], well above cross-platform 1 ULP libm exp() + // differences (~1e-16). + constexpr uint64_t kNearOneWedge = 0xffffffff00000000ull; + std::vector<size_t> neg_one_invocations; + neg_one_invocations.reserve(GaussianDistributionTestPeer::kNumStrips - 1); + for (size_t i = 1; i < GaussianDistributionTestPeer::kNumStrips; ++i) { + absl::random_internal::sequence_urbg urbg( + {0x8000000000000000ull | i, kNearOneWedge, 0x0ull}); + EXPECT_THAT(dist(urbg), IsPositiveZero()); + neg_one_invocations.push_back(urbg.invocations()); + } + EXPECT_THAT(neg_one_invocations, testing::Each(testing::Eq(3))); + + // Mode-region density check across |Z| < 2^-4 (the region where bit overlap + // previously occurred) and |Z| < 2^-8. + absl::random_internal::pcg64_2018_engine rng(0x2B7E151628AED2A6ull); + constexpr int kSamples = 500000; + constexpr double kEps4 = 0x1p-4; + constexpr double kEps8 = 0x1p-8; + int pos_eps4 = 0; + int neg_eps4 = 0; + int abs_eps8 = 0; + for (int n = 0; n < kSamples; ++n) { + const double z = dist(rng); + if (std::abs(z) < kEps4) { + if (z >= 0.0) { + ++pos_eps4; + } else { + ++neg_eps4; + } + if (std::abs(z) < kEps8) { + ++abs_eps8; + } + } + } + const double expected_p4 = std::erf(kEps4 / std::sqrt(2.0)); + const double expected_p8 = std::erf(kEps8 / std::sqrt(2.0)); + const double se_p4 = std::sqrt(expected_p4 * (1.0 - expected_p4) / kSamples); + const double se_p8 = std::sqrt(expected_p8 * (1.0 - expected_p8) / kSamples); + const double se_half_p4 = + std::sqrt((expected_p4 / 2.0) * (1.0 - expected_p4 / 2.0) / kSamples); + + EXPECT_THAT(static_cast<double>(pos_eps4 + neg_eps4) / kSamples, + testing::DoubleNear(expected_p4, 4.0 * se_p4)); + EXPECT_THAT(static_cast<double>(pos_eps4) / kSamples, + testing::DoubleNear(expected_p4 / 2.0, 4.0 * se_half_p4)); + EXPECT_THAT(static_cast<double>(neg_eps4) / kSamples, + testing::DoubleNear(expected_p4 / 2.0, 4.0 * se_half_p4)); + EXPECT_THAT(static_cast<double>(abs_eps8) / kSamples, + testing::DoubleNear(expected_p8, 4.0 * se_p8)); +} + +TEST(GaussianDistributionTest, ZigguratTableConsistency) { + constexpr size_t kC = GaussianDistributionTestPeer::kNumStrips; + constexpr double kR = GaussianDistributionTestPeer::kR; + constexpr double kRInv = GaussianDistributionTestPeer::kRInv; + constexpr double kV = GaussianDistributionTestPeer::kV; + + EXPECT_THAT(kRInv, testing::DoubleEq(1.0 / kR)); + EXPECT_THAT(GaussianDistributionTestPeer::x(1), testing::DoubleEq(kR)); + EXPECT_THAT(GaussianDistributionTestPeer::x(kC), testing::DoubleEq(0.0)); + EXPECT_THAT(GaussianDistributionTestPeer::f(kC), testing::DoubleEq(1.0)); + + // Verify strict monotonicity of x (decreasing) and f (increasing). + for (size_t i = 0; i < kC; ++i) { + EXPECT_THAT(GaussianDistributionTestPeer::x(i), + testing::Gt(GaussianDistributionTestPeer::x(i + 1))); + EXPECT_THAT(GaussianDistributionTestPeer::f(i), + testing::Lt(GaussianDistributionTestPeer::f(i + 1))); + } + + // Strip 0 box area (x[0] * f[1]) and true tail area must match kV. + EXPECT_THAT(std::abs(GaussianDistributionTestPeer::x(0) * + GaussianDistributionTestPeer::f(1) - + kV) / + kV, + testing::Lt(1e-15)); + const double sqrt_pi_over_2 = std::sqrt(std::acos(0.0)); + const double tail_area = kR * std::exp(-0.5 * kR * kR) + + sqrt_pi_over_2 * std::erfc(kR / std::sqrt(2.0)); + EXPECT_THAT(std::abs(tail_area - kV) / kV, testing::Lt(1e-13)); + + // Every strip i in [1, kC - 1] must have equal area kV to < 1e-13. + std::vector<double> strip_area_rel_errors; + strip_area_rel_errors.reserve(kC - 1); + for (size_t i = 1; i < kC; ++i) { + const double area = GaussianDistributionTestPeer::x(i) * + (GaussianDistributionTestPeer::f(i + 1) - + GaussianDistributionTestPeer::f(i)); + strip_area_rel_errors.push_back(std::abs(area - kV) / kV); + } + EXPECT_THAT(strip_area_rel_errors, testing::Each(testing::Lt(1e-13))); + + // Every stored f[i] must match std::exp(-0.5 * x[i] * x[i]) within 1 ULP. + std::vector<double> f_ulp_errors; + f_ulp_errors.reserve(kC + 1); + for (size_t i = 0; i <= kC; ++i) { + const double xi = GaussianDistributionTestPeer::x(i); + const double expected_f = std::exp(-0.5 * xi * xi); + const double ulp = + std::nextafter(expected_f, std::numeric_limits<double>::infinity()) - + expected_f; + f_ulp_errors.push_back( + std::abs(GaussianDistributionTestPeer::f(i) - expected_f) / ulp); + } + EXPECT_THAT(f_ulp_errors, testing::Each(testing::Le(1.0))); +} + } // namespace
diff --git a/absl/random/internal/gaussian_distribution_gentables.cc b/absl/random/internal/gaussian_distribution_gentables.cc index 967a327..ab444ab 100644 --- a/absl/random/internal/gaussian_distribution_gentables.cc +++ b/absl/random/internal/gaussian_distribution_gentables.cc
@@ -100,10 +100,15 @@ tables_.x[kC] = 0.0; tables_.f[kC] = f(tables_.x[kC]); // 1.0 + // Advance the Ziggurat area recurrence using a running `v` to avoid + // accumulating round-trip f(f_inv(v)) rounding error across steps, while + // storing f(tables_.x[i]) so zg_.f[i] matches std::exp(-0.5 * x * x) in the + // wedge test. + double v = tables_.f[1]; for (int i = 2; i < kC; i++) { - double v = (kV / tables_.x[i - 1]) + tables_.f[i - 1]; + v += kV / tables_.x[i - 1]; tables_.x[i] = f_inv(v); - tables_.f[i] = v; + tables_.f[i] = f(tables_.x[i]); } } @@ -113,6 +118,8 @@ "\n" "#include \"absl/random/gaussian_distribution.h\"\n" "\n" + "#include \"absl/base/config.h\"\n" + "\n" "namespace absl {\n" "ABSL_NAMESPACE_BEGIN\n" "namespace random_internal {\n"