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.

Try this instead:
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
What about


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
add ebp,edx
imul esi,eax
add esi,ebp
pop edx
pop eax
again:
mov edi,eax
imul edi,edx
add edi,edi
mul eax
add edx,edi
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