hello,

some of you may be familiar with the algorithm:

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:

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 ...

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 ...

infact, we can express it as such:

which can allow us to remove some cmp/jmps ...

```
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 ...

`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

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 ...)

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 ...)

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

thus reaching it

Raymond

(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

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 :)

You're welcome. Glad to help even if it's a tiny piece of the puzzle.:alright:

Raymond

Raymond

Like 80000000h should be first number preceded by a zero

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.

:)

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

:)