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

Есть маленькая задача "возвести число X в степень Y" я реализовал это так:

Код (Text):

1. function alu_power(x,y:longint):longint;
2. begin
3. y:=y-1;
4.  asm
5.     mov eax, x
6.     mov ecx, 1
7.   @rep:
8.    mul eax, x
9.    inc ecx
10.   cmp y, ecx
11.   jae   @rep
12.   mov @result, eax
13.  end;
14. end;

и вот так:

Код (Text):

1. function fpu_Power(const x, y: extended): extended; //x>0!
2. asm
3.   fld y
4.   fld x
5.   fyl2x
6.   fld st(0)
7.   frndint
8.   fsubr st(0),st(1)
9.   f2xm1
10.   fld1
11.   faddp
12.   fscale
13.   fxch st(1)
14.   fstp st
15. end;

Вопрос как ускорить работу данных вариантов.
И просьба написать примеры с использыванием MMX, SSE,SSE2...

 

вроде цикл dec ecx / jnz @rep будет быстрее...

 

хм...

Код (Text):

1. function alu_power2(x,y:longint):longint;
2. begin
3. y:=y-1;
4.  asm
5.     mov eax, x
6.     mov ecx, y
7.   @rep:
8.    mul eax, x
9.    dec ecx
10.   jnz @rep
11.   mov @result, eax
12.  end;
13. end;

дает прирост 2,44% на P4 3.2Ghz Prescott-2m

 

locki
Логарифмическое возведение для достаточно больших чисел будет быстрее.
То есть 2^4 = (2^2)^2.

Да и зачем:

Есть же loop.

 

ты прав - быстрей, но расход памяти выше, например: число в 1024 бит требует массив в 1024 элементов

 

UbIvItS

Ты имеешь ввиду, если сохранять все предыдущие расчёты.
Да, увеличение скорости увеличивает расход памяти. Но можно сохранять только последнуюю степень, скорость конечно несколько упадёт, но расход памяти всего на одну переменную.

 

Замещение логарифмом ускорения не даст, так как степени маленькие (макс 4),
а числа большие...
А может ускорит процесс введение ммх или SSe?

 

Код (Text):

1.       mov eax,x
2.       mov ebx,eax
3.       muv ecx,y
4. @@:   mul ebx
5.       dec ecx
6.       jnz @b
7.       mov rezult,edx
8.       mov [offset result+4],eax

 

Во - первых, я прогнал)) - кол-во элементов массива зависит от степени, в кою число возводишь.
сохранять последнюю степень - разницы не будет ощущаться на малых степенях, а на больших будет требоваться доп. пересчет.
кстати, ету схемку и для того, чтоб логарифм щимить юзать можно.
хотя, все элементы массива нам не нужны - мы можем заранее просчитать, кои степени a^(2^i) нужны, чтоб получить a^x.

 

locki

Если сможешь распараллелить, то ускорит.
Можно так 2^4:
Делаем параллельно операции.
1)
2*2
2)
2*2
Затем перемножаем эти результаты.
Но смысла это делать не вижу, так как вычислять хоть и параллельно, но одно и тоже довольно странно, уж лучше делать логарифмом.

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

 

на пример нам нужно найти A^73: 73=2^16+2^3+1 - таким образом нам нужны A^64, A^8, A

 

Да, но это для этого конкретного случая, а в общем случае могут понадобиться все степени.

 

какие степени тебе нужны, ты можешь заранее просчитать - это не проблемма.

 

http://www.wasm.ru/forum/viewtopic.php?id=9936

 

Вообще классический алго для возведения в целочисленную степень примерно такой:
псевдокод:
для v > 0, e > 0

Код (Text):

1. int pow (int v, int e)
2. {
3.  int res = v;
4.  
5.  int loop = bsr (e)-1; // bsr - bit scan reverse :)
6.  while (loop--)
7.  {
8.   res *= res; // возводим в квадрат
9.   if (e & (1<<loop))
10.     res *= v;
11.  }
12.  return res;
13. }

И для проверки вспомнил молодость...

Код (Text):

1. int wmain ()
2. {
3.     DWORD v,e,r;
4.  
5.     v = 2;
6.     e = 31;
7.  
8.     _asm
9.     {
10.         mov eax, DWORD ptr [v]
11.         mov esi, eax
12.         mov edi, DWORD ptr [e]
13.         bsr ecx, edi
14.         mov ebx, 2
15.         shl ebx, cl
16.     l1:
17.         jecxz l2
18.         dec ecx
19.         shr ebx, 1
20.  
21.         mul eax
22.  
23.         test edi, ebx
24.         jz l1
25.  
26.         mul esi
27.         jmp l1
28.  
29.     l2:
30.         mov DWORD ptr [r], eax
31.     }
32.     printf ("%u ^ %u = %u\n",v,e,r);
33. }

 

Кстати посмотрел IDA-й код для intrinsic pow из комплекта к Intel C++ 9.1
Убиццо веником! Кода километр %(
Есть 2 версии - одна под SSE, вторая на сопроцессоре.

 

CreatorCray
Да, безусловно эта реализация рулит.
UbIvItS
Заранее считать и хранить ничего не надо, что то я тоже стал забывать простые вещи. -).

 

точней код должен выглядить так:

Код (Text):

1. int pow (int v, int e)
2. {
3.  int res = 1;
4.  
5.  int loop = bsr (e); // bsr - bit scan reverse :)
6.  for(int i=0; i<loop; i++)
7.  {
8.  
9.   if (e & (1<<i))  res *= v;
10.  v *= v; // возводим в квадрат
11.  }
12.  return res;
13. }

 

Так на 1 цикл умножений больше.
Во первых нафига делать абсолютно не нужное умножение на 1?
Проверку на нулевую степень нужно выносить за цикл а не замедлять алго ради него.
Во вторых - зачем делать абсоютно не нужное возведение в квадрат в последнем цикле? Ведь в последнем цикле v *= v уже выполняет никому не нужную работу.

Так что я настаиваю на моем варианте.

 

что здесь не верно:

Код (Text):

1. function mmx_power(x,y:longint):longint;
2. begin
3. y:=y-1;
4.  asm
5.     MOVd     mm0,x
6.     MOVd     mm1,x
7.     mov ecx, y
8.   @rep:
9.    PMULLw mm0, mm1
10.    dec ecx
11.   jnz @rep
12.    movd @result, mm0
13.    emms
14.  end;
15. end;

2^15 считает, а больше ноль выдает( какое-то переполнение что ли?)