Медленный Big Int выход в Python

Question

Есть ли способ улучшить производительность "str (bigint)" и "print bigint" в python?Печать больших целочисленных значений занимает много времени.Я попытался использовать следующую рекурсивную технику:

def p(x,n):
    if n < 10:
            sys.stdout.write(str(x))
            return
    n >>= 1
    l = 10**n
    k = x/l
    p(k,n)
    p(x-k*l,n)

n = количество цифр, x = bigint

Но метод завершается ошибкой в ​​определенных случаях, когда x в дополнительном вызове имеет начальные нули.Есть ли альтернатива или более быстрый метод.(Пожалуйста, не предлагайте использовать какой-либо внешний модуль или библиотеку).

Answer 1

Преобразование из целого числа Python в строку имеет пробег O (n ^ 2), где n - длина числа.Для достаточно больших чисел это будет медленно.Для числа из 1 000 001 цифр str () занимает примерно 24 секунды на моем компьютере.

Если вам действительно нужно преобразовать очень большие числа в строку, ваш рекурсивный алгоритм является хорошим подходом.

Должна работать следующая версия вашего рекурсивного кода:

def p(x,n=0):
    if n == 0:
        n = int(x.bit_length() * 0.3)
    if n < 100:
        return str(x)
    n >>= 1
    l = 10**n
    a,b = divmod(x, l)
    upper = p(a,n)
    lower = p(b,n).rjust(n, "0")
    return upper + lower

Автоматически оценивает количество цифр в выходных данных.Это примерно в 4 раза быстрее для числа из 1 000 001 цифр.

Если вам нужно быстрее, вам, вероятно, потребуется использовать внешнюю библиотеку.

Answer 2

Для интерактивных приложений встроенные функции print и str выполняются в мгновение ока.

>>> print(2435**356)
392312129667763499898262143039114894750417507355276682533585134425186395679473824899297157270033375504856169200419790241076407862555973647354250524748912846623242257527142883035360865888685267386832304026227703002862158054991819517588882346178140891206845776401970463656725623839442836540489638768126315244542314683938913576544051925370624663114138982037489687849052948878188837292688265616405774377520006375994949701519494522395226583576242344239113115827276205685762765108568669292303049637000429363186413856005994770187918867698591851295816517558832718248949393330804685089066399603091911285844172167548214009780037628890526044957760742395926235582458565322761344968885262239207421474370777496310304525709023682281880997037864251638836009263968398622163509788100571164918283951366862838187930843528788482813390723672536414889756154950781741921331767254375186751657589782510334001427152820459605953449036021467737998917512341953008677012880972708316862112445813219301272179609511447382276509319506771439679815804130595523836440825373857906867090741932138749478241373687043584739886123984717258259445661838205364797315487681003613101753488707273055848670365977127506840194115511621930636465549468994140625
>>> str(2435**356)
'392312129667763499898262143039114894750417507355276682533585134425186395679473824899297157270033375504856169200419790241076407862555973647354250524748912846623242257527142883035360865888685267386832304026227703002862158054991819517588882346178140891206845776401970463656725623839442836540489638768126315244542314683938913576544051925370624663114138982037489687849052948878188837292688265616405774377520006375994949701519494522395226583576242344239113115827276205685762765108568669292303049637000429363186413856005994770187918867698591851295816517558832718248949393330804685089066399603091911285844172167548214009780037628890526044957760742395926235582458565322761344968885262239207421474370777496310304525709023682281880997037864251638836009263968398622163509788100571164918283951366862838187930843528788482813390723672536414889756154950781741921331767254375186751657589782510334001427152820459605953449036021467737998917512341953008677012880972708316862112445813219301272179609511447382276509319506771439679815804130595523836440825373857906867090741932138749478241373687043584739886123984717258259445661838205364797315487681003613101753488707273055848670365977127506840194115511621930636465549468994140625'

Если, однако, вы печатаете большие целые числа (скажем, для стандартного вывода), чтобы их можно было прочитать (из стандартного ввода) другим процессом, и вы находите двоичные и десятичные операции, влияющие на общую производительность, вы можете посмотрите на Существует ли более быстрый способ преобразования произвольного большого целого числа в последовательность байтов с прямым порядком байтов? (хотя принятый ответ предполагает numpy, которая является внешней библиотекой, хотя есть и другие предложения).