Возведение числа в степень... (возможные варианты и их улучшение)

Вот убей) - не понимаю зачем читать е с конца, а насчет кол-ва циклов если уж нужно, то да их можно на 1-цу уменьшить, а в конце функи написать.

Код (Text):

1. v*=v;
2. return res*v;

 

2UbIvItS
>> Вот убей) - не понимаю
Ну, раз до сих пор не понял то я тебе объяснить видимо не смогу.

>> зачем читать е с конца
Есть такое слово - оптимизация.

>> насчет кол-ва циклов если уж нужно
Нужно разумеется. Зачем выполнять совершенно лишнюю работу?

Код (Text):

1. v*=v; <-- это лишнее, оно и так у тя вычислится в конце цикла. А если циклов - 0 то вычислять и не надо :))
2. return res*v;

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

 

Вот канонический вид:

Код (Text):

1. int pow (int v, int e)
2. {
3. if(e==0) return 1;
4. if(e==1) return v;
5.     int res = 1;
6.  
7.     int loop = _bit_scan_reverse (e);
8.     for(int i=0; i<loop; i++)
9.     {
10.         if (e & (1<<i))  
11.             res *= v;
12.         v *= v;
13.     }
14.     return res * v;
15. }

теперь давай посмотрим A^14 на твоем алгосе: binary(14)= 1110
//1
res=v // вот уже неправильно

 

Да, я не идеален, а ты покажи идеальных))

P. S

Понял)) что ж не плохо), но мой вариант для меня как - то более привычней), хотя на одну переменную он проигрывает

 

UbIvItS
>> теперь давай посмотрим A^14 на твоем алгосе: binary(14)= 1110
Давай:

Код (Text):

1. loop = 3;// 1110
2. res = v;
3. // res = v = v^1
4.  
5. // 1
6. res *= res;
7. if (e & (1<<2)) res *= v;
8. // res = (v ^ 2) * v = v^3
9.  
10. // 2
11. res *= res;
12. if (e & (1<<1)) res *= v;
13. // res = ((v ^ 3) ^ 2) * v = v^7
14.  
15. // 3
16. res *= res;
17. if (e & (1<<0)) res *= v;
18. // res = (v ^ 7) ^ 2 = v^14

>> res=v // вот уже неправильно
Ёмкое заявление...
Что именно неправильно? :rolleyes:

>> Да, я не идеален, а ты покажи идеальных
Не в идеале дело, просто ты спешишь делать выводы либо не подумав и не проанализировав код, либо плохо это сделав.

>> Понял
Ну и слава Б-г.

 

Вообще, по-своему скромному опыту замечу, что есть много людей, кои не понимают мои алгосы с первого и даже с n -го раза, но я не спешу их обвинять в бездарности)) - у каждого башка забита чем - то своим и быстро в ехать в суть не всегда выходит.

 

Ну что, горячие финские парни, выговорились
Начнем с того, что код UbIvItS, вовсе не "канонический" и никакого _bit_scan_reverse тут делать не нужно. Канонический вид выглядит примерно так

Код (Text):

1. int pow (int v, int e)
2. {
3.   int res = 1;
4.   while (e)
5.   {
6.     if (e & 1)  
7.       res *= v;
8.     v *= v;
9.     e = e >> 1;
10.   }    
11.   return res;
12. }

Во-вторых, утверждения CreatorCray о премуществах его варианта являются чисто теоретическими из области абстрактной сложности алгоритмов - раз на одну операцию меньше значит быстрее. На самом деле это не так. Во-первых, _bit_scan_reverse реализуется инструкцией bsr, которая почти на всех процессорах (кроме первых P4) выполняется дольше умножения, а в AMD64 намного дольше. Во-вторых, в "каноническом" алгоритме умножения res*=v и v*=v являются независимыми и могут выполняться с перекрытием на 1 такт. В варианте CreatorCray все умножения зависимы и могут выполняться только последовательно, а латентность целочисленного умножения составляет 3-4-10-14 тактов в зависимости о проца

 

leo, реально красиво - ты меня смог удивить - снимаю шляпу, спасибо.

 

leo
Мой алго писался для больших чисел. Где умножение - дорогая операция, сдвиг - дешевле, но тоже дорог, а BSR операция дешева.

Затем, сравнение скорости алгоримов (компилено ICC 9.1 /QxP)
функции pow обявлены как __declspec (noinline)
возводим 2 ^ 31. По асм коду - все честно, без инлайнинга и замены mul->shr.
Честный цикл каждой функции - 0xffffffff раз.
тики на весь цикл:
2168466797
2167000479

разница небольшая.

+ ICC скомпилил примерно вот во что:

Код (Text):

