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

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

Ответ 1

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

Ответ 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

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

Ответ 3

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

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

Ответ 4

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

Ответ 5

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

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

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

Ответ 6

Реализовать 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

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