cresta
через регистры ecx и edx передаются значения a и b

green

Да теперь всё стало на место. Просто volodya изначально передавал через eax/ecx, поэтому подумал, что и у тебя тоже. Усё работает.

Единственное что, я слабо понимаю

__declspec(naked) unsigned int __fastcall 

Зачем использовать ДВЕ конвенции о вызовах? Мало fastcall? А вообще (и правильнее!) заменять это на

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

dmit10

Кнута мы читали. Это ты топ не читал.

volodya


После замеров времени (милисекундьі):

S_T_A_S_

1332
1372
1332
1352
1311
1352
1352

cresta

1982
1983
1993
1973
1993
1993
2003

green

1572
1602
1563
1592
1582
1592
1582

d0rki
1582
1552
1552
1542
1562
1532
1592
---

Теперь о Кнуте. Вообщето алго циклиться, может у меня только ). Посему немного модифицировал ), думаю Кнут не обидиться, и что имеем ?

2534
2553
2584
2493

Мда.. Видать модификатор из меня хреновіьй (

НО!!! Оригинал (без моих добавок) находит ответ за 741, а потом циклиться и все ((
вот таке результатьі

d0rki

Когда приводят такие замеры, надо указывать ЧЕМ они сделаны и процессор. Иначе мне от этих цифирок ни жарко, ни холодно...

volodya
каюсь. облажал..
вообще-то, я только сейчас увидел дату треда (( и видать не актуально уже..

а тестьі и не несут никакой смьісловой нагрузки, просто - чей бьістрее..

чем - GetTickCount для цикла из 0FFFFFFh повторений
проц - Cel850

а Кнут от dmit10 корректно работает только если второе число есть среди делителей первого или наоборот.

имхо, у Кнута реальньій "вьіигриш" (не знаю, вроде так пишеться )) будет, если разница между числами очень большая, так как он парньіе делит пополам, а способ с циклом уменьшает на второе число.. что не есть гуд

я блин Кнута своего отдал ((( посему и не ясно с етим алго до конца..

просто - чей бьістрее..

Дык и так было ясно, что Стасовский :)
А для серьезных аппликух я буду GMP юзать :)

Я не претендую на то, что приведённый пример работает (не проверял..) =). Я о самом алгоритме: дано a,b Найти НОД(a,b)
Алгоритм не использует деление(div на 186ом, например - 29-44 такта(теоретически(по справочнику)))
d:=1;
Если a чет, b - чет d:=d*2; a:=a/2; b:=b/2;
Если a нечет, b - чет b:=b/2;
Если a чет, b - нечет a:=a/2;
Если a нечет, b - нечет - из большей(a,b) вычесть меньшую

До тех пор, пока a>0 и b>0. Как только a=0 или b=0 d:=d*(a+b).

Сдвиги и вычитания... Так, на мой взгляд должно быстро работать.

dmit10

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

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

P.S. Я в форуме недавно, но порядком удивлён скоростью ответа... Как в чате. Здесь всегда так?

Часто :)

dmit10 > „Поскольку вычитание не сильно уменьшает числа по сравнению с делением“

Это смотря какие числа ;)
например, если A == B, то:

A - B = 0
A / B = 1

Да и за время выполнения одного деления можно далеко не одно вычитание выполнить.

Вообще же, я привёл не самый эффективный, а самый простой imho алгоритм. Если нужно оптимизировать по скорости - то проще начинать именно с таких. Только нужно знать больше информации о входных числах (может быть, например, все числа нечётные?), иначе ничего путёвого не выйдет.
Вот, например, числа складывают, а с форматом до сих пор не определились =)