Số bước chia đôi cần thiết

Với phương pháp chia đôi trên $[a,b]$, sai số sau $k$ bước là $\dfrac{b-a}{2^k}$. Hãy tìm số nguyên $k$ nhỏ nhất để sai số $\dfrac{b-a}{2^k} \le tol$.

$k = \left\lceil \log_2 \frac{b-a}{tol} \right\rceil$

(nếu $b-a \le tol$ thì $k=0$).

Ví dụ: $a=0, b=1, tol=0.01$: cần $2^k \ge 100 \Rightarrow k=7$ (vì $2^7=128 \ge 100$, $2^6=64 < 100$).