Попытка вычислить большие числа в Python с помощью gmpy.Питон продолжает сбой? - PullRequest
Новая
       39

Попытка вычислить большие числа в Python с помощью gmpy.Питон продолжает сбой?

5 голосов
/ 04 октября 2011

Мне порекомендовали использовать 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.

Thisне происходило с использованием стандартных чисел 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

1 Ответ

6 голосов
/ 04 октября 2011

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

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

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

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

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

Что касается диапазона против xrange, в Python 3.x диапазон заменил 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 () может использоваться для исключения операции%, аналогична добавлению цифр числа base-10 для проверки делимости на 9. В этом случае unpack () создает числа p-битов и мы делим на 2 ** р - 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:\x64\Python32>python.exe mersenne.py
Elapsed time: 163.683
Elapsed time: 12.782
Elapsed time:  3.630
All three tests are equal!
...