Размер входа - число разрядов: где прячется экспонента

Если ты объяснишь, почему перебор делителей до √N экспоненциален, напишешь деление длинного числа на короткое и знаешь, откуда в Python предел в 4300 цифр, - листай до «Теперь сам».

Как думаешь, зачем языку запрещать длинные числа

В Python 3.11 строка int("9" * 5000) завершается ошибкой:

ValueError: Exceeds the limit (4300 digits) for integer string conversion:
value has 5000 digits; use sys.set_int_max_str_digits() to increase the limit

Сложить два таких числа язык готов. Перемножить - тоже. А прочитать число из строки или напечатать его - нет, если цифр больше 4300. Прежде чем читать дальше, попробуй угадать: чем перевод в строку опаснее умножения?

На что это похоже

Представь номер телефона. Записать его - одиннадцать цифр, несколько секунд. Обзвонить подряд все номера от нуля до него - не хватит жизни. Длина записи и величина числа живут в разных мирах, и одиннадцать цифр - это сто миллиардов значений.

Алгоритм получает запись. Если его работа пропорциональна длине записи или её квадрату, он справится с любым номером. Если она пропорциональна величине - он обзванивает всех подряд.

Механизм: величина против длины

Число из n десятичных разрядов лежит между 10ⁿ⁻¹ и 10ⁿ. Обратно: число величины N занимает около log₁₀ N разрядов. Каждый новый разряд увеличивает величину вдесятеро, а длину - на единицу.

разрядов n      величина N         √N           сложение ~n    умножение ~n²
     6            10⁶              10³               6              36
    12            10¹²             10⁶              12             144
    20            10²⁰             10¹⁰             20             400
   617            10⁶¹⁷            10³⁰⁸           617         380 689

Последняя строка - число из 2048 бит, размер ключа RSA. Сложение и умножение в двух правых столбцах для него пустяк. Третий столбец - √N - число с тремястами нулями: столько шагов не сделает ничего.

Оценка «алгоритм делает √N шагов» выглядит лучше линейной. В разрядах она читается как 10^(n/2): на каждые две цифры работа растёт вдесятеро. Это экспонента, записанная так, что её не видно.

В разделе про динамическое программирование такая оценка уже встречалась: рюкзак решался за n · C, где C - вместимость, и называлось это псевдополиномом. Здесь причина та же: в оценке стоит величина числа, а не длина его записи.

Правило

Размер числового входа - число разрядов n ≈ log N. Алгоритм над числами полиномиален, если его цена - многочлен от n: сложение n, умножение и деление n² или быстрее. Оценка через величину - N, √N, N / 2 - экспоненциальна по n, сколько бы скромно она ни выглядела. Перевод числа между основаниями, ни одно из которых не степень другого, простым способом стоит n²: n делений длинного числа на короткое.

Разбор: перебор делителей и рост вдесятеро на две цифры

d = 2
prost = True
while d * d <= N:
    if N % d == 0:
        prost = False
        break
    d = d + 1
print(prost)

Число составное, если у него есть делитель от 2 до √N: из двух множителей хотя бы один не больше корня. Для простого N цикл доходит до конца. Берём самые большие простые с двумя, четырьмя, шестью, восемью и десятью цифрами:

N                 цифр     √N         шагов
97                  2        9            28
9 973               4       99           298
999 983             6      999         2 998
99 999 989          8    9 999        29 998
9 999 999 967      10   99 999       299 998

Три шага на делитель, делителей √N. Две цифры добавились - шагов вдесятеро больше. Продолжим таблицу в уме: двадцать цифр - 30 миллиардов шагов, сорок цифр - 3 · 10²⁰. Число из сорока цифр помещается в одну строку экрана, а его проверка этим способом не кончится никогда.

При этом каждое действие внутри цикла стоит копейки. Экспонента сидит не в цене шага, а в числе шагов.

Разбор: перевод в десятичную запись стоит квадрат

Компьютер хранит длинное число по основанию, удобному процессору, - степени двойки. Человеку нужны десятичные цифры. Перевод делается так же, как в школе: делим число на десять, остаток - очередная цифра, частное делим дальше. Нужно деление длинного на короткое:

def deli_korotkoe(a, k, B):
    out = [0] * len(a)
    ost = 0
    i = len(a) - 1
    while i >= 0:
        t = ost * B + a[i]
        out[i] = t // k
        ost = t % k
        i = i - 1
    while len(out) > 1 and out[len(out) - 1] == 0:
        out.pop()
    return [out, ost]

