Pull to refresh

Быстрое умножение целых чисел с использованием таблиц

Reading time 3 min
Views 15K
Хочу рассказать читателям о программистском трюке, с которым я познакомился в какой-то переводной книжке, содержащей подборку таких трюков, в те далёкие времена, когда ещё не изобрели не то что байт, а страшно сказать — стек, а великий Дейкстра ещё не проклял оператор GOTO (sic, in uppercase).

Трюк настолько мне понравился простотой и изяществом, что уже в этом тысячелетии я с удовольствием рассказывал о нём студентам в виде следующей задачи.

Представьте себе, что в процессе возвращения в 2030 году с Луны вы вдруг обнаружили, что ваш бортовой компьютер неправильно выполняет операции целочисленного умножения, и это непременно приведёт к аварии при посадке.

В таком сюжете нет ничего особо фантастического. Вспомним, например, какие проблемы случались когда-то с процессорами Pentium , а к моменту отправки на Луну вы ещё не достигли полного импортозамещения. И вообще надо проверить, а не были ли процессоры просверлены специально.

Но к делу. Вам надо срочно реализовать умножение программно, чтоб работало быстро в реальном времени и укладывалось в доступный ресурс.

Из школьного курса арифметики вспоминаем, что многозначные числа умножать можно столбиком, а результат умножения отдельных цифр брать из таблицы умножения.

Вот только если цифры выбрать короткими (например 0 и 1), таблица умножения будет короткой, а столбики длинными, и их вычисление будет занимать много времени.

Если, наоборот, взять цифры длинные (например от 0 до 65535), то для 16-битной арифметики
результат берётся прямо из таблицы, а столбики отсутствуют. Однако размер классической таблицы Пифагора при этом оказывается около 17GB (4*65536*65536), если учесть симметрию относительно диагонали, то половина — около 8.5GB.

Может оказаться многовато.

Напрягаемся и вспоминаем алгебру.

$(a + b)^2 = a^2 + b^2 + 2ab$ (1)

$(a - b)^2 = a^2 + b^2 - 2ab $ (2)

Вычитаем (2) из (1)

$(a + b)^2 - (a - b)^2 = 4ab$

и далее

$a b = ((a + b)^2 - (a - b)^2)/4$

Таким образом, имея таблицу квадратов в массиве 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-битных процессорах, не имеющих аппаратного умножения.

Буду благодарен всем читателям этой заметки за исправления и замечания.
Tags:
Hubs:
+45
Comments 54
Comments Comments 54

Articles