Интересная задача. Остаток от деления умножением

← →
DevilDevil © (2013-07-25 17:53) [0]

Все знают, что целочисленное деление можно сэмулировать умножением и сдвигом. На уровне ассемблера - одним умножением (забрать результат в EDX)

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

Разумеется можно сначала найти частное. Потом домножить на делитель и результат вычесть из делимого. Но хочется надеяться на чудо в виде какого-то более эффективного решения :)

← →
Rouse_ © (2013-07-25 19:19) [1]

Ты IDIV хочешь через IMUL проэмулировать?

← →
Rouse_ © (2013-07-25 19:28) [2]

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

По крайней мере аналог INC EAX через NOT EAX/ NEG EAX эт точно оттуда

← →
DevilDevil © (2013-07-25 22:49) [3]

> Rouse_ © (25.07.13 19:19) [1]
> Ты IDIV хочешь через IMUL проэмулировать?

думаешь не получится ?

> Rouse_ © (25.07.13 19:28) [2]
> Поищи в инете букварь "Алгоритмические трюки для программистов"

спсб
зазырю

← →
megavoid © (2013-07-25 22:57) [4]

Академически и правда интересно стало, а что же противопоставить SHR (хотя и занимаюсь скриптовым вебом)

Вбил "assembler get the div", чертыхнулся, вбил "assembler get the mod" :)
первые два резалта - оно?
http://stackoverflow.com/questions/8021772/assembly-language-how-to-do-modulo
http://stackoverflow.com/questions/8231882/how-to-implement-the-mod-operator-in-assembly

The DIV instruction (and it"s counterpart IDIV for signed numbers) gives both the quotient and remainder (modulo). DIV r16 dives a 32-bit number in DX:AX by a 16-bit operand and stores the quotient in AX and the remainder in DX.

mov dx, 0 mov ax, 1234 mov bx, 10 div bx ; Divides 1234 by 10. DX = 4 and AX = 123

А уж оптимизировать сие - это именно к Rouse :)

← →
DevilDevil © (2013-07-25 23:18) [5]

> megavoid © (25.07.13 22:57) [4]

div выполняется где то 20-30 тактов
а mul 3 такта

← →
Sha © (2013-07-25 23:29) [6]

> Все знают, что целочисленное деление можно сэмулировать умножением и сдвигом...

Мы умножаем число примерно на (2^n)/m,
а затем выдвигаем дробную часть результата.

Если вместо сдвига отбросить целую часть при помощи and,
затем умножить на m, а только потом выдвинуть хвост,
то по идее мы получи модуль. Но так мы получим большую погрешность.

Тот же самый результат, но без погрешности, как раз дает указанный вариант

> Разумеется можно сначала найти частное.
> Потом домножить на делитель и результат вычесть из делимого.

При этом ничто не мешает найти частное умножением и сдвигом.

← →
megavoid © (2013-07-25 23:30) [7]

Но ведь и конвейеры нынче крутые, глядишь, оно и само там соптимизирует как лучше

← →
Sha © (2013-07-25 23:32) [8]

Разумеется, для особых чисел (2^n и близких к ним) существуют особые алгоритмы.

← →
DevilDevil © (2013-07-26 09:38) [9]

> megavoid © (25.07.13 23:30) [7]
> Но ведь и конвейеры нынче крутые, глядишь, оно и само там
> соптимизирует как лучше

Поэтому программы, которые летали на вторых пентиумах, по мере развития стали тормозить на i3. Подход неверный

← →
Rouse_ © (2013-07-26 10:03) [10]

> DevilDevil © (25.07.13 22:49) [3]
> думаешь не получится ?

Получиться то получится, а вот будет ли быстрее - тут не уверен...

← →
DevilDevil © (2013-07-26 15:52) [11]

> Rouse_ © (26.07.13 10:03) [10]

> Получиться то получится, а вот будет ли быстрее - тут не
> уверен...

я честно говоря ещё не пробовал, но почему сомнения ?
даже если придётся делать особые манипуляции в случае знака - всё решаемо командами типа mov/add/sub/lea/movcc/sar - т.е. даже без прыжков. По тактам мне кажется сложно будет набрать 20-30

← →
Inovet © (2013-07-26 17:27) [12]

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

А уж если вспомнить 8080, так совсем радоваться только остаётся без всяких таблеток.

← →
Rouse_ © (2013-07-26 17:28) [13]

> DevilDevil © (26.07.13 15:52) [11]
> я честно говоря ещё не пробовал, но почему сомнения ?

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

← →
asail © (2013-07-26 18:04) [14]

> DevilDevil © (26.07.13 09:38) [9]

