Avoid using wider types in generate_canonical when the range of the random generator is a power of 2 (#4850)

statementreply · web-flow · commit 3bc0f3e69bdc · 2024-08-07T23:40:54.000-07:00
diff --git a/stl/inc/random b/stl/inc/random
@@ -310,32 +310,32 @@ _NODISCARD _Real generate_canonical(_Gen& _Gx) { // build a floating-point value
         constexpr auto _Gxmax  = (_Gen::max)();
         constexpr auto _Params = _Generate_canonical_params(_Minbits, _Gxmax - _Gxmin);
 
-        using _Sx_type = conditional_t<_Params._Smax_bits <= 32, uint32_t,
-            conditional_t<_Params._Smax_bits <= 64, uint64_t, _Unsigned128>>;
-        _Sx_type _Sx;
+        _STL_INTERNAL_STATIC_ASSERT(_Params._Kx >= 1);
 
         if constexpr (_Params._Rx_is_pow2) {
-            // Always needs only one attempt. Multiplications can be replaced with shift/add. Optimize k=1 case.
-            if constexpr (_Params._Kx == 1) {
-                _Sx = static_cast<_Sx_type>(_Gx() - _Gxmin);
-            } else if constexpr (_Params._Kx > 1) {
+            // Always needs only one attempt. Multiplications can be replaced with shift/add.
+            constexpr int _Discarded_bits = _Params._Smax_bits - _Minbits;
+            _Result_uint_type _Sx         = static_cast<_Result_uint_type>((_Gx() - _Gxmin) >> _Discarded_bits);
+
+            if constexpr (_Params._Kx > 1) {
                 constexpr int _Rx_bits = _Params._Smax_bits / _Params._Kx;
-                _Sx                    = 0;
-                int _Shift             = 0;
-                for (int _Idx = 0; _Idx < _Params._Kx; ++_Idx) {
-                    _Sx += static_cast<_Sx_type>(_Gx() - _Gxmin) << _Shift;
+                int _Shift             = -_Discarded_bits;
+                for (int _Idx = 1; _Idx < _Params._Kx; ++_Idx) {
                     _Shift += _Rx_bits;
+                    _Sx += static_cast<_Result_uint_type>(_Gx() - _Gxmin) << _Shift;
                 }
-            } else {
-                _STL_INTERNAL_STATIC_ASSERT(false); // unexpected k
             }
 
-            _Sx >>= _Params._Smax_bits - _Minbits;
-            return static_cast<_Real>(static_cast<_Result_uint_type>(_Sx)) * static_cast<_Real>(_Params._Scale);
+            return static_cast<_Real>(_Sx) * static_cast<_Real>(_Params._Scale);
         } else {
+            using _Sx_type = conditional_t<_Params._Smax_bits <= 32, uint32_t,
+                conditional_t<_Params._Smax_bits <= 64, uint64_t, _Unsigned128>>;
+
             constexpr auto _Rx        = _Sx_type{_Gxmax - _Gxmin} + 1u;
             constexpr _Sx_type _Limit = static_cast<_Sx_type>(_Params._Xx) * (_Sx_type{1} << _Minbits);
 
+            _Sx_type _Sx;
+
             do {
                 // unroll first two iterations to avoid unnecessary multiplications
                 _Sx = static_cast<_Sx_type>(_Gx() - _Gxmin);
diff --git a/tests/std/tests/P0952R2_new_generate_canonical/test.cpp b/tests/std/tests/P0952R2_new_generate_canonical/test.cpp
@@ -128,7 +128,7 @@ int main() {
         const auto expected3 = ldexpf(0xDE'55'2C >> (3 * 8 - 24), -24);
 
         assert((generate_with_ibe<float, 24, Engine>) () == expected1);
-        assert((generate_with_ibe<float, 20, Engine>) () == expected2); // needs a 64 bit accumulator for $S$
+        assert((generate_with_ibe<float, 20, Engine>) () == expected2);
         assert((generate_with_ibe<float, 8, Engine>) () == expected3);
     }
 
@@ -149,7 +149,7 @@ int main() {
 
         assert((generate_with_ibe<double, 64, Engine>) () == expected1);
         assert((generate_with_ibe<double, 32, Engine>) () == expected2);
-        assert((generate_with_ibe<double, 24, Engine>) () == expected3); // needs a 128 bit accumulator for $S$
+        assert((generate_with_ibe<double, 24, Engine>) () == expected3);
     }
 
     {

Original file line number	Diff line number	Diff line change
`@@ -128,7 +128,7 @@ int main() {`
`128`	`128`	`const auto expected3 = ldexpf(0xDE'55'2C >> (3 * 8 - 24), -24);`
`129`	`129`
`130`	`130`	`assert((generate_with_ibe<float, 24, Engine>) () == expected1);`
`131`		`- assert((generate_with_ibe<float, 20, Engine>) () == expected2); // needs a 64 bit accumulator for $S$`
	`131`	`+ assert((generate_with_ibe<float, 20, Engine>) () == expected2);`
`132`	`132`	`assert((generate_with_ibe<float, 8, Engine>) () == expected3);`
`133`	`133`	`}`
`134`	`134`
`@@ -149,7 +149,7 @@ int main() {`
`149`	`149`
`150`	`150`	`assert((generate_with_ibe<double, 64, Engine>) () == expected1);`
`151`	`151`	`assert((generate_with_ibe<double, 32, Engine>) () == expected2);`
`152`		`- assert((generate_with_ibe<double, 24, Engine>) () == expected3); // needs a 128 bit accumulator for $S$`
	`152`	`+ assert((generate_with_ibe<double, 24, Engine>) () == expected3);`
`153`	`153`	`}`
`154`	`154`
`155`	`155`	`{`