-2

Sergiu Dotenco kindly contributed his implementation based on boost, could someone recommend an open-source c++11 style implementation, without boost? Google does provided some results, but this is a bit deep in math, I could not differentiate the quality of the implmentation.

athos
  • 6,120
  • 5
  • 51
  • 95
  • Much of the boost used there have been absorbed into the standard library. The only tricky part is the use of `boost::mpl::apply` etc. That however seems to be only for optimising the compile time `%` calculation – Caleth Dec 08 '17 at 09:21
  • It looks like you can replace the `mpl` with `constexpr` functions – Caleth Dec 08 '17 at 09:29
  • @Caleth yeah the mpl is my headache. how to replace it with `constexpr`? could you give some example? – athos Dec 08 '17 at 09:33

1 Answers1

1

Here's how c++11 has made compile time programming (slightly) easier

template <typename UIntType> constexpr bool IsPowerOfTwo(UIntType r)
{
    return (r & (r - 1)) == 0;
}

namespace detail
{
    template<class UIntType, UIntType r, bool>
    struct ModuloHelper;

    template<class UIntType, UIntType r>
    struct ModuloHelper<UIntType, r, true>
    {
        template<class T>
        static T calc(T value)
        {
            return value & (r - 1);
        }
    };

    template<class UIntType, UIntType r>
    struct ModuloHelper<UIntType, r, false>
    {
        template<class T>
        static T calc(T value)
        {
            while (value >= r)
            { value -= r; }

            return value;
        }
    };
}

template<class UIntType, UIntType r>
struct Modulo : detail::ModuloHelper<UIntType, r, IsPowerOfTwo(r)>
Caleth
  • 52,200
  • 2
  • 44
  • 75
  • As I look at this, you don't even need the definition `IsPowerOfTwo`, you can just put the expression `(r & (r - 1)) == 0` there. `IsPowerOfTwo` is reusable, however – Caleth Dec 08 '17 at 09:47
  • Further, I'm not certain that a modern compiler wouldn't just *do all this* for you, when you write `x % r`, given that `r` is a template parameter – Caleth Dec 08 '17 at 09:49
  • that's another topic, basically i'm looking for a way to nominally get rid of boost. – athos Dec 08 '17 at 09:52
  • looking at the output of say https://godbolt.org/g/SFGioT it seems you can just drop it – Caleth Dec 08 '17 at 10:05
  • sorry i don't get it here, from *where* you found that *what* could be dropped? – athos Dec 08 '17 at 10:09
  • `Modulo::calc(m)`, can be replaced with `m % r`, and you get the same (or better) binary. That is, compiler writers *also* know this trick, and they use it in generating code – Caleth Dec 08 '17 at 10:12
  • is this `ModuloHelper` corresponding to the original `Power2Modulo`? I'm a bit lost not sure how to replace the previous one with your code. Or would you mind give me an example at https://stackoverflow.com/questions/47784402/how-to-rewrite-this-code-without-using-boost ? – athos Dec 13 '17 at 06:21
  • You only use `ModuloHelper` in the implementation of `Modulo`, and it compile time selects between bitwise and (only applicable to modulo powers of two, "fast"), and repeated subtraction (always correct, "slow"). If you just use `m % r`, for compile time `r`, which all the uses of `Modulo` **must** be, a modern compiler does all that for you – Caleth Dec 13 '17 at 07:39
  • i still couldn't get it. could you give me a compilable, updated version of https://bitbucket.org/sergiu/random/src/tip/well.hpp?at=default&fileviewer=file-view-default that partially replaced its original Modulo implementation? – athos Dec 13 '17 at 07:51
  • @Caleth The implementations are different. As you can see it wasn't _doing_ a modulo operation, there was a precondition on the range of `m`. You should be comparing the compiler output of those, if you want to prove that /a/ compiler optimizes it the same (I concur it might be faster. The linked implementation was intended for Boost, though, and is many years old. Things are/were different in those constraints) – sehe Dec 15 '17 at 07:45