Блог

Мне рекомендовали использовать gmpy для эффективного вычисления больших чисел. Раньше я просто использовал python, и мой скрипт работал день или два, а затем исчерпал память (не уверен, как это произошло, потому что использование памяти моей программы должно быть в основном постоянным.. может быть, утечка памяти?)

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

 mp_allocate< 545275904->545275904 >
Fatal Python error: mp_allocate failure

This application has requested the Runtime to terminate it in an unusual way. 
Please contact the application's support team for more information.
  

Кроме того, python выходит из строя, и Windows 7 выдает мне общий python.exe has stopped working диалог.

Этого не происходило при использовании стандартных целых чисел python. Теперь, когда я переключаюсь на gmpy, я получаю эту ошибку всего за несколько секунд до запуска моего скрипта. Я думал, что gmpy специализируется на работе с арифметикой больших чисел?

Для справки, вот пример программы, которая выдает ошибку:

 import gmpy2

p = gmpy2.xmpz(3000000000)
s = gmpy2.xmpz(2)
M = s**p

for x in range(p):
    s = (s * s) % M
  

У меня 10 гигабайт оперативной памяти, и без gmpy этот скрипт работал несколько дней без нехватки памяти (все еще не уверен, как это произошло, учитывая s , что на самом деле никогда не увеличивается..

У кого-нибудь есть идеи?

РЕДАКТИРОВАТЬ: Забыл упомянуть, что я использую Python 3.2

Отказ от ответственности: Я поддерживаю gmpy и gmpy2.

Я не смогу протестировать это до сегодняшнего вечера. Но пара комментариев и вопросов.

Вместо использования (s * s) % M используйте pow(s, 2, M) . Это должно быть быстрее.

Что произойдет, если вы используете gmpy2.mpz() вместо gmpy2.xmpz() ?

Используете ли вы 64-разрядную версию Python и gmpy2? (Я предполагаю, что это так, но я просто хочу подтвердить.)

Что касается range и xrange, в Python 3.x range заменил xrange .

Отредактируйте с дополнительной информацией.

Причиной сбоя было переполнение внутренних структур в 32-разрядной сборке. Использование 64-разрядной версии Python и gmpy или gmpy2 является правильным решением.

Функция unpack(x,n) аналогична функции split() для строки: она делит число на ряд из n-разрядных значений. Это эквивалентно, но намного быстрее, чем:

 def unpack(x,n):
r = []
m = 2**n
while x:
    x, temp = divmod(x,m)
    r.append(temp)
return r
  

Некоторая документация доступна через help(gmpy2.unpack) , но лучшая документация находится в моем списке дел.

Причина, по которой unpack() можно использовать для устранения операции%, та же, что и при добавлении цифр числа с основанием 10 для проверки делимости на 9. В этом случае unpack() создает p-разрядные числа, и мы делим на 2 ** p — 1 .

Вот некоторый тестовый код:

 import gmpy2
import time

def mersenne1(p):
    '''Primality test for Mersenne prime: 2**p -1.
    Uses native Python longs. Does not verify that p is prime.'''

    s = 4
    M = 2**p - 1
    for i in range(p-2):
        s = ((s*s)-2) % M
    return False if s else True

def mersenne2(p):
    '''Primality test for Mersenne prime: 2**p -1.
    Uses gmpy2.mpz. Does not verify that p is prime.'''

    s = gmpy2.mpz(4)
    M = gmpy2.mpz(2)**p - 1
    for i in range(p-2):
        s = ((s*s)-2) % M
    return False if s else True

def mersenne3(p):
    '''Primality test for Mersenne prime: 2**p -1.
    Uses gmpy2.mpz and no mod. Does not verify that p is prime.'''

    s = gmpy2.mpz(4)
    M = gmpy2.mpz(2)**p - 1
    for i in range(p-2):
        s = (s*s)
        s = sum(gmpy2.unpack(s, p))
        s = sum(gmpy2.unpack(s, p))
        if s < 2:
            s = M - 2   s
        else:
            s = s - 2
    return False if s else True

if __name__ == "__main__":
    p = 44497

    start = time.time()
    result1 = mersenne1(p)
    print("Elapsed time: {:6.3f}".format(time.time() - start))

    start = time.time()
    result2 = mersenne2(p)
    print("Elapsed time: {:6.3f}".format(time.time() - start))

    start = time.time()
    result3 = mersenne3(p)
    print("Elapsed time: {:6.3f}".format(time.time() - start))

    if result1 == result2 == result3:
        print("All three tests are equal!")
    else:
        print("Oops, something has gone wrong.")
  

И некоторое время выполнения…

 C:x64Python32>python.exe mersenne.py
Elapsed time: 163.683
Elapsed time: 12.782
Elapsed time:  3.630
All three tests are equal!