mbeutel / slowmath

Checked arithmetic for C++
https://mbeutel.github.io/slowmath
Other
2 stars 0 forks source link

Efficiency of `powi()` #1

Open mbeutel opened 4 years ago

mbeutel commented 4 years ago

The implementation of powi() attempts to achieve 𝒪(log(N)) rather than the 𝒪(N) of a naïve implementation (multiplying factors in a loop). But is this actually faster? Is any compiler capable of compiling bit_scan_reverse() as BSR? Can this be forced with an intrinsic (guarded by std::is_constant_evaluated())?

mbeutel commented 4 years ago

We could also resort to the functions from the C++20 \<bit> header instead of using BSR intrinsics ourself. There is no std::is_constant_evaluated() in pre-C++20, so we wouldn't be able to speed up pre-C++20 code with intrinsics anyway because we want to be constexpr.