This algorithm demonstrates the following statment:

If you take any whole number and put it through this loop, the loop will always exit.

My quick code (coded as a thread procedure):

Rules: you can't touch the number display frequency :)

If you take any whole number and put it through this loop, the loop will always exit.

```
```

StartLoop:

if (Number is even) {

Number = Number / 2;

} else {

Number = Number * 3 + 1;

}

if (Number != 1) goto StartLoop

My quick code (coded as a thread procedure):

```
```

CalcProc proc Param:dword

LOCAL buffer[20]:byte

mov ebx,1

TestLoop:

.if !(ebx & 0ffffh) ; Don't update for every number

invoke dwtoa,ebx,addr buffer

invoke SetWindowText,hWin,addr buffer

.endif

mov eax,ebx

or eax,eax

@@: jz @F

mov edx,eax

shr eax,1

jnc @B

lea eax,[edx+edx*2+1]

jmp @B

@@: inc ebx

jns TestLoop

ret

CalcProc endp

Rules: you can't touch the number display frequency :)

Remove the unpredicted jump to speed up.

```
```

mov eax, 1

ret

### Edit ###

The loop needs to detect zero, in which case it'll loop forever

```
```

cmp Number, 0

je @F

mov eax, 1

ret

@@:

jmp @B

Or a more serious version:

```
```

mov eax, Number

@@:

lea edx, [eax*2 + eax + 1]

shr eax, 1

cmovc eax, edx

cmp eax, 1

jnz @B

Using cmov will avoid branch prediction issues.

### end edit ###

Mirno

If we're going to be tricky, shouldn't the correct optimization be this? ;)

```
```

xor eax,eax

ret

An odd number can be represented by 2k+1 (where k is an integer). Using an odd number for Number in the formula Number = Number * 3 + 1 will result in:

Number = 3(2k+1) + 1

= 6k + 3 + 1 = 6k + 4

The result will always be even (4 is even, 6k is also even), so you could immediately divide by two in the 'else' case after the n*3+1. A check for number!=1 isn't necessary between n*3+1 and the shift since the result will be at least 4.

Thomas

Number = 3(2k+1) + 1

= 6k + 3 + 1 = 6k + 4

The result will always be even (4 is even, 6k is also even), so you could immediately divide by two in the 'else' case after the n*3+1. A check for number!=1 isn't necessary between n*3+1 and the shift since the result will be at least 4.

Thomas

I'm not sure but I believe that in binary:

odd numbers = first bit is always set to 1

even numbers = 0

Note: I assume the number zero ( 0 ) is neither odd or even.

1 == 000

2 == 001

3 == 001

4 == 010

5 == 010

6 == 011

7 == 011

8 == 100

9 == 100

you can use an AND instruction to remove bits 1 - 31. Then check if 0th bit is set to 0 or 1.

I could be wrong. :grin:

OOPS! :grin: I didn't saw the codes posted, I think I was too late. Forget what I've said above. :grin:

odd numbers = first bit is always set to 1

even numbers = 0

Note: I assume the number zero ( 0 ) is neither odd or even.

1 == 000

**1**2 == 001

**0**3 == 001

**1**4 == 010

**0**5 == 010

**1**6 == 011

**0**7 == 011

**1**8 == 100

**0**9 == 100

**1**you can use an AND instruction to remove bits 1 - 31. Then check if 0th bit is set to 0 or 1.

I could be wrong. :grin:

`and eax, 1`

eax is now either 0 or 1. Try this one if it works!!! :grin:
OOPS! :grin: I didn't saw the codes posted, I think I was too late. Forget what I've said above. :grin:

It is 3x+1 problem. Collatz conjecture.

What do you need the challenge for?

Extract mantiss and do the following change

until it is 2^n where n is integer.

After that next mantiss extraction leads to 1 and

periodic 4,2,1 'cause 3*2^0+1 = 2^2 and 2^2:2=2^(2-1)

2^(2-1):2=2^0 we get perodics.

Note that if x is odd then mantiss of 3x+1 =

So you can remove one iteration of shifts.

Add mantiss to its shifted RIGHT image +1.

Actually you can stop iterations in paternt (0)10..1

'Cause it is (2^(n*2)-1)/3

