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

← →
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 тоже специфический был, команд, регисторов меньше, а суть одна.

← →
DevilDevil © (2013-07-27 01:40) [30]

RISC

← →
DevilDevil © (2013-07-27 12:17) [31]

Ребятки, что же такое получается
Получается мы, мастера и участники форума, не знаем, как оптимизировать в своих программах деление на константу. Современные С++ компиляторы это делают автоматически, а 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;

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

← →
DevilDevil © (2013-07-29 11:21) [32]

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

← →
Sha © (2013-07-29 11:37) [33]

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

← →
DevilDevil © (2013-07-29 12:05) [34]

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

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

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

← →
Rouse_ © (2013-07-29 14:44) [35]

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

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

> Компиляторы от 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

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

← →
DevilDevil © (2013-07-29 15:04) [36]

> Rouse_ © (29.07.13 14:44) [35]

-O3

← →
Sha © (2013-07-29 15:06) [37]

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

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

← →
DevilDevil © (2013-07-29 15:13) [38]

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

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

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

← →
Sha © (2013-07-29 15:13) [39]

да ты че?

← →
DevilDevil © (2013-07-29 15:21) [40]

> 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

← →
Rouse_ © (2013-07-29 15:27) [41]

> DevilDevil © (29.07.13 15:21) [40]

А смысл то какой? Дельфя всеравно все будет по старинке генерировать.

← →
DevilDevil © (2013-07-29 15:31) [42]

> Rouse_ © (29.07.13 15:27) [41]

> А смысл то какой? Дельфя всеравно все будет по старинке
> генерировать.

нет, если заменять деление на умножение со сдвигом
или перейти на асм

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

← →
Rouse_ © (2013-07-29 16:14) [43]

> Суть в том, чтобы как минимум знать, как это можно применить
> на практике.

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

← →
DevilDevil © (2013-07-29 16:31) [44]

Ни в коем случае не нужно оптимизировать всё и вся. Очевидно, бывают задачи, в которых приходится обрабатывать большой объём данных и производить различные вычисления, такие как деление например. Приведённый мной код сводит 30 тактное деление к операциям в 6 (ну 7-8 максимум) тактов. Говорить, что оптимизировать деление в программах не нужно - достаточно опрометчиво; ибо операция распространённая и отжирает немеряно тактов.

> а если просто заменить деление в коде - достаточно через
> asm вставку произвести изменения, раз уж так хочется.

в [31] как раз и поднят этот вопрос. Ибо что именно писать в "asm вставку" общественности не известно :). Можно конечно скомпилировать хорошим С++ компилятором и посмотреть у него в дизассемблере... но как то это не по мастерски что ли. Имхо

← →
Павиа (2013-07-29 16:35) [45]

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

← →
Inovet © (2013-07-29 16:37) [46]

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

Ну, нестандартая конструкция нужна, видимо, поэтому забили.

← →
Inovet © (2013-07-29 16:40) [47]

> [44] DevilDevil © (29.07.13 16:31)
> общественности не известно :).

Ладно, смайлик стоит. Сочтём за юмор.

← →
DevilDevil © (2013-07-29 16:42) [48]

> Павиа (29.07.13 16:35) [45]
> Во первых твои ответы легко гуглится.

ну так скопируй из гугла да приведи сюда
чтобы эти "формулы" не имели погрешностей; чтобы результат деления эмулировался однозначно

> Что касается замены сдвигов, то оно всем известно. И где надо используется.
> Вот только там где надо это это от силы один случай из 1000.

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

> Преждевременная оптимизация это зло в квадрате.
а современные конвейеры выполняют div за три такта
знаем, слышали :)

← →
Павиа (2013-07-29 16:43) [49]

> Почему нет конструкции для получения результатов этих двух
> двух операций вместе

Как это нету в модуле math лежит если не путаю divmod

← →
DevilDevil © (2013-07-29 16:44) [50]

