hello,

some of you may be familiar with the algorithm:

int n = ...;

while(n > 1){
if( (n & 1) == 0 )
n >>= 1;
else
n = n * 3 + 1;
}


the idea is to prove that this loop will terminate for values of n > 1.

i am trying to express it in assembly but cannot get it, here is my
attempt:
@@top:

mov edx, ecx
cmp ecx, 1 ; if(n == 1)
je @@end

mov ecx, edx
and ecx, 1 ; if( (n & 1) == 0 )
jz @@div2

mov ecx, edx ; .
shl ecx, 2 ; n = n * 2
add ecx, edx ; n = n + n
inc ecx ; n = n + 1 - n = n * 3 + 1
jmp @@top


@@div2:
mov ecx, edx ; .
shr ecx, 1 ; n = n / 2
jmp @@top

@@end:
mov edx, ecx
cmp ecx, 0ffffffffh
je @@really_done

mov ecx, edx
inc ecx
je @@top



@@really_done:


but i think it doesn't work (i was trying to only check values less than 2^32).

also, my attempt here doesn't display numbers as its processing (not quite sure
how to do this in assembly ... ?)

thanks for any help that can be provided...

-- -------------
edit: replaced 'x' with 'n' in a few places ...
Posted on 2003-12-05 02:25:32 by latte
infact, we can express it as such:
int t;

int n = ...;
while(n > 1){
t = n & 1;
n = n >> (t ^ 1);
n = (t * ((n << 1) + 1)) + n;
}


which can allow us to remove some cmp/jmps ...
Posted on 2003-12-05 04:05:49 by latte
Posted on 2003-12-05 05:30:26 by Thomas
shl	  ecx, 2          ; n = n * 2
This is your error. The result would be n=n*4.

Here's another way you could code it using only one register (ECX in this example).
@@top:

cmp ecx,2
jb @@really_done
shr ecx,1 ;divides by 2 with remainder in C flag
jnc @@top ;continue dividing if no remainder
rcl ecx,1 ;restores the previous number
lea ecx,[ecx+ecx*2+1] ;multiplies it by 3 and adds 1
jmp @@top

@@really_done:

Raymond
Posted on 2003-12-05 10:54:18 by Raymond
thank you so much raymond :)

i assume that my attempt to compare 2^32 (0ffffffffh) was correct ? (i am just unsure about putting the 0 in front, i don't understand why it is required ...)
Posted on 2003-12-05 18:00:01 by latte
Firstly, 0ffffffffh = 2^32-1

(The MASM syntax requires that you precede a hex number with a "0" when the 1st hex digit is a letter. The number must also be terminated with the letter "h". Other assemblers may require the same or a different syntax for hex numbers.)

Secondly, the only instruction you had in your original posted code to reach the @@end label was
	cmp		ecx, 1		; if(n == 1)

je @@end

thus reaching it ONLY IF ecx=1. Once you get there, you then compare ecx to 0ffffffffh which will obviously NEVER be equal such that you would NEVER reach the @@really_done label.

Raymond
Posted on 2003-12-05 21:34:42 by Raymond

Firstly, 0ffffffffh = 2^32-1


oh, thats what i meant, sorry :)



(The MASM syntax requires that you precede a hex number with a "0" when the 1st hex digit is a letter. The number must also be terminated with the letter "h". Other assemblers may require the same or a different syntax for hex numbers.)


ah, i see ..


yes ... my original code wasn't so good :) thanks for your help :)
Posted on 2003-12-05 21:42:40 by latte
You're welcome. Glad to help even if it's a tiny piece of the puzzle.:alright:

Raymond
Posted on 2003-12-05 21:46:13 by Raymond
Like 80000000h should be first number preceded by a zero
Posted on 2003-12-08 11:03:45 by mrgone
You only need the leading 0 if the first hex digit is A B C D E or F.

Without the 0, MASM thinks it's a symbolic name.

:)
Posted on 2003-12-08 11:15:02 by S/390