49729 / 223 = 223.044(...) ?

oxygenium79 napisał(a):

Wiadomo, że spowalnia, już nie Operujesz na 64 bitowych rejestrach, tylko na bigintach, które generalnie są stringami.

Ale Pyton nie spowalnia? Dla C++ granicą jest liczba 18446744073709551557, potem musiałem użyć GMP co strasznie spowolniło.

Python jeszcze bardziej spowolni, zwłaszcza, że powyżej long max nie będzie tak łatwo użyć jit, dlatego dla takich liczb juz się stosuje inne algorytmy.
Np:
Fermat(wrażliwy na pseudo pierwsze):

def is_prime_fermat(n):
    if n == 2:
        return True
    if not n & 1:
        return False
    return pow(2, n-1, n) == 1

Miller - Rabin:

from random import randrange
def is_prime_mr(n, k=20):
    if n == 2:
        return True
    if not n & 1:
        return False

    def check(a, s, d, n):
        x = pow(a, d, n)
        if x == 1:
            return True
        for i in xrange(s - 1):
            if x == n - 1:
                return True
            x = pow(x, 2, n)
        return x == n - 1

    s = 0
    d = n - 1

    while d % 2 == 0:
        d >>= 1
        s += 1

Jeszcze lepiej Miller - Rabin jest zaimplementowany w GMP - ma lepszy algorytm mnożenia. W Pythonie Karatsuba O(n^1.37), a w GMP mnożenie jest O(n).

OK, ale probabilistyczne algorytmy mnie nie interesują. Mnie interesuje dokładne sprawdzenie.
No i na dziś napotykam na dwie ściany:
W C++ ścianą jest liczba 18446744073709551557.
W Pythonie ścianą jest powolność działania.
C++ z GMP jest strasznie skomplikowany, ale jednak szybszy od Pythona.
Ja natomiast szukam rozwiązania, które by było tak proste jak Python, a jednocześnie tak szybkie jak C++ i bez górnego ograniczenia.
Oczywiście na tyle, na ile komputer domowy pozwala (i5, Windows 10).
Na razie udało mi się:
C++: 18446744073709551557 w 19 s
C++ z GMP: 18446744073709551557 w 83s
Python: 18446744073709551557 w 17 minut
C++ z GMP: 1000000000000000000000177 w 57 godzin
Python: 9000000000000000000091 w 6 godzin.

Po pierwsze, ustalając współczynnik k w Miller - Rabin (MR) algorytmie, możemy obniżyć prawdopodobieństwo błędu do, praktycznie pomijalnych rozmiarów (4 ^ -k). W każdym problemie na projecteuler, nawet w długich pętlach (tym bardziej w długich pętlach ! ;-D) stosowałem MR i działało.
Następnie, dla bigintów nigdy nie Uzyskasz wydajnego algorytmu deterministycznego, bo, jeśli do słowa maszynowego, złożonośc jest O(sqrt(n)), to powyżej już trzeba liczyć (w bitach) O(mnożenie(n) * n).
Są opakowania na GMP w C++, jedno nawet udało mi się stworzyć:) https://github.com/lion137/GMP_C