> Inovet © (29.07.13 16:37) [46]
> Меня как-то занимал вопрос. Вот есть деление по модулю и
> целочисленное деление. Почему нет конструкции для получения
> результатов этих двух двух операций вместе, раз уж они одной
> процессорной инструкцией реализованы, да и не только инструкцией
> - по логике деления остаток всё равно где-то хранится.

справку надо читать, а не курить
div возвращает и частное и остаток

> Inovet © (29.07.13 16:40) [47]
> Ладно, смайлик стоит. Сочтём за юмор.

даже не знаю как комментировать :)
может ты просто не понял вопрос ?

← →
Павиа (2013-07-29 16:48) [51]

> а современные конвейеры выполняют div за три тактазнаем,
> слышали :)

Нет больше 9 но меньше 30.

> чтобы эти "формулы" не имели погрешностей; чтобы результат
> деления эмулировался однозначно

http://www.agner.org/optimize/optimizing_assembly.pdf
страница 140. В интернетах есть и русский перевод.

← →
DevilDevil © (2013-07-29 16:49) [52]

> Павиа (29.07.13 16:43) [49]

> Как это нету в модуле math лежит если не путаю divmod

да, но он убогий
возвращает только word-ы если не ошибаюсь
вообще мне кажется компилятор сам должен распознавать ситуации, когда в коде рядом располагаются и div и mod на одних и тех же операндах

← →
Павиа (2013-07-29 16:50) [53]

> даже не знаю как комментировать :)может ты просто не понял
> вопрос ?

Таки по поводу труб. Текут сегодня должны были почсенить. Но что-то мне не нравиться как счётчик поставили так течь начали. Уже 2 раз сантехника вызываем.

← →
DevilDevil © (2013-07-29 17:00) [54]

> http://www.agner.org/optimize/optimizing_assembly.pdf
> страница 140. В интернетах есть и русский перевод.

неплохая отправная точка
когда я листал этот документ - увидел только оптимизации с плавающей точкой
но там муторно написано. используется shr вместо sar, imul вместо mul (для unsigned). Милости прошу - отвечай на вопрос [31]. Будем тестировать

← →
Inovet © (2013-07-29 17:07) [55]

> [49] Павиа (29.07.13 16:43)
> divmod

Не, то процедура ещё и асм, теряется весь смысл. Надо,чтобы по месту работало типа инлайн бы была.

← →
Inovet © (2013-07-29 17:11) [56]

> [50] DevilDevil © (29.07.13 16:44)
> div возвращает и частное и остаток

Ты о каком div?

← →
Inovet © (2013-07-29 17:11) [57]

> [50] DevilDevil © (29.07.13 16:44)
> может ты просто не понял вопрос ?

Всё я понял.

← →
Inovet © (2013-07-29 17:13) [58]

Я вот как раз сейчас услышал один принцип:
"Принцип Боба. Когда у Боба есть проблемы со всеми, главной проблемой обычно является сам Боб."

← →
DevilDevil © (2013-07-29 17:21) [59]

> Павиа
> Таки по поводу труб. Текут сегодня должны были почсенить.
> Но что-то мне не нравиться как счётчик поставили так течь
> начали. Уже 2 раз сантехника вызываем.

> Нет больше 9 но меньше 30.

http://www.agner.org/optimize/instruction_tables.pdf

у Bobcat mul/imul от 1 до 4 тактов. div/idiv - от 27 до 81
Sandy Bridge: 1-2 и 11-84 соответственно

а в каком мануале ты видел, что меньше 30 ?
не в инструкции к счётчику воды случайно ?

← →
DevilDevil © (2013-07-29 17:30) [60]

> Inovet © (29.07.13 17:07) [55]
>
> Не, то процедура ещё и асм, теряется весь смысл. Надо,чтобы
> по месту работало типа инлайн бы была.

Вот как это выглядит в цивилизованных компиляторах

int DLL_EXPORT DivModTest(int X, int Y) { return (X / Y) + (X % Y); } mov eax, [esp+arg_0] cdq idiv [esp+arg_4] add eax, edx retn

← →
Sapersky (2013-07-29 17:46) [61]

