为什么按位运算比常规方法快?

如果 a , b 和 c 如果是整数,则可以通过 binary exponentiation 和约化模 C 在每个步骤中,包括第一步(即减少 A. 模 C 在你开始之前)。这是什么 the implementation of long_pow() 的确如此。这个函数有200多行代码,因为它必须处理引用计数,它处理负指数和一大堆特殊情况。

不过,该算法的核心思想相当简单。假设我们想要计算 a ** b 对于正整数 A. 和 B 和 B 有二进制数字 b_i .然后我们就可以写了 B 像

b = b_0 + b1 * 2 + b2 * 2**2 + ... + b_k ** 2**k

ans a**b 像

a ** b = a**b0 * (a**2)**b1 * (a**2**2)**b2 * ... * (a**2**k)**b_k

本产品中的每一个因素都是 (a**2**i)**b_i 如果 b_i 是零,我们可以忽略这个因子。如果 b_i 等于1,系数等于 a**2**i ,并且这些功率都可以计算出来 i 反复摆平 A. .总的来说,我们需要平方和乘法 k 时报,哪里 K 是的二进制位数 B .

如上所述 pow(a, b, c) 我们可以约化模 C 在每一步中,无论是平方还是相乘。

您可以考虑以下两个计算实现 (x ** y) % z 迅速地

在Python中:

def pow_mod(x, y, z):
    "Calculate (x ** y) % z efficiently."
    number = 1
    while y:
        if y & 1:
            number = number * x % z
        y >>= 1
        x = x * x % z
    return number

在C中:

#include <stdio.h>

unsigned long pow_mod(unsigned short x, unsigned long y, unsigned short z)
{
    unsigned long number = 1;
    while (y)
    {
        if (y & 1)
            number = number * x % z;
        y >>= 1;
        x = (unsigned long)x * x % z;
    }
    return number;
}

int main()
{
    printf("%d\n", pow_mod(63437, 3935969939, 20628));
    return 0;
}

我不懂python,但如果你需要快速幂,你可以通过平方来使用幂运算:

http://en.wikipedia.org/wiki/Exponentiation_by_squaring

这是一种简单的递归方法,使用了指数的交换性质。

第1426行 this file 显示了实现数学的Python代码。pow,但基本上可以归结为调用标准C库,该库可能具有该函数的高度优化版本。

Python在进行密集的数字运算时可能非常慢,但是 Psyco 它可以给你一个相当快的提速,但不如调用标准库的C代码好。

Python对一般情况使用C数学库,对一些概念(如无穷大)使用自己的逻辑。

在Python中实现pow(x,n)

def myPow(x, n):
        p = 1
        if n<0:
            x = 1/x
            n = abs(n)

        # Exponentiation by Squaring

        while n:
            if n%2:
                p*= x
            x*=x
            n//=2
        return p

在Python中实现pow(x,n,m)

def myPow(x,n,m):
            p = 1
            if n<0:
                x = 1/x
                n = abs(n)
            while n:
                if n%2:
                    p*= x%m
                x*=x%m
                n//=2
            return p

看看这个 link 为了解释