Как деление заменить умножением

Деление через умножение на обратное число

Народ, подскажите как можно делить двоичные целые числа методом умножения на обратное число!?
Буду очень признателен.

12 ответов

15 мая 2007 года
19 / / 20.04.2006

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

16 мая 2007 года
35 / / 13.05.2007

все проще мне нужно просто разделить двоичную «1» на делитель, и потом сдвинуть дробную часть — в сектор целой, и полученное двоичное целое умножить на делимое ))

16 мая 2007 года
19 / / 20.04.2006

Так действительно проще. Только как ты будешь делить 1 на делимое?

18 мая 2007 года
35 / / 13.05.2007
Так действительно проще. Только как ты будешь делить 1 на делимое?

так — как еслибы это было число с плавающей точкой: например 1/2 будет выглядеть 0000.1000 — теперь сдвину дробную часть в область целой, и умножу делимое на 1000 ))

19 мая 2007 года
19 / / 20.04.2006

Если тебя это устраивает, то замечательно. Просто это совсем не замена деления умножением.

19 мая 2007 года
35 / / 13.05.2007
почему? умножаем на обратное число, просто сдвинутое. чтоже это тогда?
19 мая 2007 года
19 / / 20.04.2006
А как ты собираешься находить обратные числа? Например, 1/23?
20 мая 2007 года
35 / / 13.05.2007

как обычно — двоичным делением. если тебя смущает целочисленность, то уменя в задаче — все обратные числа сохраняются заранее и извлекаются из таблицы

20 мая 2007 года
19 / / 20.04.2006

Меня ничего не смущает — это твоя задача, и тебе реализовывать ее так, как тебе удобнее. Только я повторюсь — тот метод, что ты предложил, не есть метод замены деления умножением, потому что такой метод замены предполагает НЕ использование операции деления вообще, а у ты собираешься использовать «обычное двоичное деление». Т.е. ты просто заменяешь одну операцию деления — двумя, одна из которых тоже деление. Может, с сумме они и дадут выигрыш по времени/производительности, ни это уже зависит от реализации.

20 мая 2007 года
35 / / 13.05.2007

фишка реализации в том, что обратные числа уже постчитаны и просто достаются из таблицы при умножении:)

23 мая 2007 года
365 / / 19.12.2005
13 декабря 2018 года
1 / / 13.12.2018

Есть метод деления любого числа на любое умножением на определённое для каждого делителя число. Этот метод я обнаружил в 80-х годах и только 10 лет назад его обнародовал. Он называется **»Вместо деления умножение»** Найдите в интернете мою статью под этим названием, которую я представил на международной конференции в 2006 году как открытие. Я пишу книгу на эту тему, материал потрясающий. Книга будет по плану состоять из 11 глав. На подступах к этому открытию я в в 1989 г написал статью *»удивительные приключения десятичных дробей»* («Квант», 1989 № 8, с.23-30). В 100 школах Москвы в 1985-1990-х годах я читал лекции на эту тему для старшеклассников. См. также мою статью «А фокусы ли это» в журнале «Математика в школе», 1989 № 5, с.110-113. Ещё в древних индийских ведах 4000 лет назад кое-что об этом методе знали. Тот, кто найдёт меня, позвоните мне. я познакомлю его с книгой американца, который был рядом с этим открытием, но не увидел его.

Как заменить деление на умножение?

Я знаю, что для этого можно просто умножить делимое на обратную дробь, созданную из самого примера на деление. Предположим, что мы хотим 25 разделить на 5. 25 * 5/25 даст нужный результ в виде простой дроби.

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

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

задан 28 Окт ’12 19:21

мы хотим 25 разделить на 5. 25 * 5/25

Эээ, тут два вопроса, что такое 5. 25 и эта звездочка?

(15 Мар 2:26) mihailm

6 ответов

А зачем делить на 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

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

(28 Окт ’12 22:24) german398

Вы не поняли. Что и на что делится? С какой точностью? Например, только числа в пределах от 1 до 10000. Или любые числа. Приближенно? Или точно? В последнем случае нужно найти период дроби?

Что считать результатом деления 5/3? 1,66666. или 1,7 или 1,67, или 1,667, . или 1,(6) ?

Если бы такой способ знали, его бы изучали в школе.

Если эта задача программистская, то все целые числа ограничены какой-то константой, а все дроби — какой-то точностью.

(28 Окт ’12 22:29) DocentI

Можно привести к знаменателю 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

Чтобы перевести число в двоичную (десятичную, …) систему счисления, нужно поделить его на два (десять, …). Причём не однажды. Я думаю, что исходная задача всё-таки нереалистична. Что значит: за деление — расстрел? Надо дойти с жалобой до ЕСПЧ! Наверняка была какая-то осмысленная задача, которая привела к этой бессмысленной формулировке…

(1 Дек ’16 11:35) abracadabra2

Читайте мою статью «Вместо деления умножение» в интернете

отвечен 29 Янв ’19 20:24

Сам искал ответ на этот вопрос. Умножение — это последовательное сложение. Например 3*4 это 3+3+3+3. То есть технически умножение легко реализуется циклом с постоянным прибавлением одного и того же числа. Нам известно число 3 и сколько итераций мы должны выполнить — 4.

Получается деление — это обратный процесс, который решается через вычитание. Чем мы в школе и занимались, решая в столбик. Сколько раз можно вычесть одно число из другого? Чтобы разделить 12 на 3, надо вычесть из 12 три ровно четыре раза. То есть по сути мы ищем число итераций.

Преобразовать a/(b+c) в какой-то вариант без знаменателя не выйдет, поэтому и решить деление через умножение не получится.

отвечен 14 Мар 21:16

