webentwicklung-frage-antwort-db.com.de

Wie hat Python die eingebaute Funktion pow () implementiert?

Ich muss ein Programm schreiben, um a**b % c zu berechnen, wobei b und c beide sehr große Zahlen sind. Wenn ich nur a**b % c benutze, ist es wirklich langsam. Dann habe ich festgestellt, dass die eingebaute Funktion pow() dies sehr schnell tun kann, indem Sie pow(a, b, c) aufrufen.
Ich bin neugierig, wie Python das implementiert? Oder wo finde ich die Quellcodedatei, die diese Funktion implementiert?

42
wong2

Wenn a, b und c ganze Zahlen sind, kann die Implementierung durch binary exponentiation effizienter gemacht werden und modulo c in jedem Schritt, einschließlich des ersten, reduziert werden (d. H. a modulo c). Dies ist, was die Implementierung von long_pow() tatsächlich tut.

36
Sven Marnach

Sie können die folgenden zwei Implementierungen für die schnelle Berechnung von (x ** y) % z in Betracht ziehen.

In 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

In 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;
}
35
Noctis Skytower

Pow (x, n) in Python implementieren

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) in Python implementieren

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

Überprüfen Sie diesen Link zur Erklärung 

0
Akshay Nair

Python verwendet C-Mathematikbibliotheken für allgemeine Fälle und für einige seiner Konzepte (z. B. Infinity) eine eigene Logik.

0
cmaynard

Zeile 1426 von dieser Datei zeigt den Python-Code, der math.pow implementiert, aber im Grunde läuft es darauf hinaus, die Standard-C-Bibliothek aufzurufen, die wahrscheinlich eine stark optimierte Version dieser Funktion hat.

Python kann für intensives Zahlen-Crunching ziemlich langsam sein, aber Psyco kann Ihnen einen Geschwindigkeitsschub verleihen, es ist jedoch nicht so gut wie C-Code, der die Standard-Library aufruft.

0

Ich weiß nichts über Python, aber wenn Sie schnelle Kräfte brauchen, können Sie Potenzierung durch Quadrieren verwenden:

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

Es ist eine einfache rekursive Methode, die die Eigenschaft von Exponenten verwendet.

0
Jonno_FTW