> Поэтому программы, которые летали на вторых пентиумах, по
> мере развития стали тормозить на i3. Подход неверный

Это какие такие программы? Сильно сомневаюсь, что Фотошоп 3 на П2 произвел бы одну и ту же операцию над одним и тем же изображением быстрее, чем CS4 на i3...
И подход абсолютно верный в 99% случаев. Вот смотри... Ты и твой конкурент решили написать одну и туже софтину. Он написал за год, не сильно заморачиваясь оптимизацией. Получилось вполне терпимо в плане скорости и он начал ее распространять. Ты же, вылизывал производительность 3 года, и в результате получил софтину значительно превосходящую конкурента по производительности. Но! Фиг ты ее теперь продашь, бо все твои потенциальные клиенты уже сидят на софте конкурента и платить дополнительно за тот же функционал им уже не охота. В остатке имеем, что ты вложил средств в 3 раза больше конкурента, а выхлоп - 0. А конкурент летает на собственном самолете на канары...

← →
DevilDevil © (2013-07-26 18:10) [15]

> asail © (26.07.13 18:04) [14]

да не нужно далеко ходить
Kaspersky, Opera, IE, Chrome, Delphi

заканчивай холивар
о плюсах и минусах качественной разработки и количественной все давным давно слышали. Оптить, конвейеры крутые, div сделает за 3 такта )))). Смешно

← →
asail © (2013-07-26 18:19) [16]

> DevilDevil © (26.07.13 18:10) [15]

> да не нужно далеко ходить Kaspersky, Opera, IE, Chrome, Delphi

А что с ними не так? Ну, за касперского не скажу, а с остальными-то? Да, подтормаживают броузеры... Но, не кажется ли тебе, что связанно это в большей степени с увеличившейся сложностью контента? Страницы, которые ИЕ9 грузит 30 сек, ИЕ5 не смог-бы открыть вообще!
Ты еще досовский едит сравни с Ворд 2010... Первый, конечно, текстовый файлик на 2кб откроет быстрее... :)

> заканчивай холивар

Да ладно. Удачи! :)

← →
DevilDevil © (2013-07-26 18:21) [17]

> asail © (26.07.13 18:19) [16]

нет, есть и обратные случаи
горячо мной любимый Windows 7 например
вот это действительно показатель как надо работать. Наверное наняли программистов, которые знают, сколько тактов делается div

← →
Rouse_ © (2013-07-26 18:34) [18]

> DevilDevil © (26.07.13 18:21) [17]
> нет, есть и обратные случаи
> горячо мной любимый Windows 7 например
> вот это действительно показатель как надо работать.

Немного сумбурно. А ХР чем плох? Мне обе системы нравятся, но вот каких-то там скачков мегапроизводительности я чей-то не наблюдал.

← →
Rouse_ © (2013-07-26 18:37) [19]

ЗЫ: даже наоборот, некоторые оконные контролы начали работать с тормозами (даже веточка была, щас сходу не найду но что-=то там по поводу SysListView32 было - моргает/дергается в services.msc кажется и еще куче программ)

← →
DevilDevil © (2013-07-26 18:58) [20]

> Rouse_ © (26.07.13 18:34) [18]

Дизайн, юзерфрендли, работа с диском (слабое место в бытовых условиях)
В итоге получалось приятнее, удобнее, быстрее
Так надо работать

← →
DevilDevil © (2013-07-26 18:58) [21]

* получилось

← →
Rouse_ © (2013-07-26 19:09) [22]

> DevilDevil © (26.07.13 18:58) [20]
> > Rouse_ © (26.07.13 18:34) [18]
>
> Дизайн, юзерфрендли, работа с диском (слабое место в бытовых
> условиях)

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

← →
DevilDevil © (2013-07-26 19:18) [23]

ну хз
Delphi XE то у тебя надеюсь стало работать медленнее, чем Delphi 7 в былые времена )

← →
Rouse_ © (2013-07-26 19:28) [24]

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

← →
Inovet © (2013-07-26 19:59) [25]

> [22] Rouse_ © (26.07.13 19:09)
> я уже 4 диска поменял за 3 года

Ничёсе. Магнитгых, не на флеш-памяти?

← →
Sha © (2013-07-26 20:22) [26]

> Наверное наняли программистов, которые знают, сколько тактов делается div

у нас даде в начальной школе знают,
сколько надо вычитаний при делении столбиком

← →
Rouse_ © (2013-07-26 20:40) [27]

> Inovet © (26.07.13 19:59) [25]
> > [22] Rouse_ © (26.07.13 19:09)
> > я уже 4 диска поменял за 3 года
>
> Ничёсе. Магнитгых, не на флеш-памяти?

