我已经实现了记忆所有计算权力的算法，然后在需要时使用它们。比如x^13等于(x^2)^2^2 * x^2 * x其中x^2^2是从表中取出来的而不是再计算一次。这基本上是@Pramod answer的实现(但在c#中)。 需要的乘法数是Ceil(Log n)

public static int Power(int base, int exp)
{
    int tab[] = new int[exp + 1];
    tab[0] = 1;
    tab[1] = base;
    return Power(base, exp, tab);
}

public static int Power(int base, int exp, int tab[])
    {
         if(exp == 0) return 1;
         if(exp == 1) return base;
         int i = 1;
         while(i < exp/2)
         {  
            if(tab[2 * i] <= 0)
                tab[2 * i] = tab[i] * tab[i];
            i = i << 1;
          }
    if(exp <=  i)
        return tab[i];
     else return tab[i] * Power(base, exp - i, tab);
}

迟到的人:

下面是一个尽可能处理y < 0的解。

It uses a result of intmax_t for maximum range. There is no provision for answers that do not fit in intmax_t. powjii(0, 0) --> 1 which is a common result for this case. pow(0,negative), another undefined result, returns INTMAX_MAX intmax_t powjii(int x, int y) { if (y < 0) { switch (x) { case 0: return INTMAX_MAX; case 1: return 1; case -1: return y % 2 ? -1 : 1; } return 0; } intmax_t z = 1; intmax_t base = x; for (;;) { if (y % 2) { z *= base; } y /= 2; if (y == 0) { break; } base *= base; } return z; }

这段代码使用了一个永久循环for(;;)，以避免在其他循环解决方案中常见的最终基数*=基数。这个乘法是1)不需要的，2)可能是int*int溢出，也就是UB。

我注意到gnu-GMP的标准指数平方算法有些奇怪:

我实现了两个几乎相同的函数——一个是幂模函数，使用最普通的二进制指数平方算法，

标签______2 ()

然后另一个基本相同的概念，但重新映射为每轮除以10，而不是除以2，

标签______10 ()

.

 ( time ( jot - 1456 9999999999 6671 | pvE0 | 

gawk -Mbe '
function ______10(_, __, ___, ____, _____, _______) {
      __ = +__
    ____ = (____+=_____=____^= \
           (_ %=___=+___)<_)+____++^____—

    while (__) {
        if (_______= __%____) {
            if (__==_______) {
                return (_^__ *_____) %___
            }
            __-=_______
            _____ = (_^_______*_____) %___
        }
        __/=____
        _ = _^____%___
    }
}
function ______2(_, __, ___, ____, _____) {
    __=+__
    ____+=____=_____^=(_%=___=+___)<_
    while (__) {
        if (__ %____) {
            if (__<____) {
                return (_*_____) %___
            }
            _____ = (_____*_) %___
            --__
        }
        __/=____
        _= (_*_) %___
    }
} 
BEGIN {
    OFMT = CONVFMT = "%.250g"

    __ = (___=_^= FS=OFS= "=")(_<_)

    _____ = __^(_=3)^--_ * ++_-(_+_)^_
    ______ = _^(_+_)-_ + _^!_

    _______ = int(______*_____)
    ________ = 10 ^ 5 + 1
    _________ = 8 ^ 4 * 2 - 1
}

GNU Awk 5.1.1, API: 3.1 (GNU MPFR 4.1.0, GNU MP 6.2.1)

.

($ + + NF = ______10(_ = ___美元,NR %________ +_________,_______*(_- 11))) ^ !___“

     out9: 48.4MiB 0:00:08 [6.02MiB/s] [6.02MiB/s] [ <=> ]
      in0: 15.6MiB 0:00:08 [1.95MiB/s] [1.95MiB/s] [ <=> ]
( jot - 1456 9999999999 6671 | pvE 0.1 in0 | gawk -Mbe ; )  

8.31s user 0.06s system 103% cpu 8.058 total
ffa16aa937b7beca66a173ccbf8e1e12  stdin

($ + + NF = ______ 2(_ = ___美元,NR %________ +_________,_______*(_- 11))) ^ !___“

     out9: 48.4MiB 0:00:12 [3.78MiB/s] [3.78MiB/s] [<=> ]
      in0: 15.6MiB 0:00:12 [1.22MiB/s] [1.22MiB/s] [ <=> ]
( jot - 1456 9999999999 6671 | pvE 0.1 in0 | gawk -Mbe ; )  

13.05s user 0.07s system 102% cpu 12.821 total
ffa16aa937b7beca66a173ccbf8e1e12  stdin

由于一些非常违反直觉和我不知道的原因，对于我投入的各种各样的输入，div-10变体几乎总是更快。这是两个哈希值之间的匹配，这让它真正令人困惑，尽管计算机显然没有内置在10进制的范例中。

我是否在代码/方法中遗漏了一些关键或明显的东西，可能会以令人困惑的方式歪曲结果?谢谢。

int pow( int base, int exponent)

{   // Does not work for negative exponents. (But that would be leaving the range of int) 
    if (exponent == 0) return 1;  // base case;
    int temp = pow(base, exponent/2);
    if (exponent % 2 == 0)
        return temp * temp; 
    else
        return (base * temp * temp);
}

更一般的解决方案考虑负指数

private static int pow(int base, int exponent) {

    int result = 1;
    if (exponent == 0)
        return result; // base case;

    if (exponent < 0)
        return 1 / pow(base, -exponent);
    int temp = pow(base, exponent / 2);
    if (exponent % 2 == 0)
        return temp * temp;
    else
        return (base * temp * temp);
}

如果你想得到一个整数的2的幂，最好使用shift选项:

Pow(2,5)可以替换为1<<5

这样效率更高。