The hailstone sequence can actually be calculated very quickly with some simple .x86 assembler. The input is put into eax, and ebx counts the number of cycles the number takes to reach 1.
xor ebx, ebx //Start the cycle counter at 0
mov ecx, 3 //Put 3 into ecx for multiplication
Parity:
cmp eax, 1 //Are we done yet?
je Done //If so, go to the end
mov edx, eax //edx = eax
and edx, 1 //Get parity bit
cmp edx, 0 //Is it even?
je ParEven //If so, skip straight to that part
//eax is odd here
mul ecx //treble eax (ecx is just 3)
add eax, 1 //and +1
add ebx, 1 //increment cycle counter
//eax is now even, so flow straight into even handler
ParEven:
shr eax, 1 //divide by two
add ebx, 1 //increment cycle counter
jmp Parity //time to test parity again
Done:
Just to clarify how this works:
- See if eax is 1 yet. If so, we're done.
- If not, get just the last bit of eax. Note that this determines whether eax is even or odd.
- If it is odd, triple and add one as usual.
- Now eax is certainly even - if it wasn't before, the previous step made it so.
- Half it quickly by shifting all the bits right. This is just like the quick method of dividing by ten in our usual base 10.
- Add one to the cycle counter, and start over.
There are a couple of micro-optimisations, which are allowed since the code is so simple. For example, we xor ecx against itself to set it to 0, rather than using mov. This is just showing off!
Please note this is MSAM. Strictly, we should use jr, in place of jmp with line lables. Likewise, the C-style comments would probably not be approved of but I thought it was more important that the code was understandable.