обычных, не SSD

← →
DevilDevil © (2013-07-27 00:42) [28]

в книге "Алгоритмические трюки для программистов" я не нашёл ничего по поводу остатка кроме стандартного Делимое - Частное * Делитель

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

← →
Cii (2013-07-27 00:51) [29]

а какой?
на ZX80 тоже специфический был, команд, регисторов меньше, а суть одна.

RISC

Ребятки, что же такое получается
Получается мы, мастера и участники форума, не знаем, как оптимизировать в своих программах деление на константу. Современные С++ компиляторы это делают автоматически, а Delphi увы нет.

Бог с ним с остатком от деления. Предлагаю разобраться с алгоритмом деления на константу. На повестке дня:
- деление Cardinal на константу Cardinal
- деление Integer на константу Integer

Пока мои опыты должным успехом не увенчались.
Но вместе с тем удалось добыть код нахождения "магической константы" и сдвига. (опять таки не очень ясно как их применять)

type TDivideInfo = record Magic: integer; Shift: integer; end; function FindDivideInfo(D: integer): TDivideInfo; const two31 = dword(1 shl 31); var p: integer; ad, anc, delta, q1, r1, q2, r2, t: dword; begin ad := abs(D); t := two31 + dword(D shr 31); anc := t - 1 - t mod ad; p := 31; q1 := two31 div anc; r1 := two31 - q1*anc; q2 := two31 div ad; r2 := two31 - q2*ad; while (true) do begin p := p + 1; q1 := 2*q1; r1 := 2*r1; if (r1 >= anc) then begin q1 := q1 + 1; r1 := r1 - anc; end; q2 := 2*q2; r2 := 2*r2; if (r2 >= ad) then begin q2 := q2 + 1; r2 := r2 - ad; end; delta := ad - r2; if not ((q1 < delta) or ((q1 = delta) and (r1 = 0))) then break; end; Result.Magic := q2 + 1; if (D < 0) then Result.Magic := -Result.Magic; Result.Shift := p - 32; end;

Слушаю предложения и результаты тестов

чё, никому не интересно быстрое деление ?
<S>неужели мастера готовы мириться с 30 тактами деления</S>

те, кому интересно, давно уже "прошли" деление )

> Sha © (29.07.13 11:37) [33]
> те, кому интересно, давно уже "прошли" деление )

по опыту предыдущих лет с подобными высказываниями
таки нет
недомастерам интереснее газонокосилки и водопровод

Глобально поднятый мною вопрос не из мира фантастики. Компиляторы от MS, Intel, GNU, Apple - 100500 лет уже выполняют эту работу автоматически. И отсутствие интереса к этому вопросу наталкивает меня на достаточно неприятные выводы, в которые мне не хочется верить. Хочется верить, что здесь есть программисты, а не кнопкошлёпы

> чё, никому не интересно быстрое деление ?

быстрее чем что?

> Компиляторы от MS, Intel, GNU, Apple - 100500 лет уже выполняют
> эту работу автоматически.

Оть тебе компилятор от MS

A = A / 3; 00E813E0 mov eax,dword ptr [A] 00E813E3 cdq 00E813E4 mov ecx,3 00E813E9 idiv eax,ecx 00E813EB mov dword ptr [A],eax

а это вариант на Delphi

Unit2.pas.37: A := A div 3; 005B233A B903000000 mov ecx,$00000003 005B233F 8B45F4 mov eax,[ebp-$0c] 005B2342 99 cdq 005B2343 F7F9 idiv ecx 005B2345 8945F4 mov [ebp-$0c],eax

не наблюдаю разницы...

> отсутствие интереса к этому вопросу наталкивает меня на достаточно неприятные выводы

когда надо, интерес присутствует:
http://www.guildalfa.ru/alsha/node/6

> Sha © (29.07.13 15:06) [37]

а так не канает ?

function IncDay(const DateTime: TDateTime; NumberOfDays: Integer): TDateTime; begin Result := DateTime + NumberOfDays; end;

да ты че?

> Rouse_ © (29.07.13 14:44) [35]
> Оть тебе компилятор от MS

Оть тебе GCC

int DLL_EXPORT IntTest(int X) { return X / 3; } mov ecx, [esp+arg_0] mov edx, 55555556h mov eax, ecx imul edx sar ecx, 1Fh sub edx, ecx mov eax, edx retn unsigned DLL_EXPORT DwordTest(unsigned X) { return X / 3; } mov edx, 0AAAAAAABh mov eax, [esp+arg_0] mul edx shr edx, 1 mov eax, edx retn

Интересная задача. Остаток от деления умножением Найти похожие ветки