home
user-header
    Быстрое умножение целых чисел с использованием таблиц
    savvinovan - 21 июня 2019 г., 15:38

    Хочу рассказать читателям о программистском трюке, с которым я познакомился в какой-то переводной книжке

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

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

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

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

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

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

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

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

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

    (a+b)2=a2+b2+2ab (1)

    (a−b)2=a2+b2−2ab (2)

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

    (a+b)2−(a−b)2=4ab

    и далее

    ab=((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.a

    Читать далее 2 3 112
    Фоторепортаж бессмертный полк
    savvinovan - 9 мая 2019 г., 16:05 в ФОТОМАНЫ

     

     

     

    Читать далее 2 273
    лес в ПКиО (1 фото)
    savvinovan - 6 июня 2015 г., 21:52 в ФОТОМАНЫ

     

    Читать далее 6 3 577
    202 мкр якутск
    savvinovan - 5 июня 2015 г., 16:37 в ФОТОМАНЫ

    Читать далее 19 1770
Обратная связь