Хочу сразу предупредить тех, кто сюда заглянул в надежде научиться быстро умножать 146 на 253. Вы уж извините, тут разговор пойдёт лишь о числах в двоичном представлении, то есть, об умножении 10010010 на 11111101. В общем, о двоичной арифметике.
NB: Двоичная арифметика, как все знают, любима вычислительной техникой, людям же, в силу культурных традиций и физиологических особенностей, привычнее десятичные записи чисел, поэтому дальше, чтобы совсем не запутаться, я буду двоичные записи чисел выделять курсивом. То есть, если встретилось 100 - то это двоичная запись четвёрки, а если 100 - то это десятичная запись сотни.
Итак, приступим. Надо сказать, что в двоичной арифметике умножение - штука довольно простая, проводимая при помощи сложений и битовых сдвигов. Действительно, что означает 101 умножить на 10 (то есть, на двойку)? Да просто приписать справа нолик:
101 ∙ 10 = 1010
Со степенями двойки (100, 1000 и т.п.) дело обстоит точно так же.
Поэтому обычное умножение в двоичной арифметике выглядит просто:
101∙110 = 101 ∙ (100+10+0) = 101∙100 + 101∙10 + 101∙0 = 10100+1010 = 11110
Битовые сдвиги влево - те самые приписывания ноликов - компьютер умеет делать шустро, складывать тоже умеет хорошо, поэтому проблем с умножением не возникает. В разных языках программирования даже есть операция, делающая битовый сдвиг числа на нужное количество разрядов. Мне привычнее обозначение Си, его и буду использовать:
101 << 1 даст 1010
101 << 2 даст 10100
и т.п.
Но вернёмся к основной теме статьи. Пусть, например, нам надо умножить некое число A на B=11111. Получаем:
A∙11111 = A ∙ (10000+1000+100+10+1) = A<<4 + A<<3 + A<<2 + A<<1 + A<<0
Как видим, потребуются четыре сложения и четыре битовых сдвига.
Но ситуацию можно улучшить, если заметить, что 11111 = 100000 - 1. Действительно, получаем:
A∙11111 = A∙(100000 - 1) = A << 5 - A
То есть, для достижения результата нужен всего один битовый сдвиг и одно вычитание!
На этом и основан метод Лемана. Алгоритм ищет в множителе последовательности из нескольких единиц и заменяет соответствующие суммирования одним вычитанием. Пусть, например, мы теперь умножаем A на B=10111101. Разбиваем 10111101 на группы 1 | 0 | 1111 | 0 | 1, и применяем к кучке единиц вышеописанную хитрость:
A∙10111101 = A<<7 + (A∙1111)<<2 + A = A<<7 + (A∙(10000 - 1))<<2 + A =
= A<<7 + (A<<4 - A)<<2 + A
То есть, вместо уготованных судьбой шести сложений (по количеству единиц в записи 10111101) мы обошлись всего тремя (ну, строго говоря, двумя сложениями и вычитанием, но вычитание для компьютера - тоже не большая проблема).
Осталось лишь упомянуть о том, как именно компьютер ищет эти самые последовательности единиц. Это человеку хорошо - глянул запись, и сразу понял, где там что можно сократить. Компьютер так не умеет. Поэтому он заводит два битовых флага, d и s:
Флаг d принимает значения {0=не нужно ничего делать | 1=нужно что-то делать}.
Флаг s принимает значения {0=складывать | 1=вычитать}.
Компьютер проходит по второму множителю от младших разрядов к старшим, попутно вычисляя флаги и суммируя при необходимости сдвинутый первый множитель.
Приведу для порядка формулы вычисления флагов d и s на n-м шаге (то есть, при анализе n-го бита):
dₙ = ( Bₙ and ¬Bₙ₋₁ ) or (¬Bₙ and Bₙ₋₁ and ¬dₙ₋₁)
sₙ = Bₙ₊₁ and Bₙ
Здесь Bₙ - обозначение n-го бита числа B.
В качестве примера рассмотрю всё то же умножение A∙10111101.
Подготовка к алгоритму - распихиваем в ячейки памяти наши числа:
𝓐 = A
𝓑 = 10111101
d = 0
s = 0
сумматор = 0
Анализируем 0-й бит числа B:
𝓐 = A
𝓑 = 10111101
d = 1 (нужно что-то делать)
s = 0 (складывать)
сумматор = A
Анализируем 1-й бит числа B:
𝓐 = A<<1
𝓑 = 10111101
d = 0 (не нужно ничего делать)
s = 0 (складывать)
сумматор = A
Анализируем 2-й бит числа B:
𝓐 = A<<2
𝓑 = 10111101
d = 1 (нужно что-то делать)
s = 1 (вычитать)
сумматор = A - A<<2
Анализируем 3-й бит числа B:
𝓐 = A<<3
𝓑 = 10111101
d = 0 (не нужно ничего делать)
s = 1 (вычитать)
сумматор = A - A<<2
Анализируем 4-й бит числа B:
𝓐 = A<<4
𝓑 = 10111101
d = 0 (не нужно ничего делать)
s = 1 (вычитать)
сумматор = A - A<<2
Анализируем 5-й бит числа B:
𝓐 = A<<5
𝓑 = 10111101
d = 0 (не нужно ничего делать)
s = 0 (складывать)
сумматор = A - A<<2
Анализируем 6-й бит числа B:
𝓐 = A<<6
𝓑 = 10111101
d = 1 (нужно что-то делать)
s = 0 (складывать)
сумматор = A - A<<2 + A<<6
Анализируем 7-й бит числа B:
𝓐 = A<<7
𝓑 = 10111101
d = 1 (нужно что-то делать)
s = 0 (складывать)
сумматор = A - A<<2 + A<<6 + A<<7
В итоге получили ту же формулу, что и раньше.
Существуют, разумеется, числа, на которых этот алгоритм не даст никакого выигрыша, например, 101010101 - тут получатся всё те же n/2 сложений. Но существуют также варианты, где потребуется всего одно вычитание, например, для множителя 11111111. В среднем же, говорят, алгоритм Лемана позволяет обходиться n/3 сложениями.
Ну и напоследок приведу список учебных пособий, с помощью которых этот алгоритм удалось разобрать:
В. И. Потапов, О.П. Шафеева, И.В. Червенчук, ОСНОВЫ КОМПЬЮТЕРНОЙ АРИФМЕТИКИ И ЛОГИКИ, Учебное пособие, Омск, 2004
И. В. Потапов, ЭЛЕМЕНТЫ ПРИКЛАДНОЙ ТЕОРИИ ЦИФРОВЫХ АВТОМАТОВ, Учебное пособие, Омск, 2011