1. PUBLIC   ?pow2$@@YAHHH@Z
2.         mov       eax, DWORD PTR [esp+4]
3.         mov       edx, DWORD PTR [esp+8]
4.         sub       esp, 8
5. $LN42:
6. ;;;     int res = 1;
7. ;;;     while (e)
8.         test      edx, edx
9.         je        $B2$6         ; Prob 10%
10. ; LOE eax edx ebx ebp esi edi
11. $B2$2:                          ; Preds $B2$1
12.         mov       DWORD PTR [esp+4], ebx
13.         mov       DWORD PTR [esp], esi
14.         mov       ecx, 1
15. ; LOE eax edx ecx ebp edi
16. $B2$3:; Preds $B2$3 $B2$2
17. $LN43:
18. ;;;     {
19. ;;;         if (e & 1)  
20.         mov       ebx, edx
21.         and       ebx, 1
22. $LN44:
23. ;;;             res *= v;
24.         mov       esi, eax
25.         imul      esi, ecx
26. $LN45:
27. ;;;         v *= v;
28.         imul      eax, eax
29. $LN46:
30.         cmp       ebx, 0
31.         cmovne    ecx, esi
32. $LN47:
33. ;;;         e = e >> 1;
34.         sar       edx, 1
35. $LN48:
36.         test      edx, edx
37.         jne       $B2$3 ; Prob 82%
38. ; LOE eax edx ecx ebp edi
39. $B2$4:  ; Preds $B2$3
40.         mov       ebx, DWORD PTR [esp+4]
41.         mov       esi, DWORD PTR [esp]
42. ; LOE ecx ebx ebp esi edi
43. $B2$5: ; Preds $B2$4 $B2$6
44. $LN49:
45. ;;;     }    
46. ;;;     return res;
47.         mov       eax, ecx
48.         add       esp, 8
49.         ret
50. ; LOE
51. $B2$6: ; Preds $B2$1                   ; Infreq
52.         mov       ecx, 1
53.         jmp       $B2$5; Prob 100%

т.е. умножение выполняется вообще всегда, установлен бит или нет.
В связи с этим вопрос: что "дороже" conditional jump или imul?
как замечено, ICC всеми силами старается избавляться от conditional переходов.

 

кстати, сравни свой алгос с либой GMP - весьма любопытно, но факт однозначен bsr не нужен)

 

CreatorCray
Мда, хотел я на простом примере отделаться, а с этими cmov пришлось целое исследование замутить. Пол дня убил фиг знает на что

Во-первых, о методике измерений. Гонять такие суперциклы с переключением контекстов само по себе не есть гуд - достаточно по rdtsc замерить 100 или 1000 повторов. К тому же в цикле суммарная задержка получается меньше за счет частичного перекрытия итераций, поэтому для более объективной оценки нужно вводить ложную зависимость итераций, например так

Код (Text):

1.   xor eax,eax
2. @@:
3.   and eax,0  ;<-- ждет завершения предыдущей итерации
4.   add eax,2
5.   stdcall intpow,eax,31
6.   sub ecx,1
7.   jnz @B

Чтобы не мешать все в кучу, для начала подтверждаем тезис о том что независимые imul в стандартном методе выполняются быстрее, чем зависимые в реверс-методе. Используем обычные методы с jcc при постоянном значении e=31 для всех проходов цикла - все jcc отдыхают и штрафов нет. Из таблицы видно, что в этом сл.стандартный метод работает заметно быстрее и тем быстрее, чем больше латентность imul - самая большая разница получается на P4, самая маленькая на AMD64.
Без особого удовольствия переходим к квазислучайным значениям e . Взял для примера e=((i*23) mod 32) or 16 при i=100..1, чтобы число сканируемых бит всегда было одинаково и = 5. С реверсом уже не связываемся, смотрим как себя ведет стандартный метод.
Видим, что рез-ты ес-но ухудшаются и степень ухудшения коррелирует с соотношением латентности imul и штрафа за непредсказанный переход (минимум для P4, максимум для PM и AMD64).
Ясно, что jcc "дороже", чем imul. Но чтобы вовсе избавится от jcc и "всегда выполнять умножение" нужно ввести доп.операции для коррекции результата по условию, а эти операции даются не бесплатно. Проверяем несколько измененный вариант ICC с cmov и получаем для всех процев кроме P4 вполне предсказуемые результаты. В AMD64 и PM латентность cmov мала и соотв-но рез-т получается значительно лучше чем со случайными jcc и несколько хуже чем с предсказуемыми jcc. В P4E латенность cmov очень большая и соответсвенно выигрыш не значителен. А вот загадочный P4 Northwood и вовсе с cmov работает хуже (также как и c setcc,adc,sbb и т.п), поэтому специально для него и его старшего братца P4Е пытаемся заменить cmov на кучку простых ALU-операций. И после некого шаманства (о чудо !) получаем для них "выдающиеся" результаты, хотя нормальные "простые" камни AMD и PM такого изврата ес-но не понимают )
"Вот такие времена..." (С) ВВП

