在C ++中将整数提高为正整数幂的正确方法是什么? [英] What is the correct way to raise an integer to a positive integer power in C++?

问题描述

我们知道对于各种原因，C ++中没有标准的整数幂函数.我正在使用较小的整数执行精确的算术运算，那么计算幂的正确方法是什么?

We know that for various reasons, there is no standard integer power function in C++. I'm performing exact arithmetic with rather small integers, what is the correct way to compute powers?

推荐答案

标准的快速求幂使用重复平方:

The standard, fast exponentiation uses repeated squaring:

uint_t power(uint_t base, uint_t exponent)
{
    uint_t result = 1;

    for (uint_t term = base; exponent != 0; term = term * term)
    {
        if (exponent % 2 != 0) { result *= term; }
        exponent /= 2;
    }

    return result;
}

步骤数是指数的对数.该算法可以简单地扩展到模幂.

The number of steps is logarithmic in the value of exponent. This algorithm can trivially be extended to modular exponentiation.

更新:这是该算法的修改版本，可减少一次乘法运算并更有效地处理一些琐碎的情况.此外，如果您知道指数永远不会为零，基数永远不会为零或一，那么您甚至可以删除初始检查:

Update: Here is a modified version of the algorithm that performs one less multiplication and handles a few trivial cases more efficiently. Moreover, if you know that the exponent is never zero and the base never zero or one, you could even remove the initial checks:

uint_t power_modified(uint_t base, uint_t exponent)
{
    if (exponent == 0) { return 1;    }
    if (base < 2)      { return base; }

    uint_t result = 1;

    for (uint_t term = base; ; term = term * term)
    { 
        if (exponent % 2 != 0) { result *= term; }
        exponent /= 2;
        if (exponent == 0)     { break; }
    }

    return result;
}

这篇关于在C ++中将整数提高为正整数幂的正确方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！