This algorithm demonstrates the following statment:

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 :)
Posted on 2003-02-04 08:00:12 by Qweerdy
Remove the unpredicted jump to speed up.
Posted on 2003-02-04 09:12:26 by bitRAKE


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
Posted on 2003-02-04 10:12:54 by Mirno
If we're going to be tricky, shouldn't the correct optimization be this? ;)



xor eax,eax
ret
Posted on 2003-02-04 10:30:35 by Qweerdy
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
Posted on 2003-02-04 13:21:06 by 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 == 0001
2 == 0010
3 == 0011
4 == 0100
5 == 0101
6 == 0110
7 == 0111
8 == 1000
9 == 1001

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:
Posted on 2003-02-04 14:33:20 by arkane
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 =


****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.
Posted on 2003-02-04 16:33:55 by The Svin
The Svin:

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
Posted on 2003-02-05 05:14:48 by Qweerdy
hmm.. I think Mirno method is good and short
Posted on 2003-02-05 08:00:46 by roticv
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.
Posted on 2003-02-05 14:50:48 by The Svin
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 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.
Posted on 2003-02-06 05:54:48 by Qweerdy
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")
Posted on 2003-02-06 12:51:14 by disavowed
Look at the pretty pattern:
Posted on 2003-02-06 21:35:06 by bitRAKE
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


****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
Posted on 2003-02-08 17:19:49 by The Svin

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
Posted on 2003-02-09 04:58:46 by Nexo
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


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 :)
Posted on 2003-02-09 09:59:56 by The Svin