How many iterations of the bisection method are needed to achieve full machine precision

Question

Suppose that an equation is known to have a root on the interval $(0,1)$. How many iterations of the bisection method are needed to achieve full machine precision in the approximation to the location of the root assuming calculations are performed in IEEE standard double precision? What if the root where known to be contained in the interval $(8,9)$?

Hint: Consider the number of base 2 digits already known in the location of the root and how many base 2 digits are available in the indicated floating point system.

From: A friendly introduction to numerical analysis by Brain Bradie.

Answer 1

The minimum number with a double number is $\varepsilon=2^{-52}$, as you have $64$ bits, one is used for the sign, $11$ bits for the mantissa.

With the bisection method you have that: $$ e_n=\frac{b-a}{2^n}, $$ where $e_n$ is the absolute error, and the research interval (suitable) is $[a,b]$.

Thus, you need to find $N$ such that: $$ e_N\leq \varepsilon, $$ or, rather $$ \frac{b-a}{2^N}\leq2^{-52}, $$ so: $$ 2^{N-52}\geq b-a, $$ hence: $$ N_{min}=\log_2(b-a)+52. $$ Your case poses $b=a+1$, or, better, $b-a=1$, i.e.: $$ N_{min}(b|b=a+1)=52. $$

Answer 2

If the root to be found is inside the interval $[2^{-n-1},2^{-n}]$, then you need $n$ bisections to move the right point to this goal, and one additional for the left point. At this point you have fixed the exponent of the floating point number, and the leading, implicit $1$ of the mantissa.

Each of the following bisections fixes one of the remaining $53$ explicit bits of the mantissa, making it a total of $n+54$ bisections.