Вопрос очень давно ставился, и сформулирован был «коряво», но суть его ясна. Я бы добавил к сказанному следующее. Разделить число b на число a означает решить уравнение ax=b. Числа a, b можно считать натуральными, хотя это не важно. Частное может находиться точно или приближённо.

Такие уравнения, как и почти любые другие типа x^2=A, x^3=A, . решаются методом половинного деления. Корень уравнения ax=b принадлежит отрезку [1,b]. Делим отрезок пополам, берём его середину, и далее выбираем одну из половинок отрезка. Это достаточно универсальный способ.

(14 Мар 21:38) falcao

Будем говорить честно, в школах у нас паршиво учат: 49 / 7 = 49 * (7 ^ -1)

отвечен 24 Июл ’14 4:51

Здравствуйте

Математика — это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

задан
28 Окт ’12 19:21

показан
27114 раз

обновлен
15 Мар 2:26

Научный форум dxdy

Замена целочисленного деления на умножение и сдвиг (теория)

Замена целочисленного деления на умножение и сдвиг (теория)
25.12.2015, 09:22

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

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

— Ссылка на архив с презентацией и программой для подбора параметров:
https://yadi.sk/d/5PLnPY0KmTaXz

Какие ещё моменты стоило упомянуть в лекции? С чем вы согласны или не согласны? Полезна ли была лекция?

Re: Замена целочисленного деления на умножение и сдвиг (теория)
25.12.2015, 09:51
А для чего эта замена нужна или может понадобиться?
Re: Замена целочисленного деления на умножение и сдвиг (теория)
25.12.2015, 10:16

Делить на константу бывает дольше, чем проделать те манипуляции. В былые времена так нередко преобразовывали при оптимизации. Сейчас, кажется, распространённые компиляторы C/C++ (и чего-нибудь ещё) делают такое преобразование, если в нём есть смысл, автоматически; точно не скажу.

Re: Замена целочисленного деления на умножение и сдвиг (теория)
25.12.2015, 10:44

Можно добавить ссылки на «Алгоритмические трюки для программистов» Уоррена мл. Там рассматривается эта задача.

Re: Замена целочисленного деления на умножение и сдвиг (теория)
25.12.2015, 11:26

Последний раз редактировалось buti 25.12.2015, 11:26, всего редактировалось 1 раз.

Цитата:
А для чего эта замена нужна или может понадобиться?

На некоторых процессорах (Intel и AMD точно из их числа) такая замена может сильно ускорить деление.

На процессорах, которые не поддерживают умножение с расширением результата до 64 бит это вряд ли даст выигрыш, но тут надо проверять, а практики ещё не было.

Re: Замена целочисленного деления на умножение и сдвиг (теория)
25.12.2015, 17:19

Последний раз редактировалось Dmitriy40 25.12.2015, 17:21, всего редактировалось 1 раз.

mihailm в сообщении #1085681 писал(а):
А для чего эта замена нужна или может понадобиться?

Добавлю, на некоторых процессорах (многие микроконтроллеры) команда умножения есть, а команды деления нет.

buti в сообщении #1085709 писал(а):
На некоторых процессорах (Intel и AMD точно из их числа) такая замена может сильно ускорить деление.
Да, а ещё тогда можно будет воспользоваться MMX/SSE/AVX расширениями и ещё более ускорить программу.
Re: Замена целочисленного деления на умножение и сдвиг (теория)
25.12.2015, 20:50

buti
Ну что же. Четыре с минусом.

Лекцию всю переписать. Теорию можете взять отсюда
http://www.agner.org/optimize/optimizing_assembly.pdf
Во-вторых когда пишете статью в конце надо приводить источники информации.

Re: Замена целочисленного деления на умножение и сдвиг (теория)
30.12.2015, 05:55

Последний раз редактировалось bondkim137 30.12.2015, 05:55, всего редактировалось 1 раз.

Dmitriy40 в сообщении #1085777 писал(а):

Добавлю, на некоторых процессорах (многие микроконтроллеры) команда умножения есть, а команды деления нет.

ARM-ы все старые (аля ARMv4) не умеют делить. и практически все компиляторы при делении на константу прибегают к такому трюку. программисты раньше также прибегали, когда делить приходилось на условную константу

Деление заменить смещением(сдвигом)

Подскажете как поделить на 10,100,1000 любого числа ‘a’ со смещением(сдвигом)? Целочисленный int (остаток от деления не важен).

Отслеживать
13.7k 12 12 золотых знаков 43 43 серебряных знака 75 75 бронзовых знаков
задан 17 июл 2016 в 23:17
Alex Bigalo Alex Bigalo
37 1 1 серебряный знак 4 4 бронзовых знака

Если это в целях оптимизации, то зря, просто напишите a/100 , компилятор сделает все наилучшем способом.

18 июл 2016 в 1:06
Компилятор иногда -тупое животное. Я для себя хочу понять есть ли способ деления по сдвигу.
18 июл 2016 в 4:53
Если вам дан исчерпывающий ответ, отметьте его как верный (галка напротив выбранного ответа).
19 июл 2016 в 7:42

1 ответ 1

Сортировка: Сброс на вариант по умолчанию

0.1₁₀ = 0.0001100110011001₂. То есть деление на 10 — это 1 / 16 + 1 / 32 + 1 / 256 + 1 / 512 + .

А если серьезно — возьмите книгу Уоррена «Алгоритмические трюки для программистов», там есть глава 10, «Целое деление на константы». Там много стоящего.

То же деление на 10:

unsigned divu10(unsigned n) < unsigned q, r; q = (n >> 1) + (n >> 2); q = q + (q >> 4); q = q + (q >> 8); q = q + (q >> 16); q = q >> 3; r = n - q * 10; return q + ((r + 6) >> 4); // return q + (r > 9); >