Как Python реализовал встроенную функцию pow ()?

Question

Мне нужно написать программу для вычисления a**b % c, где b и c - оба очень больших числа. Если я просто использую a**b % c, это действительно медленно. Затем я обнаружил, что встроенная функция pow() может сделать это очень быстро, вызвав pow(a, b, c).
Мне любопытно узнать, как Python реализует это? Или где я могу найти файл исходного кода, который реализует эту функцию?

Answer 1

Если a, b и c являются целыми числами, реализацию можно сделать более эффективной путем двоичного возведения в степень и уменьшения по модулю c на каждом шаге, включая первый (т.е.уменьшение a по модулю c еще до начала).Вот что действительно делает реализация long_pow().

Answer 2

Вы можете рассмотреть следующие две реализации для быстрого вычисления (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

В С:

#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;
}

Answer 3

Реализация pow (x, n) в Python

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

Реализация pow (x, n, m) в Python

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

Оформить заказ на эту ссылку для объяснения

Answer 4

Я не знаю насчет питона, но если вам нужны быстрые силы, вы можете использовать возведение в степень, возводя в квадрат:

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

Это простой рекурсивный метод, использующий коммутативное свойство экспонент.

Answer 5

Python использует математические библиотеки C для общих случаев и собственную логику для некоторых своих понятий (например, бесконечность).

Answer 6

Строка 1426 из этого файла показывает код Python, который реализует math.pow, но в основном он сводится к его вызову стандартной библиотеки C, которая, вероятно, имеет высокооптимизированную версию этой функции.

Python может быть довольно медленным для интенсивного перебора чисел, но Psyco может дать вам прирост скорости, хотя он не будет так же хорош, как код C, вызывающий стандартную библиотеку.