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 алгоритм. Если нужно оптимизировать по скорости - то проще начинать именно с таких. Только нужно знать больше информации о входных числах (может быть, например, все числа нечётные?), иначе ничего путёвого не выйдет. Вот, например, числа складывают, а с форматом до сих пор не определились =)
S_T_A_S > "Только нужно знать больше информации о входных числах" > "Вот, например, числа складывают, а с форматом до сих пор не определились =)" Как я понимаю, числа любые unsigned B > 0, A >= B. Поэтому алгоритм может завершиться и за 1-2 шага и за много шагов, и сложений может потребоваться от одного до фиг знает сколько. А по сему конкретных мыслей по оптимизации алгоритма у меня пока нет, а вот некоторый выигрыш по скорости вычислений по алгоритму сложения получить можно. Это просто пример того, какой "фигней" мы маемся по ссылочке, приведенной S_T_A_S_, когда замена 3-х инструкций на 10 может привести к выигрушу по скорости на десятки процентов. В данном случае, идея - в разворачивании внешнего цикла, которая заодно позволяет иcключить лишние регистровые пересылки и получить длинный, но симпатичный и быстрый код. Код (Text): mov ecx,B mov eax,A sub ecx,eax ;это подготовка для цикла @@rep @@rep: add ecx,eax @@eax1: sub eax, ecx ja @@eax1 ;дальше идут 3 одинаковых цикла сложения с чередованием роли регистров eax и ecx jz @@end_c add eax,ecx ;определяем остаток @@ecx1: sub ecx,eax ja @@ecx1 jz @@end_a add ecx,eax @@eax2: sub eax, ecx ja @@eax2 jz @@end_c add eax,ecx @@ecx2: sub ecx,eax ja @@ecx2 jnz @@rep @@end_a: mov ecx,eax @@end_c: mov R,ecx На P4 получается заметный выигрыш по скорости - проверил на нескольких комбинациях чисел с разным числом итераций и короткими и длинными циклами сложения. Но вообще-то, этот пример приведен просто для развлечения. Настоящая оптимизация, видимо зарыта где-то в комбинации двоичного уравновешивания и сложений, поскольку прибавлять сотню раз единицу, чтобы получить 100, выглядит как-то не изящно. PS: А основная проблема как выбрать или угадать, что будет для данных eax и ecx быстрее без лишних сравнений и и условных переходов (о варианте dmit10 с несколькими условиями на каждом шаге мне чего-то даже думать страшно). По-видимому в любом случае будут промахи и придется чем-то жертвовать. Кроме второго приближения с использованием удвоенного значения ecx пока ничего не вижу, да и то смутно.
итак, проделано еще немного копаний в сторону истиньі ) как и ожидалось, при большой разнице между числами результатьі не очень утешительньіе посему бьіл создан симбиоз алгоритма S_T_A_S и Кнута ) просто добавилась проверка на четность и соответсвенньій здвиг итого, все тот же GetTickCount (поправка на 210 милисекунд - само время вьіполнения пустого цикла), все тот же Cel850 ..числа...........S_T_A_S..........S_T_A_S + Knuth ......................................... .777 - 629.........1292..............1562 ...................1332..............1612 ...................1321..............1633 ...................1332..............1632 ......................................... ..777 - 6..........6329..............1703 ...................6499..............1692 ...................6379..............1693 ...................6389..............1672 ......................................... вот так вот, проигрьівая при небольшой разнице, имеем значительньій прирост при большой.. истинна где-то рядом leo результьі на скорую руку З,І, leo 777 - 6 6229 6669 6730 6340 777 - 629 1022 1012 1002 1012 пока біьстрее всех ) но жаль не всегда ) уже зреет коварньій план по написанию симбиоза leo + Knuth )
Вот ссылочка в тему: http://athena.vvsu.ru/docs/science/crypt/crypto/handbook/chap14.pdf Раздел 14.4 Binary gcd algorithm Есть у меня ощущение, что инструкция PSADBW очень хорошо в этом алгоритме смотрится.
