Как я могу преобразовать абсолютно массивное число в строку за разумное время?

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

prime = 2**74207281 - 1

Это занимает около полутора секунд, и все работает отлично. Операции довольно быстрые. Деление его на 10 (без десятичных знаков) для смещения цифр происходит быстро. Однако str(prime) занимает очень много времени. Я повторно выполнил str следующим образом и обнаружил, что он обрабатывает около ста цифр в секунду.

while prime > 0:
    strprime += str(prime%10)
    prime //= 10

Есть ли способ сделать это более эффективно? Я делаю это на Python. Должен ли я даже попробовать это с помощью Python, или есть лучший инструмент для этого?

Ответ 1

Повторяющаяся конкатенация строк, как известно, неэффективна, поскольку строки Python неизменяемы. Я бы пошел за

strprime = str(prime)

В моих тестах это всегда самое быстрое решение. Вот моя маленькая тестовая программа:

import decimal

def f1(x):
    ''' Definition by OP '''
    strprime = ""
    while x > 0:
        strprime += str(x%10)
        x //= 10
    return strprime

def digits(x):
    while x > 0:
        yield x % 10
        x //= 10

def f2(x):
    ''' Using string.join() to avoid repeated string concatenation '''
    return "".join((chr(48 + d) for d in digits(x)))

def f3(x):
    ''' Plain str() '''
    return str(x)

def f4(x):
    ''' Using Decimal class'''
    return decimal.Decimal(x).to_eng_string()

x = 2**100

if __name__ == '__main__':
    import timeit
    for i in range(1,5):
        funcName = "f" + str(i)
        print(funcName+ ": " + str(timeit.timeit(funcName + "(x)", setup="from __main__ import " + funcName + ", x")))

Для меня это печатает (используя Python 2.7.10):

f1: 15.3430171013
f2: 20.8928260803
f3: 0.310356140137
f4: 2.80087995529

Ответ 2

В алгоритме Python integer to string используется упрощенный алгоритм с запуском O (n ** 2). Поскольку длина числа удваивается, время преобразования увеличивается в четыре раза.

Некоторые простые тесты на моем компьютере показывают увеличение времени выполнения:

$ time py35 -c "n=str(2**1000000)"
user    0m1.808s
$ time py35 -c "n=str(2**2000000)"
user    0m7.128s
$ time py35 -c "n=str(2**4000000)"
user    0m28.444s
$ time py35 -c "n=str(2**8000000)"
user    1m54.164s

Так как фактический показатель примерно в 10 раз больше моего последнего тестового значения, он должен занимать около 100 раз дольше. Или чуть более 3 часов.

Можно ли это сделать быстрее? Да. Есть несколько методов, которые быстрее.

Метод 1

Быстрее разделить очень большое число на 10 единиц на два примерно одинаковых, но меньших числа. Процесс повторяется до тех пор, пока номера не будут относительно небольшими. Затем на каждом номере используется str(), а начальные нули используются для заполнения результата до той же длины, что и последняя мощность 10. Затем строки объединяются для формирования конечного результата. Этот метод используется библиотекой mpmath, и документация подразумевает, что она должна быть примерно в 3 раза быстрее.

Метод 2

Целочисленные числа Python хранятся в двоичном формате. Двоичный файл отлично подходит для вычислений, но двоично-десятичное преобразование является узким местом. Можно определить свой собственный целочисленный тип, который хранит значение в блоках из десятичных цифр (или некоторых аналогичных значений) из 100 знаков. Операции (возведение в степень, умножение, деление) будут медленнее, но преобразование в строку будет очень быстрым.

Много лет назад я реализовал такой класс и использовал эффективные алгоритмы для умножения и деления. Код больше не доступен в Интернете, но я нашел резервную копию, которую я тестировал. Время работы сократилось до ~ 14 секунд.

Обновление

Я обновил приведенный выше код DecInt и теперь доступен в https://github.com/casevh/DecInt.

Если используется собственный целочисленный тип Python, общее время работы на моем компьютере составляет менее 14 секунд. Если вместо этого используется тип gmpy2 integer, время работы ~ 3,5 секунды.

$ py35 DecInt.py
Calculating 2^74207281
Exponentiation time: 3.236
Conversion to decimal format: 0.304
Total elapsed time: 3.540
Length of result: 22338618 digits

Метод 3

Я поддерживаю библиотеку gmpy2, которая обеспечивает легкий доступ к библиотеке GMP для быстрой целочисленной арифметики. GMP реализует метод 1 в высоко оптимизированном C и сборочном коде и вычисляет простое число и строковое представление в ~ 5 секунд.

Метод 4

Модуль decimal в Python сохраняет значения в виде десятичных цифр. Недавние версии Python 3 включают реализацию C десятичной библиотеки, которая намного быстрее, чем реализация pure-Python с Python 2. Реализация C выполняется всего за 3 секунды на моем компьютере.

from decimal import *
getcontext().prec = 23000000
getcontext().Emin = -999999999
getcontext().Emax = 999999999
x=Decimal(2)**74207281 - 1
s=str(x)

Ответ 3

Взял около 32 секунд для вывода файла с помощью WinGhci (язык Haskell):

import System.IO

main = writeFile "prime.txt" (show (2^74207281 - 1))

Файл был 21 мегабайт; последние четыре цифры, 6351.

Ответ 4

Существует gmp, многоадресная арифметическая библиотека GNU. Он особенно разработан при быстром обращении с огромными числами.