I have been thinking what is the math formula for the piece of code I wrote below.
Assume there are B, D and F three positive integers, and D is smaller than F. Given D and F, the value of B would be found by the following program.
I wonder what is the formula for this. Many thanks.
int B = 1;
while( D < F ) {
B = B + 1;
F = F / 2;
}
return B;
You start with $B = 1$ and increment it each time the loop runs, so the final value $B$ is one more than the number of times the loop runs.
The loop divides $F$ by $2$ each time until it is at most $D$. After $k$ iterations of the loop, $F$ changes to $\lfloor F/2^k \rfloor$. So the number of times the loop runs is the smallest $k \ge 0$ such that $\lfloor F/2^k \rfloor \le D$. As $D$ is an integer, this is equivalent to $F/2^k \le D$, which in turn is equivalent to $2^k \ge F/D$ or $k \ge \log_2 (F/D)$. The smallest such integer $k \ge 0$ is therefore $\lceil \log_2(F/D)\rceil$. (If $F \le D$ is possible, we'd have to take the maximum of this and $0$.)
This means that the returned $B$ is therefore $$B = 1 + \lceil \log_2(F/D)\rceil.$$
A note on code: despite having the formula, it may be better to keep the existing code, because floating-point operations have subtle rounding properties and may introduce error if not reasoned about carefully. In fact, the loop, involving only integer operations, may in fact run faster than the formula, which involves division (note that you can't do integer division $\lfloor F/D \rfloor$ here) followed by finding the floating-point logarithm, then taking ceiling, etc.