84 такта - это r64... вроде редко нужно делить что-то именно 64-битное.

DIVPS (SSE) - 10-14 тактов, 4 числа за раз, в расчёте на 1 число около 3 тактов.
RCPPS (приближённое 1/x) - 5 тактов, хотя мне в единственном случае применения точности как раз не хватило.

Понятно, что если алгоритм уже заточен под целые, то SSE с плавающей точкой вряд ли имеет смысл, конверсия форматов здорово испортит (а то и вообще убьёт) всё ускорение. С другой стороны, возможно, это повод пересмотреть формат данных:
http://blog.lexa.ru/2011/08/27/o_legacy_i_formatakh_dannykh.html

← →
DevilDevil © (2013-07-29 17:52) [62]

> Sapersky (29.07.13 17:46) [61]

ну так целочисленное деление не равно делению с плавающей точкой
в таком случае вообще делается UN_DIV_CONST = 1/const
вообще без операций деления

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

← →
Sapersky (2013-07-29 19:41) [63]

А что тут детализировать...
Шаманский метод вроде [40] - это конечно замечательно, но если компилятор не поддерживает, нужно каждый раз высчитывать магические числа вручную, и ещё прикидывать какие-то исключения, с которыми это не будет работать.
Уж проще тогда написать UN_DIV_CONST = 65536 div const + умножение со сдвигом, а не хватит точности - пусть будет div, и пофиг сколько тактов.

А если переложить высчитывание магических чисел на комп, то это оправдывается, только если нужно делить массив чисел на одно и то же. У Агнера Фога [51] там дальше есть ссылка на его библиотечку с подобными функциями. Вот это в принципе имеет смысл, можно попробовать... правда делить массив на одно число нужно не так уж и часто.

← →
Inovet © (2013-07-29 19:49) [64]

> [60] DevilDevil © (29.07.13 17:30)
> Вот как это выглядит в цивилизованных компиляторах
>
> int DLL_EXPORT DivModTest(int X, int Y)
> {
> return (X / Y) + (X % Y);
> }
>
> mov eax, [esp+arg_0]
> cdq
> idiv [esp+arg_4]
> add eax, edx
> retn

Вот как это выглядит в Builder XE4
struct tdiv_test { int quot; int rem; tdiv_test(int q, int r) {quot = q; rem = r;} }; inline __fastcall tdiv_test div_test(int num, int div) { return tdiv_test(num / div, num & div); } int __fastcall DivModTest(int n, int d) { return n / d + n % d; } int __fastcall DivModTest2(int n, int d) { tdiv_test t = div_test(n, d); return t.quot + t.rem; } @DivModTest$qqrii segment virtual align 2 @@DivModTest$qqrii proc near ?live16385@0: @1: push ebx push esi mov ebx,edx mov ecx,eax ?live16385@16: ; ECX = n, EBX = d mov eax,ecx cdq idiv ebx mov esi,eax mov eax,ecx cdq idiv ebx add esi,edx mov eax,esi ?live16385@32: ; @3: @2: pop esi pop ebx ret @@DivModTest$qqrii endp @DivModTest$qqrii ends _TEXT ends _TEXT segment dword public use32 "CODE" @DivModTest2$qqrii segment virtual align 2 @@DivModTest2$qqrii proc near ?live16386@0: @4: push ebx push esi add esp,-8 ?live16386@16: ; EAX = n, EDX = d mov ecx,eax mov ebx,edx mov esi,ebx and esi,ecx mov eax,ecx cdq idiv ebx mov dword ptr [esp],eax mov eax,esi mov dword ptr [esp+4],eax ?live16386@32: ; EAX = @temp4 mov edx,dword ptr [esp] add edx,eax mov eax,edx ?live16386@48: ; @6: @5: pop ecx pop edx pop esi pop ebx ret @@DivModTest2$qqrii endp @DivModTest2$qqrii ends

← →
Inovet © (2013-07-29 20:19) [65]

> [64] Inovet © (29.07.13 19:49)
> return tdiv_test(num / div, num & div);

