i wrote a procedure to raise a 32 bit number (x) to a power (y),
it seems to work OK except when x=2 and y>20 it gives the wrong answer.
(note: there's no overflow check.)
can someone help?

here's the code fasm style.

``````
mov ecx,[y]     ;y
cmp ecx,0       ;if y<0
jnc iPow_1
mov eax,0       ;result = 0
jmp iPow_Wend1  ;we are finished
iPow_1:
jnz iPow_2      ;if y=0
mov eax,1       ;result = 1
jmp iPow_Wend1  ;we are finished
iPow_2:
mov ebx,1       ;z=1
mov eax,[x]     ;x
cmp ecx,0
iPow_While1:
jle iPow_Wend1  ;while y>0
iPow_While2:
bt ecx,0        ;test for odd/even
jc iPow_Wend2   ;while y is even
sar ecx,1       ;ecx=ecx/2
imul eax        ;x=x*x
jmp iPow_While2
iPow_Wend2:
imul ebx        ;z=z*x
mov ebx,eax
dec ecx
jmp iPow_While1
iPow_Wend1:       ;result left in eax
``````
Posted on 2003-09-28 09:48:15 by jack
I saw a lot of errors there.

mov ecx,
mov eax,
xor ebx,ebx
test ecx,ecx
js done2
inc ebx
jmp short begin
again2:
imul ebx,eax
again:
imul eax
begin:
shr ecx,1
ja again
jb again2
done:
imul ebx,eax
done2:
xchg ebx,eax
Posted on 2003-09-28 10:39:07 by Sephiroth3
``````
mov eax, [x]
mov ebx, [x]
mov ecx, [y]
sub ecx, 1 ; so that carry flag is affected
jna _out
_mult:
imul ebx
dec ecx
jnz _mult
_out:
``````
Posted on 2003-09-28 11:23:27 by roticv
Well, that will take a shitload of time, but ok.
Posted on 2003-09-28 11:32:37 by Sephiroth3
Here are some FPU versions...
http://www.asmcommunity.net/board/index.php?topic=4181&highlight=power

...which leads to this solution:
``````	mov	ebx, _X_
mov	ecx, _Y_
mov	eax, 1
jmp	_a

_2:	imul	ecx, ecx

_a:	shr	ebx, 1
jnc	_3

imul	ecx
_3:	jne	_2

; return 64-bit result``````
Posted on 2003-09-28 12:49:47 by bitRAKE
here's the function in Pascal.

``````
function power1(x:extended;e:integer):extended;
{take x to an integer power}
var z:extended;
begin
z:=1.0;
while e>0 do begin
while not odd(e) do begin
e:=e div 2;
x:=sqr(x);
end;
e:=e-1;
z:=z*x;
end;
power1:=z;
end;
``````

i finally got to work, here's the code. (for integers only, no overflow check)
``````
mov ecx,[y]
cmp ecx,0       ;if y<0
jnc iPow_1
mov eax,0       ;result = 0
jmp iPow_Wend1  ;we are finished
iPow_1:
jnz iPow_2      ;if y=0
mov eax,1       ;result = 1
jmp iPow_Wend1  ;we are finished
iPow_2:
mov ebx,1       ;z=1
mov eax,[x]
cmp ecx,0
iPow_While1:
jle iPow_Wend1  ;while y>0
iPow_While2:
bt ecx,0        ;test for odd/even
jc iPow_Wend2   ;while y is even
sar ecx,1       ;ecx=ecx/2
imul eax        ;x=x*x
jmp iPow_While2
iPow_Wend2:
xchg ebx,eax
mul ebx        ;z=z*x
xchg ebx,eax
dec ecx
jmp iPow_While1
iPow_Wend1:     ;result left in eax
xchg ebx,eax
``````

sorry bitRAKE
did not see your post until after i posted this, i'll test your code:alright:
Posted on 2003-09-28 13:01:46 by jack
This one might work?
``````; X^Y
mov	ebx, _Y_
mov	ecx, _X_
mov	eax, 1
xor	edx, edx
jmp	_a

_1:	imul	ecx
_2:	imul	ecx, ecx

_a:	shr	ebx, 1
jnbe	_2
jc	_1

; return 64-bit result``````
Tested it: 3^24 = 282429536481, hey it works :tongue:
Posted on 2003-09-28 13:19:36 by bitRAKE
thanks bitRAKE, works great :)
Posted on 2003-09-28 13:27:03 by jack
It will still only work if X^Y is below 2^31 when only the highest bit of Y is kept. So, 4^24 won't work for example. Other than that, it's the same as mine.

Here's a version that should work with 64 bits:
``````
mov ecx,[y]
mov eax,[x]
push ebx
push edi
push esi
push ebp
xor ebx,ebx
xor esi,esi
cdq
test ecx,ecx
js done2
inc ebx
jmp short begin
again2:
push eax
push edx
mov ebp,edx
imul ebp,ebx
mul ebx
imul esi,eax
pop edx
pop eax
again:
mov edi,eax
imul edi,edx
mul eax
begin:
shr ecx,1
ja again
jb again2
done:
imul ebx,eax
done2:
xchg ebx,eax
mov edx,esi
pop ebp
pop esi
pop edi
pop ebx
``````
Posted on 2003-09-28 14:25:08 by Sephiroth3
I hope you understand this algo doesn't cover a large range of integers. The number of bits in the result is less than (bits in X) times Y, but is also greater than (bits in X) times (bits in X - 1) times Y/2.
Posted on 2003-09-28 14:41:30 by bitRAKE
``````
cmp ecx,0
jnc iPow_1
``````

The carry flag will never be set. It doesn't matter what ecx is, if you subtract zero from it, the carry will never occur.

The cmp in between the "iPow_2", and "iPow_While1" lables isn't needed because nothing will have changed the flags in between (movs and jmps don't affect the flags).

Personally I'd use "test" rather than "bt" for speed on older processors (bt on the Pentium is slow, but on the PII and above is just as fast as test).

If you replace "jmp iPow_While1" with "jg iPow_While2" then you can remove the "iPow_While1" label, and the following "jle ..." line.

And finally...
You've forgotten to change the register being used in the cases when y is 0 or less to ebx, so the final xchg swaps it out from eax to ebx.

Here's the version I made from your code, it should work identically... I've not tested it as its all a paper exercise (no MASM here to assemble & test it). It also contains a little trick to set the result to 0 or 1 without the extra jump in the case where Y is zero or less.

Note it will fail for y = 080000000h, but all other conditions are fully covered :)
Fixing it for this case is easy, but makes the code look less pretty, and I personally value asthetics higher than correctness :tongue:
``````
mov  ecx, [y]
cmp  ecx, 1
jge  iPow_2

sbb  ebx, ebx
neg  ebx
jmp  iPow_Wend1

iPow_2:
mov  ebx, 1
mov  eax, [x]

iPow_While2:
test ecx, 1
jnz  iPow_Wend2
shr  ecx, 1
imul eax
jmp  iPow_While2

iPow_Wend2:
xchg ebx,eax
mul  ebx
xchg ebx,eax
dec  ecx
jg  iPow_While2

iPow_Wend1:
xchg ebx,eax
``````

Mirno
Posted on 2003-09-28 18:07:27 by Mirno