Testing at godbolt shows that the compiler (ARM GCC none-eabi) generates an efficient code for that.
The gist is the following
a * 10 = (a * 8) + (a * 2) = (a << 3) + (a << 1);Plus, every number can be represented as a sum of multiples of 2. Proof:
X = 2^0 * x = 1 + 1 + ...
Everything else is just extrapolation.
| #include <iostream> | |
| #include <limits> | |
| using namespace std; | |
| template <uint64_t aValue> | |
| constexpr uint64_t closestMul2SupOffset() | |
| { | |
| return | |
| (1ULL << 63) <= aValue ? 63 : | |
| (1ULL << 62) <= aValue ? 62 : | |
| (1ULL << 61) <= aValue ? 61 : | |
| (1ULL << 60) <= aValue ? 60 : | |
| (1ULL << 59) <= aValue ? 59 : | |
| (1ULL << 58) <= aValue ? 58 : | |
| (1ULL << 57) <= aValue ? 57 : | |
| (1ULL << 56) <= aValue ? 56 : | |
| (1ULL << 55) <= aValue ? 55 : | |
| (1ULL << 54) <= aValue ? 54 : | |
| (1ULL << 53) <= aValue ? 53 : | |
| (1ULL << 52) <= aValue ? 52 : | |
| (1ULL << 51) <= aValue ? 51 : | |
| (1ULL << 50) <= aValue ? 50 : | |
| (1ULL << 49) <= aValue ? 49 : | |
| (1ULL << 48) <= aValue ? 48 : | |
| (1ULL << 47) <= aValue ? 47 : | |
| (1ULL << 46) <= aValue ? 46 : | |
| (1ULL << 45) <= aValue ? 45 : | |
| (1ULL << 44) <= aValue ? 44 : | |
| (1ULL << 43) <= aValue ? 43 : | |
| (1ULL << 42) <= aValue ? 42 : | |
| (1ULL << 41) <= aValue ? 41 : | |
| (1ULL << 40) <= aValue ? 40 : | |
| (1ULL << 39) <= aValue ? 39 : | |
| (1ULL << 38) <= aValue ? 38 : | |
| (1ULL << 37) <= aValue ? 37 : | |
| (1ULL << 36) <= aValue ? 36 : | |
| (1ULL << 35) <= aValue ? 35 : | |
| (1ULL << 34) <= aValue ? 34 : | |
| (1ULL << 33) <= aValue ? 33 : | |
| (1ULL << 32) <= aValue ? 32 : | |
| (1ULL << 31) <= aValue ? 31 : | |
| (1ULL << 30) <= aValue ? 30 : | |
| (1ULL << 29) <= aValue ? 29 : | |
| (1ULL << 28) <= aValue ? 28 : | |
| (1ULL << 27) <= aValue ? 27 : | |
| (1ULL << 26) <= aValue ? 26 : | |
| (1ULL << 25) <= aValue ? 25 : | |
| (1ULL << 24) <= aValue ? 24 : | |
| (1ULL << 23) <= aValue ? 23 : | |
| (1ULL << 22) <= aValue ? 22 : | |
| (1ULL << 21) <= aValue ? 21 : | |
| (1ULL << 20) <= aValue ? 20 : | |
| (1ULL << 19) <= aValue ? 19 : | |
| (1ULL << 18) <= aValue ? 18 : | |
| (1ULL << 17) <= aValue ? 17 : | |
| (1ULL << 16) <= aValue ? 16 : | |
| (1ULL << 15) <= aValue ? 15 : | |
| (1ULL << 14) <= aValue ? 14 : | |
| (1ULL << 13) <= aValue ? 13 : | |
| (1ULL << 12) <= aValue ? 12 : | |
| (1ULL << 11) <= aValue ? 11 : | |
| (1ULL << 10) <= aValue ? 10 : | |
| (1ULL << 9) <= aValue ? 9 : | |
| (1ULL << 8) <= aValue ? 8 : | |
| (1ULL << 7) <= aValue ? 7 : | |
| (1ULL << 6) <= aValue ? 6 : | |
| (1ULL << 5) <= aValue ? 5 : | |
| (1ULL << 4) <= aValue ? 4 : | |
| (1ULL << 3) <= aValue ? 3 : | |
| (1ULL << 2) <= aValue ? 2 : | |
| (1ULL << 1) <= aValue ? 1 : | |
| 0; | |
| }; | |
| template<uint64_t kMultiplier> | |
| inline uint64_t fastMul(uint64_t aValue) | |
| { | |
| static constexpr uint64_t kResidualMultiplier = kMultiplier - (1ULL << closestMul2SupOffset<kMultiplier>()); | |
| return kMultiplier == 0ULL ? 0ULL : (aValue << closestMul2SupOffset<kMultiplier>()) + fastMul<kResidualMultiplier>(aValue); | |
| } | |
| int main(void) | |
| { | |
| uint64_t value = fastMul<100>(25); | |
| std::cout << value << std::endl; | |
| return 0; | |
| } |