А чёрт. Думаю - что за фигня, а оно вон что. Вот так правильно
return tdiv_test(num / div, num % div); _TEXT segment dword public use32 "CODE" @DivModTest2$qqrii segment virtual align 2 @@DivModTest2$qqrii proc near ?live16386@0: @4: push ebx push esi add esp,-8 ?live16386@16: ; EAX = n, EDX = d mov ecx,eax mov ebx,edx mov eax,ecx cdq idiv ebx mov esi,edx mov eax,ecx cdq idiv ebx mov dword ptr [esp],eax mov eax,esi mov dword ptr [esp+4],eax ?live16386@32: ; EAX = @temp4 mov edx,dword ptr [esp] add edx,eax mov eax,edx ?live16386@48: ; @6: @5: pop ecx pop edx pop esi pop ebx ret @@DivModTest2$qqrii endp @DivModTest2$qqrii ends _TEXT ends
Короче, результат не радует. Это с дефолтными установками компилятора на Release, только отключена динамическая RTL, но здесь это пофиг.

← →
Jeer © (2013-07-29 20:34) [66]

TC - "Очередной метр".

← →
Inovet © (2013-07-29 20:39) [67]

> [66] Jeer © (29.07.13 20:34)
> "Очередной метр".

Я бы даже сказал - метроном.:)

← →
DevilDevil © (2013-07-29 21:13) [68]

> Sapersky (29.07.13 19:41) [63]

> Шаманский метод вроде [40] - это конечно замечательно, но
> если компилятор не поддерживает, нужно каждый раз высчитывать
> магические числа вручную

об том и речь

> и ещё прикидывать какие-то исключения, с которыми это не
> будет работать.

не
суть как раз в том, что если делать грамотно - он сработает для любых констант на любом диапазоне чисел (в рамках integer/cardinal конечно). А если подходить упрощено типа 2^16 - тогда естественно погрешность будет. Но зачем, если можно эмулировать деление один в один

> А если переложить высчитывание магических чисел на комп,
> то это оправдывается, только если нужно делить массив чисел
> на одно и то же.

не мне тебе рассказывать, что такое такты. Если в твоём цикле 3 деления реализованы рассматриваемым способом - это уже 90+ тактов экономии на одну итерацию. Взять тот же IntToStr - много делений (в последних версиях на 100).

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

← →
DevilDevil © (2013-07-29 21:15) [69]

> Inovet © (29.07.13 20:19) [65]

> Короче, результат не радует. Это с дефолтными установками
> компилятора на Release, только отключена динамическая RTL,
> но здесь это пофиг.

ну что и требовалось доказать
не понятно только, зачем тебе целая структура для двух значений
используй Point )))

← →
DevilDevil © (2013-07-29 21:16) [70]

Удалено модератором

← →
Jeer © (2013-07-29 21:20) [71]

Удалено модератором

>Сергей Батькович

Не.. я затих:)
Пусть меряет дальше спокойно.

>сейчас то что не так ?

Все нормально.
"Работа мозгом, нежели поршнями, дает больше шансов на повышение интеллекта"

P.S.
Я тоже доставал старших "глупостями", а потом - они становились в очередь за работой ко мне.

> Jeer © (29.07.13 23:45) [77]

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

> Sapersky (29.07.13 19:41) [63]
> У Агнера Фога [51] там дальше есть ссылка на его библиотечку
> с подобными функциями.

да, забавно
думаю взять их за основу, только адаптировать под привычный нам register, а не cdecl :)

смотрю исходники и не могу понять смысл действия
можешь объяснит, что происходит ?

bsr ecx, ebx ; floor(log2(d-1)) ... // ахтунг ахтунг inc ecx ; L = ceil(log2(d)) sub ecx, 1 ; shift count = L - 1 adc ecx, 0 ; avoid negative shift count

как ecx может получиться отрицательный - я чёт не понимаю

← →
Sapersky (2013-07-30 17:40) [80]

Прямо перед bsr строчка:
mov ecx, -1 ; value for bsr if ebx = 0 (assuming bsr leaves dest unchanged if src = 0)
то есть странное телодвижение inc ecx/sub ecx/adc ecx - исключительно для обработки этого случая, чтобы привести ecx к 0.
Хотя в функции предварительного расчёта можно было и явный тест/джамп воткнуть, но автор как настоящий хакер не может не выпендриться...

>если ты хочешь

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

P.S.
Что делать в этой ветке, буду решать я.

> Sapersky (30.07.13 17:40) [80]
> Прямо перед bsr строчка:

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

> Jeer © (30.07.13 18:00) [81]

на смахивает на то, что внимание нужно тебе, а не адептам числодробилок
у них, в отличие от тебя, его предостаточно ))))))))))

Собственно готова реализация, которую можно применить в жизни
И для integer, и для cardinal

1 функция рассчитывает магическую константу и сдвиг для делителя
2 функция - это пример, как имея магическую константу и сдвиг, быстро разделить целое число

Пользуйте кому нужно

// magic-константа и сдвиг для чисел со знаком // Division должен быть больше 0 procedure extract_div_magic(const Divisor: integer; out Magic, Shift: integer); overload; asm cmp eax, 1 jg @norm je @1 ud2 // d <= 0. generate error @1: mov [edx], 1 mov [ecx], 0 ret @norm: push edx dec eax // d-1 mov edx, ecx bsr ecx, eax // floor(log2(d-1)) mov [edx], ecx // shift found mov edx, 1 shl edx, cl lea ecx, [eax+1] // restore d xor eax, eax div ecx pop edx inc eax mov [edx], eax // magic end; // пример как можно эмулировать целочисленное деление на константу // (для чисел со знаком) function integer_div_example(const X: integer; const Magic, Shift: integer): integer; asm // делимое потом ещё понадобится // а свободных регистров пока нет push eax // edx := (int64(eax) * reg) shr 32; // в качестве операндов выступают делимое и magic-константа imul edx // возвращаем делимое (потому что не было свободных регистров) pop eax // корректировка результата (от edx) add edx, eax shr eax, 31 sar edx, cl {в реальных условиях константа} add eax, edx end; // magic-константа и сдвиг для чисел без знака procedure extract_div_magic(const Divisor: cardinal; out Magic, Shift: cardinal); overload; asm cmp eax, 1 jg @norm je @1 ud2 // d = 0. generate error @1: mov [edx], 1 mov [ecx], 0 ret @norm: push ebx push ecx dec eax push edx lea ebx, [eax+1] bsr ecx, eax mov edx, 1 inc ecx xor eax, eax shl edx, cl cmp cl, 20h adc edx, -1 sub edx, ebx div ebx pop edx inc eax sub ecx, 1 mov [edx], eax seta al setae dl neg al movzx edx, dl and al,cl movzx eax, al pop ecx shl eax, 8 pop ebx or eax, edx mov [ecx], eax end; // пример как можно эмулировать целочисленное деление на константу // (для чисел без знака) function cardinal_div_example(const X: cardinal; const Magic, Shift: cardinal): cardinal; asm // делимое потом ещё понадобится push eax // умножаем делимое на Magic --> результат в edx mul edx // возвращаем делимое pop eax // корректировка результата (от edx) sub eax, edx shr eax, cl {в реальных условиях константа} shr ecx, 8 // в реальных условиях не нужно add eax, edx shr eax, cl {в реальных условиях константа} end;

Кроме очевидного профита при делении на константы, сии наработки можно использовать при множественном делении на одно и то же число. Возьмём например код
int MultiDivTest(int X1, int X2, int X3, int X4, int X5, int D) { return (X1 / D) + (X2 / D) + (X3 / D) + (X4 / D) + (X5 / D); }

Не знаю как ICC, но GCC честно выполняет 5 делений. Мы же в "аналогичных" ситуациях можем решить 1 делением и 5 умножениями.

поправочка