and in next 3x+1 it gives 2^(n*2).

I specified 2 in place of exponant 'cause it always

even exponant.

What do you need the challenge for?

Extract mantiss and do the following change

until it is 2^n where n is integer.

After that next mantiss extraction leads to 1 and

periodic 4,2,1 'cause 3*2^0+1 = 2^2 and 2^2:2=2^(2-1)

2^(2-1):2=2^0 we get perodics.

Note that if x is odd then mantiss of 3x+1 =

```
```

****b1|0

****b|

1|0

So you can remove one iteration of shifts.

Add mantiss to its shifted RIGHT image +1.

Actually you can stop iterations in paternt (0)10..1

'Cause it is (2^(n*2)-1)/3

and in next 3x+1 it gives 2^(n*2).

I specified 2 in place of exponant 'cause it always

even exponant.

The Svin:

Our maths teacher brought it up in class, and mentioned it was a algo that could be done fast with a computer. I believe he said that it had already been proven but he didn't give us the answer of course :)

I just wanted to see how fast it could be in ASM, as his version was in java :grin:

Also, he didn't tell us the name of the problem, so I have to thank you for that too :)

Thomas:

I had thought of that too, but the resulting algo became a bit complex and I wasn't sure anymore it was doing the correct thing. I probably could have figured it out if I had had more time, but the last few days have been very busy and I haven't allowed myself much free time. Here's my new version, dunno if it actually does what it's supposed to:

It is 3x+1 problem. Collatz conjecture. What do you need the challenge for?

Our maths teacher brought it up in class, and mentioned it was a algo that could be done fast with a computer. I believe he said that it had already been proven but he didn't give us the answer of course :)

I just wanted to see how fast it could be in ASM, as his version was in java :grin:

Also, he didn't tell us the name of the problem, so I have to thank you for that too :)

Thomas:

I had thought of that too, but the resulting algo became a bit complex and I wasn't sure anymore it was doing the correct thing. I probably could have figured it out if I had had more time, but the last few days have been very busy and I haven't allowed myself much free time. Here's my new version, dunno if it actually does what it's supposed to:

```
```

CalcProc proc Param:dword

LOCAL buffer[20]:byte

mov ebx,1

TestLoop:

.if !(ebx & 0fffffh)

invoke dwtoa,ebx,addr buffer

invoke SetWindowText,hWin,addr buffer

.endif

mov eax,ebx

or eax,eax

@@: jz @F

shr eax,1

jnc @B

lea eax,[eax+eax*2+2]

jmp @B

@@: inc ebx

jns TestLoop

ret

CalcProc endp

hmm.. I think Mirno method is good and short

Qweerdy, I was just curious why do you need it for.

Now I in other words can repeat for I was saying, 'cause

I see you haven't understood why did I asked it.

The problem is called by different names but

mostly as "3x+1" or "Collatz conjecture".

The problem is to prove or unprove lemma:

"If we start with natural number and generate raw this way:

If x(n) is odd then x(n+1) = 3*x(n)+1

else

x(n+1)=x(n)/2

The raw always ends with periodic tail (4,2,1)"

I was just wondering where you are in proving Collatz conjecture

or there was some other reason for bringing the challenge.

I'm sorry if my question and simple math notions seemed as

something else.

If it is only about generation for some reason this raw -

there is a question you have to answer:

what if 3x+1 on some step exceed range of 32 bits?

With lea you'd never know it.

Now I in other words can repeat for I was saying, 'cause

I see you haven't understood why did I asked it.

The problem is called by different names but

mostly as "3x+1" or "Collatz conjecture".

The problem is to prove or unprove lemma:

"If we start with natural number and generate raw this way:

If x(n) is odd then x(n+1) = 3*x(n)+1

else

x(n+1)=x(n)/2

The raw always ends with periodic tail (4,2,1)"

I was just wondering where you are in proving Collatz conjecture

or there was some other reason for bringing the challenge.

I'm sorry if my question and simple math notions seemed as

something else.

If it is only about generation for some reason this raw -

there is a question you have to answer:

what if 3x+1 on some step exceed range of 32 bits?

With lea you'd never know it.

The Svin,

