Хочу рассказать читателям о программистском трюке, с которым я познакомился в какой-то переводной книжке, содержащей подборку таких трюков, в те далёкие времена, когда ещё не изобрели не то что байт, а страшно сказать — стек, а великий Дейкстра ещё не проклял оператор GOTO (sic, in uppercase).
Трюк настолько мне понравился простотой и изяществом, что уже в этом тысячелетии я с удовольствием рассказывал о нём студентам в виде следующей задачи.
Представьте себе, что в процессе возвращения в 2030 году с Луны вы вдруг обнаружили, что ваш бортовой компьютер неправильно выполняет операции целочисленного умножения, и это непременно приведёт к аварии при посадке.
В таком сюжете нет ничего особо фантастического. Вспомним, например, какие проблемы случались когда-то с процессорами Pentium , а к моменту отправки на Луну вы ещё не достигли полного импортозамещения. И вообще надо проверить, а не были ли процессоры просверлены специально.
Но к делу. Вам надо срочно реализовать умножение программно, чтоб работало быстро в реальном времени и укладывалось в доступный ресурс.
Из школьного курса арифметики вспоминаем, что многозначные числа умножать можно столбиком, а результат умножения отдельных цифр брать из таблицы умножения.
Вот только если цифры выбрать короткими (например 0 и 1), таблица умножения будет короткой, а столбики длинными, и их вычисление будет занимать много времени.
Если, наоборот, взять цифры длинные (например от 0 до 65535), то для 16-битной арифметики
результат берётся прямо из таблицы, а столбики отсутствуют. Однако размер классической таблицы Пифагора при этом оказывается около 17GB (4*65536*65536), если учесть симметрию относительно диагонали, то половина — около 8.5GB.
Может оказаться многовато.
Напрягаемся и вспоминаем алгебру.
(1)
(2)
Вычитаем (2) из (1)
и далее
Таким образом, имея таблицу квадратов в массиве sqr, получаем
a * b = ( sqr[a + b] — sqr[a — b]) / 4 (*)
Размер таблицы 8*(65535+65535) около 8.4MB, что уже может оказаться приемлемым.
Размер элемента таблицы в 8 байт связан с тем, что при максимальных a и b квадрат их суммы в 4 байта не влезает — не хватает 2-х бит.
Далее опишу некоторое улучшение, которого в книжке не было, Его я придумал сам, когда уже писал эту заметку.
Заметим, что два младших бита квадрата чётного числа всегда 00, а квадрата нечётного — всегда 01. С другой стороны для любой пары чисел их сумма и разность имеют одинаковую чётность.
Поэтому в нашей формуле (*) процесс вычитания в скобках не может иметь переносов,
связанных с двумя младшими битами. Поэтому содержимое элементов таблицы квадратов
можно заранее сдвинуть на два бита вправо и тем самым сэкономить половину памяти.
Окончательно имеем
a * b = sqr4[a + b] — sqr4[a — b] (**)
где sqr4 — модифицированная таблица квадратов.
В нашем примере её размер около 4.2 MB.
Ниже для иллюстрации этого подхода включен текст программы на языке Lua.
function create_multiplier(N) -- N это число разных цифр
local sqr4 = {} -- создаём таблицу
for i = 1, 2 * N - 1 do
local temp = 0
for j = 1, i - 1 do -- для вычисления квадрата
temp = temp + i - 1 -- используем многократное сложение
end -- т.к. умножение "неисправно"
sqr4[i] = math.floor(temp / 4) -- экономим 2 бита
end
return -- возвращаем мультипликатор (функцию)
function (i, j)
if i < j then i, j = j, i end
return sqr4[1 + i + j] - sqr4[1 + i - j]
end
end
N = 256
mpy = create_multiplier(N)
for i = 0, N - 1 do
for j = 0, N - 1 do
if i * j ~= mpy(i,j) then
print("Ошибка", i, j, i * j, mpy(i,j))
end
end
end
print("Всё работает.")
Для современных процессоров представляется разумным иметь размер цифр кратным размеру байта для лёгкого доступа к ним. При цифрах размером в 1 байт, размер таблицы всего лишь 1022 байт, что может позволить использовать этот трюк в 8-битных процессорах, не имеющих аппаратного умножения.
Буду благодарен всем читателям этой заметки за исправления и замечания.
Автор: Сергей Половников
