Число как список разрядов: сложение стоит n, а не 1

Если ты напишешь сложение двух чисел, заданных списками разрядов, объяснишь, почему перенос не бывает больше единицы и почему n сложений растущих чисел стоят n², - листай до «Теперь сам».

Как думаешь, сколько стоит тысяча шестьсот сложений

Числа Фибоначчи: каждое следующее - сумма двух предыдущих. 0, 1, 1, 2, 3, 5, 8, 13, … Программа из четырёх строк в цикле делает одно сложение на виток:

a = 0
b = 1
i = 0
while i < n:
    c = a + b
    a = b
    b = c
    i = i + 1
print(a)

При n = 100 витков сто, при n = 1600 - тысяча шестьсот. Прежде чем читать дальше, ответь себе: во сколько раз второй запуск дороже первого? В шестнадцать? Ответ - в двести двадцать три, и в разборе ниже видно, откуда он берётся.

Сначала о том, почему эта программа на тренажёре вообще не доходит до n = 100. Она останавливается на 78-м витке с ошибкой «целое число вышло за предел точного счёта». Тренажёр хранит целое так же, как JavaScript: точно до 2⁵³ = 9 007 199 254 740 992. Граница ниже 64 бит, потому что число там хранится как дробное двойной точности, и под значащие разряды в нём отведено 53 бита из 64; как устроены дробные числа - в последней главе раздела. Число Фибоначчи с номером 78 равно 8 944 394 323 791 464 и ещё помещается, следующее - 14 472 334 024 676 221 - уже нет.

Настоящий Python не остановился бы. Он молча перешёл бы на длинные числа - и именно поэтому легко не заметить, что строка c = a + b перестала стоить одно действие.

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

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

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

Механизм: список разрядов и перенос

Длинное число хранят списком цифр, младшая цифра первой. Число 428 - это [8, 2, 4]. Порядок перевёрнут намеренно: сложение идёт от младших разрядов, и результат может вырасти на разряд, а дописать элемент в конец списка дёшево.

  428 + 795                     разряд   цифры     сумма с переносом   пишем   перенос
                                  0      8 + 5          13               3        1
  a = [8, 2, 4]                   1      2 + 9 + 1      12               2        1
  b = [5, 9, 7]                   2      4 + 7 + 1      12               2        1
  c = [3, 2, 2, 1]  → 1223        3      перенос         1               1        0

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

Перенос не бывает больше единицы. Самый тяжёлый случай: 9 + 9 и перенос 1 дают 19 - пишем 9, переносим 1. Чтобы перенести двойку, сумма должна дойти до 20, а ей неоткуда. Поэтому сумма двух чисел по n разрядов занимает не больше n + 1 разряда.

Десятка здесь не обязательна. Основание B - сколько значений у одного разряда; разрядом может быть число от 0 до 999 999, и тогда B = 1 000 000, а список в шесть раз короче: число 1 234 567 - это [234567, 1]. Формулы те же: остаток и частное берутся от деления на B.

Правило

Число, которое не помещается в машинное слово, хранится списком разрядов по основанию B, младший разряд первым. Сложение и вычитание двух чисел по n разрядов стоят Θ(n) действий над разрядами, и результат занимает не больше n + 1 разряда. Размер числа N как входа алгоритма - число его разрядов, то есть около log N, а не само N. Алгоритм, который делает k сложений над растущими числами, стоит не k, а сумму длин этих чисел.

Буква Θ - из раздела про анализ: «растёт как», с точностью до постоянного множителя.

Разбор: программа сложения и её цена

def slozhi(a, b, B):
    out = []
    perenos = 0
    i = 0
    while i < len(a) or i < len(b) or perenos > 0:
        s = perenos
        if i < len(a):
            s = s + a[i]
        if i < len(b):
            s = s + b[i]
        out.append(s % B)
        perenos = s // B
        i = i + 1
    return out

Условие цикла держит три случая сразу: разряды остались только у a, только у b, или кончились у обоих, но остался перенос. slozhi([8, 2, 4], [5, 9, 7], 10) возвращает [3, 2, 2, 1], а slozhi([9, 9, 9], [1], 10) - [0, 0, 0, 1]: перенос прошёл через все три девятки.

Цена на тренажёре, оба числа по n разрядов, B = 10:

n          шагов
10           106
100          916
1 000      9 016

