Умножение столбиком: квадрат, который прячется за звёздочкой

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

Как думаешь, во сколько раз выиграет быстрая степень

Нужно число 3⁸⁰⁰ целиком, все 382 цифры. Первый способ: начать с единицы и восемьсот раз умножить на 3. Второй - быстрое возведение в степень из раздела про рекуррентности: возводить в квадрат и домножать, всего 12 умножений длинного числа на длинное.

Восемьсот умножений против двенадцати. Прежде чем читать дальше, ответь себе: во сколько раз второй способ дешевле на тренажёре - в шестьдесят шесть, как умножений? В десять? Числа хранятся списками разрядов, как в прошлом уроке.

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

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

Школьный столбик устроен так же: каждая цифра нижнего числа встречается с каждой цифрой верхнего. Карацуба из раздела «Разделяй и властвуй» показал, что правило «каждый с каждым» не обязательно, но для этого умножение пришлось устроить иначе.

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

Числа хранятся младшим разрядом вперёд: a[i] - цифра с весом Bⁱ. Произведение цифр a[i] · b[j] имеет вес Bⁱ · Bʲ = Bⁱ⁺ʲ, значит ему место в разряде i + j результата.

          1 2 3 4        b = [4, 3, 2, 1]
        × 5 6 7 8        a = [8, 7, 6, 5]
        ---------
          9 8 7 2        1234 · 8      попадает в разряды 0..3
        8 6 3 8          1234 · 7      сдвиг на разряд: 1..4
      7 4 0 4            1234 · 6      сдвиг на два:    2..5
    6 1 7 0              1234 · 5      сдвиг на три:    3..6
    -------------
    7 0 0 6 6 5 2        7 006 652

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

Переполнения разряда при этом не бывает. Самое большое, что может получиться в одной ячейке, - старое значение (до B − 1), плюс произведение (до (B − 1)²), плюс перенос (до B − 1). В сумме (B − 1)² + 2(B − 1) = B² − 1: частное от деления на B не больше B − 1, то есть перенос снова помещается в разряд. Но само промежуточное число доходит до B², и ему нужно слово вдвое шире разряда.

Произведение числа из n разрядов на число из m разрядов занимает n + m разрядов или на один меньше.

Правило

Умножение столбиком числа из n разрядов на число из m разрядов стоит Θ(n · m) действий над разрядами; для чисел одной длины это Θ(n²). Умножение длинного числа на короткое - такое, что его произведение на разряд помещается в машинное слово, - стоит Θ(n). Основание выбирают так, чтобы B² помещалось в самый широкий точный тип. Деление длинного на короткое стоит Θ(n), длинного на длинное уголком - Θ(n · m). Быстрые умножения - Карацуба с n^1.585 и умножение через преобразование Фурье с n · log n - включаются выше порога, и деление тогда ускоряется вместе с ними: оно сводится к нескольким умножениям.

Разбор: программа и её цена

def umnozh(a, b, B):
    out = [0] * (len(a) + len(b))
    i = 0
    while i < len(a):
        perenos = 0
        j = 0
        while j < len(b):
            p = out[i + j] + a[i] * b[j] + perenos
            out[i + j] = p % B
            perenos = p // B
            j = j + 1
        out[i + len(b)] = perenos
        i = i + 1
    while len(out) > 1 and out[len(out) - 1] == 0:
        out.pop()
    return out

Внешний цикл берёт цифру a[i], внутренний проводит её по всему b. Строка после внутреннего цикла кладёт последний перенос в разряд, которого этот проход ещё не касался. Последний цикл снимает нули сверху: [0] * (n + m) взято с запасом, и 99 · 99 = 9801 заняло все четыре разряда, а 12 · 13 = 156 - только три.

umnozh([8, 7, 6, 5], [4, 3, 2, 1], 10) возвращает [2, 5, 6, 6, 0, 0, 7] - число 7 006 652 из схемы выше. Цена на тренажёре, оба числа по n разрядов:

n        шагов          5n² + 8n + 9
50        12 909            12 909
100       50 809            50 809
200      201 609           201 609
400      803 209           803 209

Формула сходится точно, и главное в ней - 5n²: пять строк внутреннего цикла на каждую пару цифр. Число вдвое длиннее - умножение вчетверо дороже.

Длинное на короткое - тот же внутренний цикл без внешнего:

def umnozh_korotkoe(a, k, B):
    out = []
    perenos = 0
    for x in a:
        p = x * k + perenos
        out.append(p % B)
        perenos = p // B
    while perenos > 0:
        out.append(perenos % B)
        perenos = perenos // B
    return out

Последний цикл нужен, потому что множитель k может быть больше основания: при B = 10 и k = 25 перенос бывает двузначным. Так считают факториал: начать со списка [1] и по очереди умножить его на 2, 3 и так далее до 25. 25! - это 24 умножения длинного на короткое, и на тренажёре по основанию 10 все 26 цифр 15511210043330985984000000 получаются за 1426 шагов.

