Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
Хочу рассказать читателям о программистском трюке, с которым я познакомился в какой-то переводной книжке, содержащей подборку таких трюков, в те далёкие времена, когда ещё не изобрели не то что байт, а страшно сказать — стек, а великий Дейкстра ещё не проклял оператор 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.
Для современных процессоров представляется разумным иметь размер цифр кратным размеру байта для лёгкого доступа к ним. При цифрах размером в 1 байт, размер таблицы всего лишь 1022 байт, что может позволить использовать этот трюк в 8-битных процессорах, не имеющих аппаратного умножения.
Буду благодарен всем читателям этой заметки за исправления и замечания.
Трюк настолько мне понравился простотой и изяществом, что уже в этом тысячелетии я с удовольствием рассказывал о нём студентам в виде следующей задачи.
Представьте себе, что в процессе возвращения в 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-битных процессорах, не имеющих аппаратного умножения.
Буду благодарен всем читателям этой заметки за исправления и замечания.