Девять шагов на разряд - по одному на каждую строку цикла - плюс шестнадцать на обвязку: 9n + 16. Число 9 зависит от того, как написан цикл, и ничего не значит. Значит то, что n стоит в первой степени.

Разбор: почему Фибоначчи стоит n², а не n

Заменим в программе из начала урока a + b на slozhi(a, b, 10), а начальные ноль и единицу - на [0] и [1]. Теперь она считает любое число Фибоначчи; в шаги входит всё - и цикл, и вызовы. Ответ - список разрядов, его длина и стоит во втором столбце.

n        разрядов в ответе    шагов, B = 10    шагов, B = 1 000 000
100             21                 10 893              3 081
200             42                 40 585              9 228
400             84                155 904             30 834
800            167                612 740            111 814
1 600          335              2 429 220            424 236

Витков вдвое больше - шагов вчетверо больше. Это квадрат. Причина - во втором столбце: число разрядов растёт вместе с n, около 0,209 разряда на номер. На витке с номером i складываются числа длиной около 0,209 · i, и это сложение стоит столько же. Сумма длин по всем виткам - сумма чисел от 1 до n с множителем, то есть около 0,209 · n² / 2. Та же арифметическая прогрессия, что у сортировки вставками.

Ответ на вопрос из начала: 2 429 220 / 10 893 = 223. Шестнадцать раз по шестнадцать было бы 256; недобор - постоянная обвязка каждого витка, которая на маленьких числах ещё заметна.

Последний столбец - то же самое по основанию миллион. Числа в шесть раз короче, и шагов меньше: в три с половиной раза в первой строке и в 5,7 раза в последней - чем длиннее числа, тем меньше заметна постоянная обвязка каждого витка. Рост идёт к тому же: удвоение n увеличивает цену в 3,6 и в 3,8 раза на последних строках. Большое основание уменьшает множитель и не меняет порядок. Настоящие библиотеки поэтому берут основание размером с машинное слово или чуть меньше: в CPython - основной реализации Python, той, что ставится с python.org, - разряд длинного числа занимает 30 бит, B = 2³⁰.

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

Первое: потерянный старший перенос. Цикл while i < len(a) без проверки переноса на 999 + 1 возвращает [0, 0, 0] - ноль вместо тысячи. На числах, сумма которых не выросла на разряд, ошибки нет, поэтому тест 428 + 571 = 999 её не ловит, а 428 + 795 = 1223 ловит: вернётся [3, 2, 2].

Второе: молчаливая потеря точности. JavaScript и любой язык, где число - дробное двойной точности, за 2⁵³ не падает, а округляет: 123456789 · 987654321 даёт 121932631112635260 вместо …269. Ответ похож на правильный. Тренажёр в этом месте останавливается с ошибкой, и это лучшее из возможного.

Третье: переполнение в языках с фиксированным размером. В C сумма двух больших чисел типа int на практике заворачивается через край и становится отрицательной: старший бит числа служит знаком, и перенос в него превращает большое положительное в отрицательное (а по стандарту языка результат не определён вовсе); программа продолжает работать с мусором.

Четвёртое: старшая цифра первой. Со списком [4, 2, 8] сложение приходится вести с конца, а новый старший разряд - вставлять в начало, что само стоит n действий.

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

Идентификаторы. Номер записи в базе - 64-битное целое, и пока он меньше 2⁵³, всё работает. Потом сервис отдаёт его в JSON, браузер читает число как дробное, и два разных номера превращаются в один. Крупные сервисы после такой истории стали присылать номер ещё и строкой.

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

Криптография. Ключ RSA - число из 2048 бит, шестьсот с лишним десятичных цифр. Каждое действие над ним - цикл по разрядам, и вся стойкость строится на том, что одни действия над такими числами стоят n или n², а другие - больше, чем есть времени у вселенной. Об этом главы дальше.

Оценка чужого кода. Строка x = x + y в цикле на Python выглядит как одно действие и становится линейной по длине числа, как только x перерастает машинное слово. Квадрат в такой программе не виден в коде - он виден только на замере.

Теперь сам

1. Сложи по разрядам [7, 5, 9] и [6, 4], основание 10. Запиши список-ответ и число, которое он обозначает.
2. По формуле из разбора: сколько шагов тренажёра стоит одно сложение двух чисел по 500 разрядов?
3. Число Фибоначчи с номером 1600 стоило 2 429 220 шагов. Оцени цену для номера 3200.