n-methods/src/exponentiation.cpp at main · pawanmsr/n-methods · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <exponentiation.hpp>

#include <cstdint>

namespace nm {
    /* T is expected to be any integer data type */
    template <typename T>
    T bin_exp(T x, T y) {
        if (y<=0) return 1;

        T z = bin_exp<T>(x, y/2);
        return y%2 ? z*z*x : z*z;
    }

    template <typename T>
    T bin_exp_iterative(T x, T y) {
        if (y<=0) return 1;

        T res = 1;
        while (y) {
            if (y & 1) res *= x;
            x = x*x;
            y >>= 1;
        }
        return res;
    }
} // binary exponentiation

template std::int32_t nm::bin_exp<std::int32_t>(std::int32_t, std::int32_t);
template std::int64_t nm::bin_exp<std::int64_t>(std::int64_t, std::int64_t);

template std::int32_t nm::bin_exp_iterative<std::int32_t>(std::int32_t, std::int32_t);
template std::int64_t nm::bin_exp_iterative<std::int64_t>(std::int64_t, std::int64_t);