I wasn't trying to prove that the lemma is true for all numbers. I just saw the algo and thought that it would make an interesting optimization challenge. So it was just a bit of coding practice, nothing more :)

In the end I came up with the code posted in my previous post, it looks pretty nice but I haven't gotten around to testing it properly yet. In particular the reduced precision of eax after the shift made finding the correct lea values a bit more work than I had time for (seeing as I actually had absolutely

And yes, there is a problem with the numbers exceeding 2^32. Perhaps I'll come up with some bitmask to test for appropriate values, or find another way.

I wasn't trying to prove that the lemma is true for all numbers. I just saw the algo and thought that it would make an interesting optimization challenge. So it was just a bit of coding practice, nothing more :)

In the end I came up with the code posted in my previous post, it looks pretty nice but I haven't gotten around to testing it properly yet. In particular the reduced precision of eax after the shift made finding the correct lea values a bit more work than I had time for (seeing as I actually had absolutely

*no*time).And yes, there is a problem with the numbers exceeding 2^32. Perhaps I'll come up with some bitmask to test for appropriate values, or find another way.

if anyone is interested in doing this in a silly language (i know i'm going to get flames for saying that), i took this class 2 years ago: http://www.cs.cornell.edu/courses/cs312/2001fa/lecture/lec22.htm (scroll down to "The 3x+1 Problem")

Look at the pretty pattern:

Qweerdy,

You don't need shift then one position in time.

If it's even - find least segnificant bit and shift at

once by the index.

And again, after 3x+1 you for sure have even number -

you can have no doubt on it.

Then instead of 3x+1 you can

add x+1/2x(shifted image) + 1.

Cause if it is even then you have for example

You can leave out 0 at once

adding image + shifted right image + 1

You don't need shift then one position in time.

If it's even - find least segnificant bit and shift at

once by the index.

And again, after 3x+1 you for sure have even number -

you can have no doubt on it.

Then instead of 3x+1 you can

add x+1/2x(shifted image) + 1.

Cause if it is even then you have for example

```
```

****1

3x+1= 2x+x+1 =

****10

+

****1

+ 1

-----------

=

****1|0

****|0 (****1 -1)

1|0 (1+1)

You can leave out 0 at once

adding image + shifted right image + 1

challenge. So it was just a bit of coding practice, nothing more :)

It is a bit of coding practice only ;)

```
```

@@: lea eax,[3*eax+1]

bsf ecx,eax

shr eax,cl

cmp eax,1

jne @B

ret

Good code, it is exactly what I meant by extracting

mantiss or shifting out all zeroes at once.

A little thought to do it 2 bytes shorter:

3x+1=2x+x+1 where least significant bit of x = 1

then mantiss of 3x+1 = mantiss of 3 *(SHR x,1) +2

I'm sorry for annoying details in the post, but when

I write short sometimes people don't understand what I mean :)

mantiss or shifting out all zeroes at once.

A little thought to do it 2 bytes shorter:

3x+1=2x+x+1 where least significant bit of x = 1

then mantiss of 3x+1 = mantiss of 3 *(SHR x,1) +2

```
```

Explonation:

Let x = ****1 where * means unknown bits.

so SHR x,1 = ****

then:

3x+1= 2x+x+1 =

****10

****1

1

=

****1|0

****|1 - 1

|1 + 1

=

****1|0

****|0

1|0

mantiss = (leaving out last bit zero)

****1 -1

****

1 +1

=

****0

****

10

--------

but **** = shr x,1 then ****0 = 2(shr x,1) and

****0+****+10=2(shr x,1)+(shr x,1) + 2 = 3(shr x,1) + 2

So if you change entrence to your proc it can be done

2 bytes shorter in size.

; eax = x

call @procentr

....

;-----proc body------

@@:lea eax,[3*eax+2]

@procentr:

bsf ecx,eax ;bsf will set zf=0 'cause x <> 0

inc ecx ;shift mantiss 1 bit right

shr eax,cl ;cl can not be 0 'cause we increased it

;so ZF is changed accordig result in eax

jne @B ;if mantiss of x was 1 then we get 0.

ret

;------proc body-----

I'm sorry for annoying details in the post, but when

I write short sometimes people don't understand what I mean :)