1

モジュロを計算するためのこの再帰関数があります。

uint64_t fast_power(uint64_t k, uint64_t n, uint32_t m) {

        uint64_t sum;
        if (n == 0) {
            return 1;
        }

        if ((n % 2) == 0) {
            sum = fast_power(k, (n / 2), m) * fast_power(k, (n / 2), m);

            return MOD(sum, m);
        } else {
            sum = k * (fast_power(k, (n - 1), m));
            return MOD(sum, m);
        }

}

同じ関数で繰り返しを使用するにはどうすればよいですか? これは私がこれまでに持っているものです:

uint64_t iter_power(uint64_t k, uint64_t n, uint32_t m) {

    uint64_t arr[n - 1];

    uint64_t num;

    for (int i = 1; i < n; i++) {

        num = power(k, i);

        arr[num] = MOD(arr[num], m);

    }
    return arr[num];

}
4

1 に答える 1

2

アルゴリズムは二乗による累乗です。方程式は次のとおりです。

iter_pow(k, n) = iter_pow(k * k, n / 2) * k   if n % 2 == 1
iter_pow(k, n) = iter_pow(k * k, n / 2)       if n % 2 == 0

これにより、次の反復コードが生成されます。

uint64_t iter_power(uint64_t k, uint64_t n, uint32_t m) {
    uint64_t result = 1;
    while (n) {
        if (n % 2) result = MOD(result * k, m);
        n /= 2;
        k = MOD(k * k, m);
    }
    return result;
}
于 2013-11-11T21:00:54.910 に答える