Деление идёт от старшего разряда к младшему, остаток приписывается слева к следующей цифре - тот же уголок, только делитель в одну «цифру». deli_korotkoe([4, 3, 2, 1], 7, 10) возвращает [[6, 7, 1], 2]: 1234 = 176 · 7 + 2. Один вызов - один проход по числу, Θ(n).

def v_desyatichnuyu(a, B):
    cifry = []
    while len(a) > 1 or a[0] > 0:
        r = deli_korotkoe(a, 10, B)
        a = r[0]
        cifry.append(str(r[1]))
    if len(cifry) == 0:
        return "0"
    cifry.reverse()
    return "".join(cifry)

Число из двух разрядов по основанию 256, [1, 1], - это 1 · 256 + 1; функция возвращает "257". Теперь замер: разряды по 15 бит, B = 32 768 (в CPython их по 30; здесь 15, чтобы промежуточные числа помещались в точное целое тренажёра), число из n разрядов, каждый равен наибольшему значению 32 767.

разрядов по 15 бит    десятичных цифр    шагов
        25                  113           10 347
        50                  226           37 621
       100                  452          142 947
       200                  904          556 819

Число вдвое длиннее - перевод почти вчетверо дороже. Каждая десятичная цифра стоит целого прохода по числу, цифр около 4,5 · n, проходов столько же. Это n².

Вот ответ на вопрос из начала. Умножение тоже квадратично, но чтобы заставить чужую программу перемножить два длинных числа, надо, чтобы она сама этого захотела. А прочитать число из входа она готова всегда: поле в JSON, параметр в адресе, значение в конфиге. Строка из миллиона цифр весит мегабайт и стоит серверу 10¹² действий. Уязвимость записана в общий реестр под номером CVE-2020-10735 (номер выдан в 2020 году, когда о ней сообщили); в сентябре 2022 года во все поддерживаемые версии Python добавили предел в 4300 цифр на перевод в обе стороны.

Что ломается без этого

Первое: «линейный» алгоритм по величине. Цикл for i in range(N) - это 10ⁿ витков. Он работает на тестах с N = 1000 и не работает на первом настоящем входе.

Второе: незаметный квадрат в выводе. Программа посчитала число из ста тысяч цифр быстрым алгоритмом и печатает его дольше, чем считала. На замере виновата строка print, и это не ошибка замера.

Третье: доверие к длине входа. Сервис, который превращает в число любую строку из цифр, отдаёт процессорное время тому, кто прислал строку подлиннее. Предел на длину ставят до разбора, а не после.

Четвёртое: перенос оценки между задачами. «Проверка простоты - это до корня» верно для чисел в девять цифр и бессмысленно для чисел в шестьсот. Для них нужен алгоритм с ценой в степенях n, и он есть - глава про простоту.

Зачем это в работе

Предел можно поднять: после import sys вызвать sys.set_int_max_str_digits(100000) или задать при запуске программы настройку PYTHONINTMAXSTRDIGITS. Делать это стоит только там, где длинные числа приходят из своих же расчётов, а не из сети. На шестнадцатеричную запись предел не действует: 16 - степень двойки, каждая цифра - ровно четыре бита, и перевод линеен. С версии 3.12 CPython переводит очень длинные числа алгоритмом быстрее квадрата, но предел по умолчанию оставлен.

Тот же вопрос задают к любому числовому алгоритму: цена названа от величины или от длины? Алгоритм Евклида делает число шагов, пропорциональное числу цифр, - он настоящий полиномиальный. Перебор делителей до корня - нет. На разнице между этими двумя ответами для одной пары задач - «простое ли число» и «на какие множители оно делится» - стоит шифрование с открытым ключом.

И к оценкам прошлых разделов. Счёт «одно действие на сложение» в них честен, потому что числа там - индексы и длины, и они помещаются в машинное слово. Как только величина числа сама становится входом, считать приходится разряды.

Теперь сам

1. Перебор делителей потратил 29 998 шагов на восьмизначное простое. Оцени число шагов для простого из четырнадцати цифр.
2. Переведи вручную список [2, 1] по основанию 256 в десятичное число.
3. Перевод в десятичную запись числа из 200 разрядов по 15 бит стоил 556 819 шагов. Оцени цену для 800 разрядов. Сколько примерно десятичных цифр получится?
4. Алгоритм над числом N делает N / 1000 шагов. Он полиномиален?