Разбор: быстрая степень, которая не быстрая

Вернёмся к 3⁸⁰⁰. Первый способ - 800 раз вызвать umnozh_korotkoe(r, 3, 10), начав с r = [1]. Второй - квадраты; здесь a - короткое число, основание степени, а n - показатель, вызов stepen_kvadratami(3, 800, 10):

def stepen_kvadratami(a, n, B):
    r = [1]
    x = [a]
    while n > 0:
        if n % 2 == 1:
            r = umnozh(r, x, B)
        n = n // 2
        if n > 0:
            x = umnozh(x, x, B)
    return r

степень    разрядов в ответе    подряд по одному    квадратами    выигрыш
100              48                  10 491            5 222        2,0
200              96                  40 067           18 996        2,1
400             191                 156 468           72 555        2,2
800             382                 618 293          283 942        2,2

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

Откуда квадрат у первого способа, известно из прошлого урока: n дешёвых действий над числом, которое растёт до 0,477 · n разрядов. У второго способа умножений всего двенадцать: девять возведений в квадрат и три домножения. Но последнее из них перемножает 3²⁸⁸ и 3⁵¹² - числа из 138 и 245 разрядов: 138 · 245 = 33 810 пар цифр, около 169 тысяч шагов из 284. Предпоследнее - квадрат 123-разрядного 3²⁵⁶, ещё 76 тысяч. Два последних умножения - шесть седьмых всей цены.

Счёт «двенадцать вместо восьмисот» верен, пока каждое умножение стоит одинаково. Так бывает в двух случаях. Либо числа держат короткими, беря остаток по модулю после каждого шага, - тогда все умножения идут над числами одной длины, и про это следующая глава. Либо само умножение быстрее квадрата: с умножением за n · log n квадраты выигрывают уже по порядку, потому что столбик из n коротких умножений остаётся квадратичным.

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

Первое: слишком большое основание. При B = 10⁹ произведение двух разрядов доходит до 10¹⁸. На тренажёре и в JavaScript это за границей точности, в C не помещается в 32 бита, а в 64 входит впритык. Основание 10⁶ даёт запас: 10¹² плюс переносы помещаются всюду.

Второе: неснятые старшие нули. [6, 5, 1, 0] и [6, 5, 1] - одно число, но длины разные, и сравнение «у кого больше разрядов, тот и больше» начинает врать. Нули снимают после каждой операции, которая могла их оставить.

Третье: out[i + len(b)] = perenos забыто. Перенос последней цифры прохода теряется, и ошибка видна только когда он не нулевой: 12 · 13 проходит, 99 · 99 даёт [1] вместо [1, 0, 8, 9].

Четвёртое: вера в число умножений. Оценка «алгоритм делает log n умножений» ничего не говорит о цене, пока не сказано, над числами какой длины.

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

Звёздочка в Python. Пока меньший из множителей не длиннее 70 внутренних разрядов по 30 бит - это около 630 десятичных цифр, - CPython умножает столбиком. Выше включается Карацуба. Быстрее Карацубы в стандартном Python ничего нет, поэтому программы, которым нужны числа в миллионы цифр, берут библиотеку GMP: там лестница из столбика, Карацубы, нескольких вариантов Тоома-Кука и умножения через преобразование Фурье, и пороги между ступенями подобраны замером под каждый процессор.

Ключи. Число в 2048 бит - это 32 машинных слова по 64 бита. Такая длина - около порога между столбиком и Карацубой, а преобразование Фурье на ней проигрывает обоим. Поэтому криптографические библиотеки вкладываются не в асимптотику, а в то, чтобы умножение столбиком занимало одинаковое время на любых данных.

Рекорды. Самое большое известное простое число - 2¹³⁶ ²⁷⁹ ⁸⁴¹ − 1, 41 024 320 десятичных цифр, найдено в октябре 2024 года. Проверка такого числа - 136 миллионов возведений в квадрат, и каждое делается через преобразование Фурье: столбиком один квадрат занял бы 1,7 · 10¹⁵ умножений цифр.

Теоретический предел тоже известен: в 2019 году Харви и ван дер Хувен показали умножение за n · log n. Их алгоритм выигрывает на числах, которые не поместятся ни в один компьютер, и на практике не используется - редкий случай, когда лучшая оценка и лучшая программа расходятся полностью.

Теперь сам

1. Числа 47 и 36 заданы списками [7, 4] и [6, 3]. В какой разряд результата попадает произведение a[1] · b[1] и чему оно равно? Чему равен результат целиком?
2. По формуле из разбора: сколько шагов тренажёра стоит умножение двух чисел по 1000 разрядов?
3. Число умножают столбиком на само себя. Во сколько раз вырастет цена, если число станет втрое длиннее?
4. Сколько разрядов может быть в произведении 300-разрядного числа на 200-разрядное?