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