2 ms·
> 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 s
by 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.