Гм, на С пишется просто: Код (Text): /* a must be >= b */ unsigned gcd(unsigned a, unsigned b) { while(b) { unsigned r = a % b; a = b; b = r; } return a; } Компилятор в режиме самой офуительной оптимизации выдал мне сие: Код (Text): ; _a$ = eax ; _b$ = ecx ; 8 : while(b) test ecx, ecx je SHORT $L8421 $L8420: ; 9 : { ; 10 : unsigned r = a % b; xor edx, edx div ecx ; 11 : a = b; mov eax, ecx test edx, edx ; 12 : b = r; mov ecx, edx jne SHORT $L8420 $L8421: Как по мне, так в test edx, edx/jne SHORT $L8420 нужды нет. Можно было бы просто заменить это jmp. Плоды моих усилий вымучались в: Код (Text): unsigned gcd(unsigned a, unsigned b) { unsigned r = 0; __asm { mov eax, a mov ecx, b again: test ecx, ecx je SHORT end xor edx, edx div ecx mov eax, ecx mov ecx, edx jmp SHORT again end: mov r, eax } return r; } Теперь, собственно, упражнение - максимально оптимизировать скорость. Как по мне, так уже больше некуда, но, может, я ошибаюсь?
imho, вот так будет быстрее: Код (Text): __declspec(naked) unsigned int __fastcall gcd(unsigned int a, unsigned int b) { __asm { mov eax, ecx l1: cmp eax, edx jae l2 xchg eax, edx l2: sub eax, edx jnz l1 retn } }
Может и быстрее, но алгоритм не работает И первая же инструкция мне не понравилась - ты перетираешь значение а!
прошу прощения, не протестил Вот так у меня вроде работает: Код (Text): __declspec(naked) unsigned int __fastcall gcd(unsigned int a, unsigned int b) { __asm { xchg eax, ecx l1: cmp edx, eax jae l2 xchg edx, eax l2: sub edx, eax jnz l1 retn } }
Проверил для 777 и 629, получается 37. Медоленные команды не используются. Код (Text): mov eax, a mov ecx, b @@: mov edx, eax sub eax, ecx jnc @b mov eax, ecx mov ecx, edx jnz @b mov r, eax
S_T_A_S_ Два вопроса. 1) Чей алгоритм быстрее? Твой или green'a? 2) Что это за метка "@@"? И где метка "@b"? Ты пользуешься синтаксисом, которого я не знаю
Сам алгоритм вроде одинаковый, заменили деление вычитанием. У меня не используется xchg, которая довольно медленна и не спаривается с другими командами. Одна команда проверки условия вместо 2х. Нет зависимости по данным, кроме как jnc сразу после sub (зато jnz должен быть предсказан одновременно с jnc). "@@" - это просто анонимная локальная метка, "@b" - значит переход на ближайшую "@@" назад (если "@f" - это вперёд). Я и забыл, что С регается на символы @
volodya > 2) Что это за метка "@@"? И где метка "@b"? Ты пользуешься синтаксисом, которого я не знаю jmp @B или jmp @b - это прыжок назад на ближайшую метку @@: jmp @F или jmp @f - тоже самое, но вперед ЗЫ: нормальный ассемблерный синтаксис.
S_T_A_S_ Твой алгоритм вычисляет наибольший общий делитель, но зацикливается после его нахождения. Вот так работает, правда две команды плюс: Код (Text): mov eax, 10557 mov ecx, 1530 @@: cmp eax,ecx je short Exit mov edx, eax sub eax, ecx jnc @B mov eax, ecx mov ecx, edx jnz @B Exit:
cresta Мог бы и добавить, что ответ в eax :|> А от Код (Text): @@: cmp eax,ecx je short Exit избавиться нельзя? Мне не нравится.
Ой млин.. точно, спасибо косячный вариант запостил Правильно так: Код (Text): mov eax, a mov ecx, b @@: mov edx, eax sub eax, ecx ja @b mov eax, ecx mov ecx, edx jnz @b mov r, eax
А алгоритм green'a для некоторых пар чисел выдаёт ошибочный результат. Я так понял, это зависит от содержимого edx. Если его обнулить перед циклом, то вообще зацикливается. Нельзя ли уточнить, что должно быть в регистре edx перед выполнением цикла?
а вот так алгоритм S_T_A_S_ можно в С-код впаять: Код (Text): __declspec(naked) unsigned int __fastcall gcd(unsigned int a, unsigned int b) { __asm { l: mov eax, edx sub edx, ecx ja l mov edx, ecx mov ecx, eax jnz l ret } }
green Да теперь всё стало на место. Просто volodya изначально передавал через eax/ecx, поэтому подумал, что и у тебя тоже. Усё работает.
Единственное что, я слабо понимаю Код (Text): __declspec(naked) unsigned int __fastcall Зачем использовать ДВЕ конвенции о вызовах? Мало fastcall? А вообще (и правильнее!) заменять это на Код (Text): static inline inline - ежику понятно. static - это то, что надо линкеру, чтобы не искал внешних ссылок. Глянь в коды линухи - там все функции через static.
volodya 1) __declspec(naked) - это фича компилятора MS. Она указывает, что компилятор не должен генерировать никакой отсебятины для ф-ции -- всякие прологи/эпилоги т.е. В данном случае они (прологи/эпилоги) не нужны, и задача ставилась - оптимизировать по скорости. 2) __fastcall - конвенция передачи параметров в ф-цию: первые 2 параметра передаются через ecx и edx, остальные - через стек. С __declspec(naked) это не связано. Да, на данном этапе оптимизации возможно уже есть смысл сделать это ф-цию inline. Тогда в самом деле и naked и __fastcall лишние.
Вы Кнута читали? Там что-то, вроде нечто: Вход eax,ebx Выход eax mov ecx,1 next_step: test eax,eax jz end_loop test ebx,ebx jz end_loop test eax,1 jnz eax_nechet shr eax,1 test ebx,1 jnz next_step shr ebx,1 shl ecx,1 jmp next_step eax_nechet: test ebx,1 jnz ebx_nechet shr ebx,1 jmp next_step ebx_nechet: sub eax,ebx jns next_step neg eax jmp next_step end_loop: sub eax,ebx mul ecx
