Замена деления умножением на обратную величину
В предыдущем разделе было показано, что операцию умножения можно производить сравнительно быстро, если взять на вооружение комбинационные схемы параллельного умножения. Данное обстоятельство можно использовать, заменив операцию деления на D умножением на
В этом случае проблема сводится к эффективному вычислению X/D. Обычно задача решается одним из двух методов; с помощью ряда Тейлора или метода Ньютона-Рафсона. В обоих случаях основное время расходуется на умножение, поэтому рассматриваемый метод ускорения деления имеет смысл при наличии быстрых схем умножения.
При реализации первого метода делитель D представляется в виде: D = 1+Х. Тогда для двоичного представления D можно записать:
Метод был использован в модели 91 вычислительной машины IBM 360 для вычисления 32-разрядной величины 1/D. Возможные значения сомножителей в правой части выражения извлекались из таблицы емкостью 28 байт, хранящейся в памяти. Операция вычисления 1/D требует шести умножений.
Вычисление величины 1/D методом Ньютона-Рафсона сводится к нахождению корня уравнения
то есть Х= I/O. Решение может быть получено с привлечением рекуррентного соотношения: Xi+l = Xi (2 –
XiD). Количество итераций определяется требуемой точностью вычисления X/d. Реализация метода для n-разрядных чисел требует 2 int(log2n) — 1 операций умножения.
В общем, замена операции деления на умножение более характерна для чисел с плавающей запятой.
Ускорение вычисления частичных остатков
Возможности данного подхода весьма ограничены и связаны в основном с ускорением операций сложения (вычитания). Способы достижения этой цели ничем не отличаются от тех, что применяются, например, при выполнении умножения. Это различные приемы для убыстрения распространения переноса, матричные схемы сложения и т. п. В частности, для вычисления частичных остатков может быть применена матричная схема, показанная на рис. 7.53.
Рис. 7.53. Матричное устройство деления для алгоритма без восстановления остатка
Представленная схема реализует алгоритм деления без восстановления остатка для правильных дробей, что типично в операциях над мантиссами чисел в форме с плавающей запятой. Нетрудно заметить, что схеме присущ длинный тракт распространения переноса, что явно не способствует сокращению времени деления. Таким образом, матричное исполнение деления нельзя считать очень эффективным в плане быстродействия, хотя данный метод и выигрывает в сравнении с традиционным устройством деления. Основное достоинство матричной схемы заключается в ее регулярности, что удобно при реализации устройства в виде интегральной микросхемы.
Алгоритм srt
В основе третьей группы методов ускорения операции деления, согласно приведенной выше классификации, лежит так называемый алгоритм SRT [77,184,214]. Свое название алгоритм получил по фамилиям авторов (Sweeney, Robertson, Tocher), разработавших его независимо друг от друга приблизительно в одно и то же время. Этот алгоритм представляет собой модификацию деления без восстановления остатка. В стандартной процедуре па каждом шаге помимо сдвига частичного остатка производится прибавление либо вычитание делителя. В SRT-алгоритме сдвиг Ч0 также имеется в каждой итерации, однако сложение или вычитание в зависимости от получающегося Ч0, на отдельных шагах может не выполняться, что, естественно, позитивно влияет па быстродействие деления.
Алгоритм был ориентирован на операции над мантиссами чисел с плавающей запятой и опирается на то обстоятельство, что мантиссы в таких числах нормализованы. Впервые SRT-алгоритм был реализован и модели 91 вычислительной машины IBM 360. В настоящее время он широко применяется в блоках обработки чисел с плавающей запятой, в частности в микропроцессорах фирмы Intel.
Сначала рассмотрим алгоритм применительно к положительным целым числам. Делимое представляется (2п + 1)-разрядным числом, а делитель — n-разрядным. Процедура деления начинается с удаления в делителе всех нулей, предшествующих старшей единице, то есть с операции, аналогичной нормализации мантиссы в числах с плавающей запятой. По той же аналогии будем в дальнейшем условно называть эту операцию нормализацией. Исключение k предшествующих нулей реализуется за счет сдвига делителя влево на k разрядов. На аналогичное число разрядов влево сдвигается и делимое. Далее выполняются п итерации, в которых вычисляются цифры частного и частичные остатки. Действия, выполняемые на i-й итерации, можно описать следующим образом:
Обратим внимание па то, что частное представляется в системе счисления, отличной от двоичной. Это означает, что цифры частного могут иметь больше, чем. два значения О и 1. В рассматриваемом случае — -1,0, 1.
По завершении всех п итераций, если последний остаток отрицателен, выполняется коррекция этого остатка и полученного частного, для чего к остатку прибавляется делитель, а из частного вычитается единица с весом младшего разряда.
Последний момент в алгоритме — преобразование частного из системы <-1,0,1>в систему <0, 1>, то есть в обычную двоичную систему.
На практике это выливается в следующую процедуру (при объяснении будем ссылаться на схему деления без восстановления остатка, приведенную на рис: 7.50). Делимое и делитель, представленные в дополнительном коде, размещаются в регистре делимого (РДМ) и делителя (РДТ) соответственно. Дальнейшие действия можно описать следующим образом.
1. Если в делителе D имеются к предшествующих нулей (при D > 0) или предшетвующих единиц (при D < 0), то производится предварительный сдвиг содержимого РДМ и РДТ влево на k разрядов.
2. Для i от 0 до п — 1:
— если три старших цифры частичного остатка в РДМ совпадают, то qi = О и производится сдвиг содержимого РДМ па один разряд влево;
— если три старших цифры частичного остатка в РДМ не совпадают, а сам ЧО отрицателен, то qi = -1, делается сдвиг содержимого РДМ на один разряд влево и к ЧО прибавляется делитель;
— если три старших цифры частичного остатка в РДМ не совпадают, а сам ЧО положителен, то qi = 1, выполняется сдвиг содержимого РДМ на разряд влево и из ЧО вычитается делитель.
3. Если после завершения пункта 2 остаток отрицателен, то производится коррекция (к остатку прибавляется делитель, а из частного вычитается единица).
4. Остаток сдвигается вправо на k разрядов.
Описанную процедуру иллюстрирует пример, приведенный на рис. 7.54.
Рис. 7.54. Пример деления целых чисел по алгоритму SRT
На первом шаге для удаления предшествующих нулей делитель сдвигается на два разряда влево. Аналогично поступают и с ЧО, который вначале совпадает с делимым. Далее выполняется процедура, описанная выше в пункте 2. Операция вычитания D обеспечивается прибавлением делителя с противоположным знаком. Поскольку по завершении операции остаток отрицателен, производится его коррекция путем прибавления D. Одновременно частное уменьшается на единицу (эта операция показана в системе <-1,0, 1>, в которой представлено частное). Наконец, на последнем шаге форма представления частного меняется, переходят к представлению в стандартной двоичной системе.
В стандартном алгоритме деления без восстановления остатка помимо сдвига в каждой итерации выполняется операция сложения или вычитания. В варианте SRT, в зависимости от кодов операндов в отдельных итерациях, достаточно только сдвига, что, безусловно, ускоряет процесс деления, Согласно статистическим данным, в среднем число сложений и вычитании при использовании этого алгоритма сокращается в 2,67 раза.
Деление через умножение на обратное число
Если тебя интересует сам алгоритм, то смысл его сводится к следующему: операцию деления Z/D можно заменить на умножение Z*(1/D). Весь вопрос в том, как определить 1/D. Для этого используются два метода — разложение в ряд Тейлора и метод Ньютона-Рафсона.
Первый: D=1+X, тогда 1/D = (1-X)*(1+X^2)*(1+X^4)*(1+X^8)*(1+X^16)*.
Второй сводится к решению уравнения f(X) = 1/X — D = 0, т.е. X = 1/D, которое может быть найдено с помощью реккурентного соотношения
X(i+1) = X(i)*(2-X(i)D).
все проще мне нужно просто разделить двоичную «1» на делитель, и потом сдвинуть дробную часть — в сектор целой, и полученное двоичное целое умножить на делимое ))
Так действительно проще. Только как ты будешь делить 1 на делимое?
так — как еслибы это было число с плавающей точкой: например 1/2 будет выглядеть 0000.1000 — теперь сдвину дробную часть в область целой, и умножу делимое на 1000 ))
Если тебя это устраивает, то замечательно. Просто это совсем не замена деления умножением.
Меня ничего не смущает — это твоя задача, и тебе реализовывать ее так, как тебе удобнее. Только я повторюсь — тот метод, что ты предложил, не есть метод замены деления умножением, потому что такой метод замены предполагает НЕ использование операции деления вообще, а у ты собираешься использовать «обычное двоичное деление». Т.е. ты просто заменяешь одну операцию деления — двумя, одна из которых тоже деление. Может, с сумме они и дадут выигрыш по времени/производительности, ни это уже зависит от реализации.
Как заменить деление на умножение?
Я знаю, что для этого можно просто умножить делимое на обратную дробь, созданную из самого примера на деление. Предположим, что мы хотим 25 разделить на 5. 25 * 5/25 даст нужный результ в виде простой дроби.
Но так как мне нужна десятичная дробь, то придется делить простую дробь, чтобы ее получить. Замкнутый круг. А я хочу как раз избежать операции деления. Существует ли достаточно простой и универсальный способ перевода простой дроби в десятичную без деления?
Или как вариант, какой может быть другой, достаточно простой и универсальный способ замены деления на умножение?
задан 28 Окт ’12 19:21
5 ответов
А зачем делить на 5/25? В данном случае это верно, но не всегда. Например, чтобы поделить 36 на 4, надо умножить 36 на 1/4 =9/36, а не на 4/36.
Чтобы поделить на 5, надо умножить на 1/5 = 0,2.
Поставьте задачу точнее: что делать, если деление не заканчивается за конечное число шагов? Взять приближенное значение (с какой точностью?) Найти период дроби?
Если Вы делите только на степени двойки и пятерки (чтобы деление закончилось), можно воспользоваться тем, что 1/2 = 0,5 и 1/5 = 0,2, т.е. заменить деление на 5 умножением на 2 с последующим передвижением десятичной запятой. Правда, последнее действие по сути тоже деление, но без него не обойтись.
отвечен 28 Окт ’12 22:15
Уточняю: найти относительно простой и универсальный способ выполнить деление без самого деления. Считайте, что деление теперь является тяжким преступлением, которое карается расстрелом.
Вы не поняли. Что и на что делится? С какой точностью? Например, только числа в пределах от 1 до 10000. Или любые числа. Приближенно? Или точно? В последнем случае нужно найти период дроби?
Что считать результатом деления 5/3? 1,66666. или 1,7 или 1,67, или 1,667, . или 1,(6) ?
Если бы такой способ знали, его бы изучали в школе.
Если эта задача программистская, то все целые числа ограничены какой-то константой, а все дроби — какой-то точностью.
Можно привести к знаменателю 10, 100, 1000. А затем написать как десятичную
отвечен 15 Июн ’15 13:41
Если деление запрещено, то ответ можно найти методом подбора: 100 / 5 = ? Какое число нужно умножить на 5, что бы получилось 100? Методом подбора получаем 20. Можно воспользоваться «словарём» — заранее иметь словарь значений от деления единицы на разные числа, которые могут потребоваться, и затем умножать второе число на значение из словаря. Например, для 1/5 имеем без деления заранее известный (может быть методом подбора) ответ: 0.2 Тогда заменяем 100/5 = 100*0.2 = 20 Ну и, наконец, можно в некоторых случаях, выйти из положения с помощью хитрых правил. Например, деление на 10 не обязательно вычислять, нужно просто передвигать «запятую», разделяющую целую и дробную часть. При этом если в пустую дробь попадает 0, то её не записываем, так, 2230/10 = 223 без выполнения операции деления. Аналогично можно поступить с другими случаями: что бы 2230 разделить на 2, нужно сначала перевести это число в двоичную систему счисления, а затем перенести запятую и вернуть обратно в десятичную. Для данного случая 2230(10) = 100010110110(2) / 2(10) = 10001011011(2) = 1115(10). Ответ получен без операции деления — только перемещением запятой в нужной системе счисления.
отвечен 1 Дек ’16 10:47
Чтобы перевести число в двоичную (десятичную, …) систему счисления, нужно поделить его на два (десять, …). Причём не однажды. Я думаю, что исходная задача всё-таки нереалистична. Что значит: за деление — расстрел? Надо дойти с жалобой до ЕСПЧ! Наверняка была какая-то осмысленная задача, которая привела к этой бессмысленной формулировке…
Читайте мою статью «Вместо деления умножение» в интернете
отвечен 29 Янв ’19 20:24
Будем говорить честно, в школах у нас паршиво учат: 49 / 7 = 49 * (7 ^ -1)
отвечен 24 Июл ’14 4:51
Здравствуйте
Математика — это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Делись, рыбка, быстро и нацело
Деление — одна из самых дорогих операций в современных процессорах. За доказательством далеко ходить не нужно: Agner Fog[1] вещает, что на процессорах Intel / AMD мы легко можем получить Latency в 25-119 clock cycles, а reciprocal throughput — 25-120. В переводе на Русский — МЕДЛЕННО! Тем не менее, возможность избежать инструкции деления в вашем коде — есть. И в этой статье, я расскажу как это работает, в частности в современных компиляторах(они то, умеют так уже лет 20 как), а также, расскажу как полученное знание можно использовать для того чтобы сделать код лучше, быстрее, мощнее.
Собственно, я о чем: если делитель известен на этапе компиляции, есть возможность заменить целочисленное деление умножением и логическим сдвигом вправо (а иногда, можно обойтись и без него вовсе — я конечно про реализацию в Языке Программирования). Звучит весьма обнадеживающе: операция целочисленного умножения и сдвиг вправо на, например, Intel Haswell займут не более 5 clock cycles. Осталось лишь понять, как, например, выполняя целочисленное деление на 10, получить тот же результат целочисленным умножением и логическим сдвигом вправо? Ответ на этот вопрос лежит через понимание… Fixed Point Arithmetic (далее FPA). Чуть-чуть основ.
При использовании FP, экспоненту (показатель степени 2 => положение точки в двоичном представлении числа) в числе не сохраняют (в отличие от арифметики с плавающей запятой, см. IEE754), а полагают ее некой оговоренной, известной программистам величиной. Сохраняют же, только мантиссу (то, что идёт после запятой). Пример:
0.1 — в двоичной записи имеет ‘бесконечное представление’, что в примере выше отмечено круглыми скобками — именно эта часть будет повторяться от раза к разу, следуя друг за другом в двоичной FP записи числа 0.1.
В примере выше, если мы используем для хранения FP чисел 16-битные регистры, мы не сможем уместить FP представление числа 0.1 в такой регистр не потеряв в точности, а это в свою очередь скажется на результате всех дальнейших вычислений в которых значение этого регистра участвует.
Пусть дано 16-битное целое число A и 16-битная Fraction часть числа B. Произведение A на B результатом дает число с 16 битами в целой части и 16-тью битами в дробной части. Чтобы получить только целую часть, очевидно, нужно сдвинуть результат на 16 бит вправо.
Поздравляю, вводная часть в FPA окончена.
Формируем следующую гипотезу: для выполнения целочисленного деления на 10, нам нужно выполнить умножение Числа Делимого на FP представление числа 0.1, взять целую часть и дело в шля… минуточку… А будет ли полученный результат точным, точнее его целая часть? — Ведь, как мы помним, в памяти у нас хранится лишь приближенная версия числа 0.1. Ниже я выписал три различных представления числа 0.1: бесконечно точное представление числа 0.1, обрезанное после 16-ого бита без округления представление числа 0.1 и обрезанное после 16 ого бита с округлением вверх представление числа 0.1.
Оценим погрешности truncating представлений числа 0.1:
Чтобы результат умножения целого числа A, на Аппроксимацию числа 0.1 давал точную целую часть, нам нужно чтобы:
Удобнее использовать первое выражение: при мы всегда получим тождество (но, заметь, не все решения, что в рамках данной задачи — более чем достаточно). Решая, получаем . То есть, умножая любое 14-битное число A на truncating with rounding up представление числа 0.1, мы всегда получим точную целую часть, которую бы получили умножая бесконечно точно 0.1 на A. Но, по условию у нас умножается 16-битные число, а значит, в нашем случае ответ будет неточным и довериться простому умножению на truncating with rounding up 0.1 мы не можем. Вот если бы мы могли сохранить в FP представлении числа 0.1 не 16 бит, а, скажем 19, 20 — то все было бы ОК. И ведь можем же!
Внимательно смотрим на двоичное представление — truncating with rounding up 0.1: старшие три бита — нулевые, а значит, и никакого вклада в результат умножения не вносят (новых бит).
Следовательно, мы можем сдвинуть наше число влево на три бита, выполнить округление вверх и, выполнив умножение и логический сдвиг вправо сначала на 16, а затем на 3 (то есть, за один раз на 19 вообще говоря) — получим нужную, точную целую часть. Доказательство корректности такого ’19’ битного умножения аналогично предыдущему, с той лишь разницей, что для 16-битных чисел оно работает правильно. Аналогичные рассуждения верны и для чисел большей разрядности, да и не только для деления на 10.
Ранее я писал, что вообще говоря, можно обойтись и без какого-либо сдвига вовсе, ограничившись лишь умножением. Как? Ассемблер x86 / x64 на барабане:
В современных процессорах, есть команда MUL (есть еще аналоги IMUL, MULX — BMI2), которая принимая один, скажем 32 / 64 -битный параметр, способна выполнять 64 / 128 битное умножение, сохраняя результат частями в два регистра (старшие 32 / 64 бита и младшие, соответственно):
В регистре RCX пусть хранится некое целое 62-битное A, а в регистре RAX пускай хранится 64 битное FA представление truncating with rounding up числа 0.1 (заметь, никаких сдвигов влево нету). Выполнив 64-битное умножение получим, что в регистре RDX сохранятся старшие 64 бита результата, или, точнее говоря — целая часть, которая для 62 битных чисел, будет точной. То есть, сдвиг вправо (SHR, SHRX) не нужен. Наличие же такого сдвига нагружает Pipeline процессора, вне зависимости поддерживает ли он OOOE или нет: как минимум появляется лишняя зависимость в, скорее всего и без того длинной цепочке таких зависимостей (aka Dependency Chain). И вот тут, очень важно упомянуть о том, что современные компиляторы, видя выражение вида some_integer / 10 — автоматически генерируют ассемблерный код для всего диапазона чисел Делимого. То есть, если вам известно что числа у вас всегда 53-ех битные (в моей задаче именно так и было), то лишнюю инструкцию сдвига вы получите все равно. Но, теперь, когда вы понимаете как это работает, можете сами с легкостью заменить деление — умножением, не полагаясь на милость компилятору. К слову сказать, получение старших битов 64 битного произведения в C++ коде реализуется интринсиком (something like mulh), что по Asm коду, должно быть равносильно строчкам инструкции MUL
Возможно, с появлением контрактов (в С++ 20 не ждем) ситуация улучшится, и в каких-то кейсах, мы сможем довериться машине! Хотя, это же С++, тут за все отвечает программист — не иначе.
Рассуждения описанные выше — применимы к любым делителям константам, ну а ниже список полезных ссылок: