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

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

← →
Jeer © (2013-07-30 18:00) [81]

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

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

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

← →
DevilDevil © (2013-07-30 18:19) [82]

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

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

← →
DevilDevil © (2013-07-30 18:20) [83]

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

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

← →
DevilDevil © (2013-07-30 22:26) [84]

Собственно готова реализация, которую можно применить в жизни
И для 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 умножениями.

← →
DevilDevil © (2013-07-30 22:52) [85]

поправочка

*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. Со сдвигами только не понятно

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

← →
Rouse_ © (2013-07-30 23:04) [86]

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

← →
DevilDevil © (2013-07-30 23:09) [87]

> Rouse_ © (30.07.13 23:04) [86]

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

← →
DevilDevil © (2013-07-31 12:14) [88]

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

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

← →
Sha © (2013-08-01 00:17) [89]

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

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

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

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

← →
DevilDevil © (2013-08-01 00:35) [90]

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

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

← →
Sha © (2013-08-01 00:49) [91]

> DevilDevil © (01.08.13 00:35) [90]

Я не рассуждаю. Я знаю.

← →
DevilDevil © (2013-08-01 00:57) [92]

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

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

← →
Sha © (2013-08-01 01:02) [93]

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

← →
DevilDevil © (2013-08-01 01:09) [94]

> Sha © (01.08.13 01:02) [93]

меня вряд ли может обидеть человек, не понимающий, что такое точность

← →
Sha © (2013-08-01 01:12) [95]

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

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

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. Меня в данном случае интересует топик. И очень показательно, что не смотря на наличие убер мастеров уровня вселенной, тему кроме меня никто не развивает

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