Конспект: длинные числа и цена арифметики

Понятия

Машинное слово - число фиксированного размера, над которым процессор работает одной командой. 64 бита - около девятнадцати десятичных цифр.

Длинное число - список разрядов по основанию B, младший разряд первым. 428 при B = 10 - это [8, 2, 4].

Основание B - сколько значений у одного разряда. В CPython B = 2³⁰.

Перенос - то, что не поместилось в разряд и уходит в следующий.

Размер числового входа - число разрядов n ≈ log N, а не величина N.

Что унести

ДЕЙСТВИЕ НАД ЧИСЛАМИ ИЗ n РАЗРЯДОВ             ЦЕНА            ЗАМЕР НА ТРЕНАЖЁРЕ, B = 10
сложение, вычитание                             n               9n + 16 шагов
умножение на короткое, деление на короткое      n
умножение столбиком                             n²              5n² + 8n + 9 шагов
деление уголком                                 n²
перевод в десятичную запись делением            n²              556 819 на 904 цифры
Карацуба (раздел 13)                            n^1.585
через преобразование Фурье (раздел 13)          n · log n
перебор делителей до √N                         10^(n/2)        299 998 на 10 цифр

Растущие числа меняют порядок алгоритма. n сложений чисел Фибоначчи - это n², потому что длина числа растёт как 0,209 · n.

Основание меняет множитель, а не порядок. В шесть раз короче список - в пять-шесть раз меньше шагов, рост тот же.

Счёт умножений честен только при числах одной длины. 3⁸⁰⁰ целиком: 800 умножений на 3 - 618 293 шага, 12 умножений через квадраты - 283 942. Выигрыш в 2,2 раза, порядок один и тот же.

СЛОЖЕНИЕ, один разряд            УМНОЖЕНИЕ, одна пара разрядов
s = a[i] + b[i] + perenos        p = out[i + j] + a[i] * b[j] + perenos
out[i] = s % B                   out[i + j] = p % B
perenos = s // B                 perenos = p // B
перенос ≤ 1                      p ≤ B² − 1: нужно слово вдвое шире разряда
результат: до n + 1 разряда      результат: n + m или n + m − 1 разряд

ВЕЛИЧИНА ПРОТИВ ДЛИНЫ
разрядов      √N            шагов перебора делителей
    6         10³                  2 998
   10         10⁵                299 998
   20         10¹⁰          30 миллиардов
  617         10³⁰⁸         не кончится          ← ключ RSA в 2048 бит

Границы. Тренажёр и JavaScript точны до 2⁵³ ≈ 9 · 10¹⁵. 64-битное целое - до 2⁶³ ≈ 9,2 · 10¹⁸. CPython умножает столбиком до 70 разрядов по 30 бит (около 630 десятичных цифр), дальше Карацуба. Перевод целого в строку и обратно в Python ограничен 4300 цифрами; снимается sys.set_int_max_str_digits.

Ловушки джокера

Потерянный старший перенос. Цикл до конца разрядов без проверки переноса: 999 + 1 даёт [0, 0, 0]. Тест без роста на разряд ошибку не ловит.

Потерянный перенос прохода при умножении. Без out[i + len(b)] = perenos верно считается 12 · 13 и неверно 99 · 99.

Неснятые старшие нули. [6, 5, 1, 0] и [6, 5, 1] - одно число разной длины; сравнение по длине врёт.

Разряд без нулей при печати. При основании 1000 разряд 7 - это цифры 007. Без дополнения нулями печатается число короче настоящего. Старший разряд - единственный, который печатают как есть.

Слишком большое основание. B = 10⁹: произведение разрядов доходит до 10¹⁸ - за пределом точности JavaScript и впритык к 64 битам.

Молчаливое округление. За 2⁵³ дробное двойной точности не падает, а округляет: 123456789 · 987654321 оканчивается на …260 вместо …269.

«Всего log n умножений». Оценка без длины множителей ничего не говорит о цене.

«Всего √N шагов». В разрядах это экспонента: каждые две цифры - вдесятеро.

Число из чужого входа. Строка из миллиона цифр весит мегабайт и стоит 10¹² действий при переводе. Длину проверяют до разбора.

Куда это ведёт

Длина числа - главный враг этой главы: она растёт от каждого умножения и тянет цену за собой. В следующей главе её останавливают остатком по модулю: после каждого действия число возвращается в пределы одного и того же размера, и счёт «сколько умножений» снова становится счётом цены. На этом стоят алгоритм Евклида, обратный элементРазбирается в разделе 18, глава «Модульная арифметика, НОД и обратный элемент»: Расширенный Евклид и обратный элемент: как делить по модулю и быстрая степень - три инструмента, из которых потом собираются проверка простоты и шифрование.