Код (Text):

1. Проц         PM     P4    P4E   AMD64
2. -------------------------------------
3. imul r,r      4     14    10     3     ;латентность imul
4. cmovcc r,r    2      6    ~9     1     ;латентность cmovcc
5. штраф jcc    ~12   ~20   ~30    ~12    ;штраф за непредсказанный переход
6. =====================================  ;тики на цикл из 100 повторений при e=const=31
7. реверс_jcc  4277  17356   8798  4415   ;<- метод обратного сканирования res*=res + res*=d
8. стд_jcc     3545  11204   6112  4012   ;<- стандартный метод
9. разница %   20.6   54.9   43.9  10.0
10. =====================================  ;тики на цикл из 100 повторений e=((i*23) and 31) or 16
11. стд_jcc     6984  13336  10980  7453   ;<- стандартный метод с jcc
12. стд_cmov    4567  15052  10620  4113   ;<- с заменой jcc на cmov  
13. стд_АЛУ     5673   9080   7320  4913   ;<- с заменой jcc на "кучку" АЛУ-операций
14. -------------------------------------
15. PM    - Pentium M,       1.2 ГГц, cpuid=6.11.1
16. P4    - P4 Northwood,    3.2 ГГц, cpuid=15.2.9 (HT Disabled !!!)
17. P4E   - P4 Prescott,     3.0 ГГц, cpuid=15.4.3 (HT Disabled !!!)
18. AMD64 - Athlon 64 3200+, 2.0 ГГц, cpuid=15.95.2

Исходник на фасме

 

leo
Оффтоп
Простите, когда мы увидим Ваши книги? Или они существуют, но я об этом не знаю?

 

leo
>> Мда, хотел я на простом примере отделаться, а с этими cmov пришлось целое исследование замутить. Пол дня убил фиг знает на что
Сорри ) Исследование на самом деле весьма полезное. Так что убил не зря...

Для чисел, которые влазят в регистры проца - да, зависимость умножения хавает все преимущество. Для длинной математики - наоборот.

UbIvItS
>> сравни свой алгос с либой GMP
Не получится - там аналогичный pow только для modular.
Впрочем попробую завтра.

Но bsr и правда не нужен согласен. Я ж алго этот притянул из своей библы - там можно возводить в любую целую положительную степень. Т.е. ни в один регистр проца экспонента не влазит. И shr для нее - дорого. Единственный выход: пробежка по битам, для которой требуется аналог bsr для длинной математики.

 

>> сравни свой алгос с либой GMP
Выдалась свободная минутка - сравнил свой BigNumber::FromPowMod с mpz_powm:

Всё как положено: REALTIME_PRIORITY_CLASS + THREAD_PRIORITY_TIME_CRITICAL + affinity жестко на 2-е ядро
20 раз по 10 вызовов - в конце минимальное время. PQ - произведение простых. E - экспонента RSA для PQ. C - random

Сравнивать BigNumber::FromPow пока не с чем - нет в GMP функции которая экспоненту бы принимала как mpz_t а не как int

 

да, это верно сдвигать здоровый массив веселое занятие)
кстати, у тебя какая gmp, а то в моей нет mpf фунок??

 

UbIvItS
gmp-4.2.1.tar.bz2 слит вчера с http://gmplib.org

 

там на скока знаю сырцы у меня траблы компилить их

 

ну, я .c файлики побросал в проект вижуаловский. Все, что потребовались при компиляции теста.
Впрочем можно в гугле поискать - есть уже готовые собранные lib + h под MSVC.

Я тут с GMP фигею. Хотя может это у меня с головой не в порядке...

Код (Text):

1. void mpz_nextprime (mpz_ptr p, mpz_srcptr t)
2. {
3.   mpz_add_ui (p, t, 1L);
4.   while (! mpz_probab_prime_p (p, 5))
5.     mpz_add_ui (p, p, 1L); // почему +1? Четные числа ведь не могут быть простыми
6. }

 

у меня на msvc скомпилить не вышло - я готовый юзаю, но там нет плавающей точки

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

 

UbIvItS
Я не жалуюсь, мне просто интересно зачем тратить время на проверку четных чисел, которые по-любому делятся на 2 - т.е. не могут быть простыми по определению.

>> в какой области тебе длинная арифа
Да так, плюшками балуюсь... Криптография в основном.