In src/mcts.c, the function fixed_sqrt() is intended to compute the square root of a fixed-point number. The implementation uses a loop where, starting from the highest set bit of x, it iteratively attempts to set each lower bit of the result to 1 by testing whether including that bit keeps the squared value less than or equal to x:
for (int i = (31 - __builtin_clz(x | 1)); i >= 0; i--) {
fixed_point_t t = (1U << i);
u64 candidate = (u64) s + t;
if (((candidate * candidate) >> FIXED_SCALE_BITS) <= x)
s += t;
}The code assumes that for any positive integer x, the square root of x is never greater than x itself.
However, this assumption does not hold when x is a fixed-point number less than 1.
For example, if $x = 2^{-16}$, the correct square root should be $2^{-8}$, but the code will return $2^{-16}$, which is incorrect. The reason is that t starts from 1, so the return value cannot be greater than $2^{-16}$, which corresponds to the highest set bit of x.
In summary, the algorithm fails for fixed-point inputs where the highest set bit of $\sqrt{x}$ is greater than that of $x$.
In
src/mcts.c, the functionfixed_sqrt()is intended to compute the square root of a fixed-point number. The implementation uses a loop where, starting from the highest set bit ofx, it iteratively attempts to set each lower bit of the result to 1 by testing whether including that bit keeps the squared value less than or equal tox:The code assumes that for any positive integer
x, the square root ofxis never greater thanxitself.However, this assumption does not hold when
xis a fixed-point number less than 1.For example, if$x = 2^{-16}$ , the correct square root should be $2^{-8}$ , but the code will return $2^{-16}$ , which is incorrect. The reason is that $2^{-16}$ , which corresponds to the highest set bit of
tstarts from 1, so the return value cannot be greater thanx.In summary, the algorithm fails for fixed-point inputs where the highest set bit of$\sqrt{x}$ is greater than that of $x$ .