Советы
Software
Алгоритмы
Keil C51
PIC16
Хаки

Первая страница » Советы » Алгоритмы » Умножение без умножения

Умножение без умножения

Влад Князев
20 мая 2004

2 + 2 = 4
2 * 2 = 4
2² = 4

1 Постановка задачи

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

Интуитивно понятно, что наиболее просто выполняются операции умножения числа на константу, равную степени 2-х: 2, 4, 8, 16 и т.д. Это делается путем замены операции умножения на последовательность операций сдвига влево. Допустим, необходимо умножить некоторую переменную x на константу N, т.е.

y = x * N;

Эквивалентное выражение будет выглядеть так:

y = x << K;  (где K = log2 N)

Пример:

(x * 16) эквивалентно (x << 4)

Можно добавить, что подобные случаи легко распознаются компиляторами, которые оптимизируют такие выражения и при этом программисту не требуется делать такую замену самому.

В тех случаях, когда константа не равна целой степени 2-х, ситуация несколько усложняется. Но и в этих случаях можно обойтись без универсальных подпрограмм умножения. При этом помимо операции сдвига потребуется использовать дополнительно операции сложения или вычитания. В общем, правило замены умножения на более простые операции таково:

необходимо представить константу в виде суммы или, если потребуется, разности целой степени 2-х и единицы (или другого небольшого числа).

2 Немного теории

Попробуем разобраться, как это можно сделать. Возьмем исходное выражение:

y = x * N; или, что то же самое y = N * x;			(1)

здесь x — некоторая переменная, N — константа.

Предположим (без ограничения общности и для простоты рассуждений), что N представляет собой 8-разрядное двоичное число. Как и любое число в позиционной системе счисления оно может быть записано в виде полинома:

N = (d₇d₆d₅d₄d₃d₂d₁d₀)₂ = d₇·2⁷+d₆·2⁶+d₅·2⁵+d₄·2⁴+d₃·2³+d₂·2²+d₁·2¹+d₀·2⁰ (2)

здесь d_i = 0,1 — двоичная цифра в i-ом разряде числа.

С учетом этого выражение (1) можно переписать в виде

y = d₇·2⁷·x+d₆·2⁶·x+d₅·2⁵·x+d₄·2⁴·x+d₃·2³·x+d₂·2²·x+d₁·2¹·x+d₀·2⁰·x (3)

Таким образом, операция умножения свелась к процедуре вычисления полинома. Но стало ли от такой замены выполнение операции умножения проще? На первый взгляд это совсем не очевидно.

Чтобы упростить процедуру вычисления такого полинома, мы воспользуемся схемой Горнера, часто используемой для этих целей. Перепишем полином (3) соответствующим образом:

y = ((((((d₇·x·2+d₆·x)·2+d₅·x)·2+d₄·x)·2+d₃·x)·2+d₂·x)·2+d₁·x)·2+d₀·x (4)

Теперь процедура вычисления полинома существенно упростилась. Если учесть, что цифры в двоичном числе могут быть либо 0, либо 1, а умножение на 2 эквивалентно сдвигу числа на один разряд влево, то вычисление полинома вообще не составит большого труда.

3 Несколько примеров

Чтобы убедиться в этом, давайте рассмотрим несколько примеров.

Умножение на 3. Представим число три как сумму 2 + 1. Тогда получим

x * 3 = x * (2+1) = x*2 + x = (x<<1) + x;

Аналогично для числа 5:

x * 5 = x * (4+1) = x*4 + x = (x<<2) + x;

Одним из наиболее часто встречающихся случаев является умножение числа на 10: x * 10. Запись этого числа в виде полинома будет иметь вид:

10₁₀ = 00001010₂ = 2³ + 2¹

т.е. разряды d₇, d₆, d₅, d₄, d₂, d₀ равны нулю, а d₃ и d₁ — единице. Подставляя их значения в выражение (4), получим:

y = ((x*2 )*2 + x)*2 = (x*4 + x)*2

Заменив умножение переменной на число степени 2-х, эквивалентной операцией сдвига влево, получим выражение на языке Си в виде:

y = ((x<<2) + x) << 1;	// y = x * 10;

Как видим, для умножения переменной x на 10 потребовалось выполнить всего лишь 4 операции: 3 операции сдвига и 1 операцию сложения.

4 Частные случаи

Внимательно посмотрев на выражение (4), можно заметить, что чем меньше количество единичных разрядов в константе, тем проще вычисление полинома. Наиболее идеальный случай — умножение на константу, равную степени 2-х. В таких константах всего один единичный разряд, и для умножения потребуются только операции сдвига.

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

Но, «все не так уж сумрачно вблизи». Процедура вычисления полинома может существенно упроститься, если воспользоваться операцией вычитания, в дополнение к используемым выше операциям.

При этом мы должны учесть, что число, у которого все значащие разряды равны единице (N), на единицу меньше числа являющегося целой степенью 2-х (M). То есть справедливо равенство:

N + 1 = M или N = M - 1,

тогда

x * N = x * (M - 1) = x * M - x

Возьмем для примера N = 15. Тогда M = 16 (степень 2-х!). Выражение Си для данного случая будет выглядеть так:

y = (x <<4) - x;	// y = x * 15;

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

5 Заключение

Мне хотелось бы сделать несколько замечаний.

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

Во-вторых, выражения для умножения, записанные таким образом, становятся менее понятными, особенно для посторонних глаз. Поэтому я рекомендую в качестве комментариев показывать исходное выражение, в котором используется операция умножения. Это несколько скомпенсирует потерю наглядности программы.

И, в-третьих, компиляторы обычно не выполняют преобразования выражений, подобных тем, о которых было сказано, за исключением умножения на степень 2-х. Поэтому, если вы не хотите зависеть от способностей оптимизации используемого вами компилятора, то следует подобные преобразования выражений делать вручную самим. Это даст вам гарантию в том, что ваши вычисления будут выполняться оптимально. Но при этом все-таки нужно время от времени просматривать сгенерированный компилятором код. Это даст вам возможность выбрать из разных вариантов преобразования наиболее оптимальный.

On Embedding