*procedure extract_div_magic(const Divisor: cardinal; out Magic, Shift: cardinal); overload; asm cmp eax, 1 ja @norm

Хочу обговорить вот какой вопрос.
По аналогии с [40] ставим своей задачей реализацию деления на константу 3
Вызываем extract_div_magic(3, integer, integer), получаем магическую константу $AAAAAAAB, сдвиг - 1

Получается "функция" деления на 3 будет у нас выглядеть так:
function IntDiv3(const X: integer): integer; asm mov edx, $AAAAAAAB mov ecx, eax imul edx add edx, ecx shr ecx, 31 sar edx, 1 lea eax, [ecx + edx] end;

что меня беспокоит?
да хотя бы то, что компилятор GCC ([40]):
1) использует магическую константу $55555556
2) делает "доведение" в 2 команды, а не в 4 как у нас

и я бы возможно оправдал сей факт фразой "ну просто над GCC гении работают", если бы код в [31] тоже не выдавал константу $55555556. Со сдвигами только не понятно

остаётся вопрос. Что же не учёл Фог ?

Через тесты прогонял?

Подоспел заказанный мной перевод главы Фога о целочисленном делении
http://zalil.ru/34653415

Можете читать на русском

> DevilDevil © (30.07.13 22:52) [85]
> Что же не учёл Фог ?

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

> DevilDevil © (31.07.13 12:14) [88]
> Можете читать на русском

Глянул сразу на последнюю страницу.
В первой же строчке формула не верна.
Лучше все-таки оригинал.

> Sha © (01.08.13 00:17) [89]

ты рассуждаешь как-то... "а может быть, а может и не быть"
подход должен 100% попадание в результат div/idiv
а для этого точно нужно понять принцип и позже применять его
даже если формул несколько формул
надо выбрать оптимальный вариант
(что в частности продемонстрировал GCC)

> Sha © (01.08.13 00:49) [91]
> Я не рассуждаю. Я знаю.

Либо ты плохо знаешь, либо Фог и прочие разработчики ICC/GCC - дилетанты. Одно из двух

Есть еще вариант. Боюсь обидеть.

ты его тоже вряд ли сможешь обидеть

Почитал ещё раз Фога

1) По формулам действительно получается как в [40] (unsigned) - т.е. одно умножение и один сдвиг. Для 3 (как и в GCC) получается константа $AAAAAAAB
2) Но для знаковых (signed) у Фога не написано !
3) В "Алгоритмических трюках для программистов" ("Hacker"s Delight") для чисел со знаком тоже много команд; элегантных решений типа [40] не обозначено. Кстати 1Fh - это 31.
4) Не ясно, почему в asm_lib Фога столько манипуляций для unsigned-чисел

Итог:
Сейчас надо понять, как GCC сделал деление со знаком

> DevilDevil © (01.08.13 00:57) [92]
> > Sha © (01.08.13 00:49) [91]
> > Я не рассуждаю. Я знаю.
> Либо ты плохо знаешь, либо Фог и прочие разработчики ICC/GCC
> - дилетанты. Одно из двух

Сурово...

Чёт я пока не догоняю с делением на отрицательные

> DevilDevil © (01.08.13 00:57) [92]

> Либо ты плохо знаешь, либо Фог и прочие
> разработчики ICC/GCC - дилетанты. Одно из двух

Не из двух, а из трех. Ведь не исключено, что дилетант кто-то третий...

Как думаешь, кто бы это мог быть? Или ты такую возможность даже не рассматриваешь?

PS
Ты с работами Sha знаком? Если нет, то ознакомься и подумай.

> Ты с работами Sha знаком? Если нет, то ознакомься и подумай.

А вот тут и проблема. Как познакомиться с работами Шарахова? :)
Я с ними знаком, ты с ними знаком. Мы с тобой знакомые люди! (с) А.Райкин

> Юрий Зотов © (02.08.13 01:07) [99]

Какое мне дело до работ Шарахова, если человек сомневается в алгоритмах, которые уже не первое десятилетие доказывают свою надёжность

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

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

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