4 ms·
Doubling the speed of std:uniform_int_distribution in the GNU C++ library
- paulddraper 7y ago> It is somewhat puzzling that the C++ language does not see fit to make it easy to compute the full product between two integers. Perhaps, but certainly not surprising. This is the same language where you can't even have signed overflow without nasal demons. --- Anyway, this would be a slow, standard way (not sure about best way to calculate base). // big-endian array result std::array<Int, 2> multiply<class Int = int>(Int x, Int y) { // assumes radix 2, and even number of digits int base = 1 << std::numeric_limits<IntType>::digits / 2; Int x_1 = x % base, x_2 = x / base; Int y_1 = y % base, y_2 = x / base; Int z_11 = x_1 * y_1; Int z_12 = x_1 * y_2; Int z_21 = x_2 * y_2; Int z_22 = x_2 * y_2; return { z_11 + z_12 % base + z_21 % base, z_22 + z_12 / base + z_22 / base } }
- deleted 7y ago[deleted]
- leni536 7y agoI think you made some mistakes in your implementation, here is my version: //1. It's little-endian //2. I think you calculated the 0th element wrong //3. There were several typos/copy-paste errors #include <array> #include <limits> // little-endian array result template <typename Int=int> std::array<Int, 2> multiply(Int x, Int y) { using Unsigned = std::make_unsigned_t<Int>; // assumes radix 2, and even number of digits Unsigned base = Unsigned(1) << std::numeric_limits<Unsigned>::digits / 2; Unsigned x_1 = x % base, x_2 = x / base; Unsigned y_1 = y % base, y_2 = y / base; Unsigned z_11 = x_1 * y_1; Unsigned z_12 = x_1 * y_2; Unsigned z_21 = x_2 * y_1; Unsigned z_22 = x_2 * y_2; return { z_11 + z_12 * base + z_21 * base, z_22 + z_12 / base + z_21 / base }; } Also I think integer overflow UB is way overblown. I even would like a narrow-contract unsigned type too.
- 29athrowaway 7y agoWould it not be possible to reuse that value? -uint64_t(__uerange) % uint64_t(__uerange)
- saagarjha 7y agoWhat, uint64_t(__uerange)?
- nightcracker 7y agoI had the same thought in this discussion: https://www.reddit.com/r/cpp/comments/daif4f/doubling_the_speed_of_stduniform_int_distribution/f1qiedw/ https://www.reddit.com/r/cpp/comments/daif4f/doubling_the_sp...