From comments:
But, this code never stops (because of integer overflow) !?! Yves Daoust
For many numbers it will not overflow.
If it will overflow - for one of those unlucky initial seeds, the overflown number will very likely converge toward 1 without another overflow.
Still this poses interesting question, is there some overflow-cyclic seed number?
Any simple final converging series starts with power of two value (obvious enough?).
2^64 will overflow to zero, which is undefined infinite loop according to algorithm (ends only with 1), but the most optimal solution in answer will finish due to shr rax
producing ZF=1.
Can we produce 2^64? If the starting number is 0x5555555555555555
, it's odd number, next number is then 3n+1, which is 0xFFFFFFFFFFFFFFFF + 1
= 0
. Theoretically in undefined state of algorithm, but the optimized answer of johnfound will recover by exiting on ZF=1. The cmp rax,1
of Peter Cordes will end in infinite loop (QED variant 1, "cheapo" through undefined 0
number).
How about some more complex number, which will create cycle without 0
?
Frankly, I'm not sure, my Math theory is too hazy to get any serious idea, how to deal with it in serious way. But intuitively I would say the series will converge to 1 for every number : 0 < number, as the 3n+1 formula will slowly turn every non-2 prime factor of original number (or intermediate) into some power of 2, sooner or later. So we don't need to worry about infinite loop for original series, only overflow can hamper us.
So I just put few numbers into sheet and took a look on 8 bit truncated numbers.
There are three values overflowing to 0
: 227
, 170
and 85
(85
going directly to 0
, other two progressing toward 85
).
But there's no value creating cyclic overflow seed.
Funnily enough I did a check, which is the first number to suffer from 8 bit truncation, and already 27
is affected! It does reach value 9232
in proper non-truncated series (first truncated value is 322
in 12th step), and the maximum value reached for any of the 2-255 input numbers in non-truncated way is 13120
(for the 255
itself), maximum number of steps to converge to 1
is about 128
(+-2, not sure if "1" is to count, etc...).
Interestingly enough (for me) the number 9232
is maximum for many other source numbers, what's so special about it? :-O 9232
= 0x2410
... hmmm.. no idea.
Unfortunately I can't get any deep grasp of this series, why does it converge and what are the implications of truncating them to k bits, but with cmp number,1
terminating condition it's certainly possible to put the algorithm into infinite loop with particular input value ending as 0
after truncation.
But the value 27
overflowing for 8 bit case is sort of alerting, this looks like if you count the number of steps to reach value 1
, you will get wrong result for majority of numbers from the total k-bit set of integers. For the 8 bit integers the 146 numbers out of 256 have affected series by truncation (some of them may still hit the correct number of steps by accident maybe, I'm too lazy to check).