# Q&A: Which is Faster, Bisection or Newton’s Method?

by Justin Skycak on

Cross-posted from here.

## Question

I read that Newton’s method is faster than bisection, but for comparing speed of the bisection method with Newton’s method, I just tried the corresponding Python functions like this:


import numpy as np
from scipy.optimize import bisect, newton
import time

# Define an example function
def f(x):
return x**3 - 2

# Bisection method
start_time_bisection = time.time()
root_bisection = bisect(f, 1, 2)
end_time_bisection = time.time()
time_bisection = end_time_bisection - start_time_bisection

# Newton's method
start_time_newton = time.time()
root_newton = newton(f, 1.0)
end_time_newton = time.time()
time_newton = end_time_newton - start_time_newton

# Print results
print("Bisection Method Result:", root_bisection)
print("Newton's Method Result:", root_newton)
print("Bisection Method Time:", time_bisection)
print("Newton's Method Time:", time_newton)


The results on my laptop were:


Bisection Method Result: 1.2599210498951834
Newton's Method Result: 1.2599210498947795
Bisection Method Time: 2.0265579223632812e-05
Newton's Method Time: 0.00040721893310546875


In this case, the bisection method was faster.

The example you gave comparing bisection and Newton’s method is not a fair comparison. Sure, bisection ran faster for you, but Newton’s method produced a more accurate result by at least several orders of magnitude (you’re not holding the level of precision constant, so it’s not an apples-to-apples comparison). Additionally, you didn’t supply any information about the derivative into Newton’s method, so you’re artificially hamstringing it to use a difference approximation (which takes longer).

To find the root of $x^3-2$ a proper comparison would be to compare iterating the function update_newton(x) = 2/3 * (x + 1/x^2) versus update_bisection(bounds) = [bounds[0], m] if m**3 > 2 else [m, bounds[1]] (where m = (bounds[0]+bounds[1])/2) until the desired level of convergence.

Doing this, we see that Newton’s method is in fact faster.


Num Trials:              1000
True Root:               1.259921049894873191
Epsilon:                 0.000000000001000000

Bisection Method Result: 1.259921049895638134
Newton's Method Result:  1.259921049895406320

Bisection Method Time:   0.000012086868286133
Newton's Method Time:    0.000001034021377563


Here’s the script:


import time

def update_bisection(bounds):
mid = (bounds[0] + bounds[1]) / 2
if mid**3 > 2:
return [bounds[0], mid]
else:
return [mid, bounds[1]]

def update_newton(x):
# f(x) = x^3 - 2
# x - f(x) / f'(x)
# x - (x^3 - 2) / 3x^2
# x - 1/3 x + 2/3 x^2
# 2/3 x + 2/3 x^2
return 2/3 * (x + 1/x**2)

root = 2**(1/3) # = 1.2599210498948732
epsilon           = 0.000000000001
num_trials = 1000

sum_results_bisection = 0
sum_results_newton = 0

def run_bisection():
global sum_results_bisection
guess_bisection = [1, 2]
while abs((guess_bisection[0] + guess_bisection[1]) / 2 - root) > epsilon:
guess_bisection = update_bisection(guess_bisection)
sum_results_bisection += (guess_bisection[0] + guess_bisection[1]) / 2

def run_newton():
global sum_results_newton
guess_newton = 1.5
while abs(guess_newton - root) > epsilon:
guess_newton = update_newton(guess_newton)
sum_results_newton += guess_newton

start_time_bisection = time.time()
for _ in range(num_trials):
run_bisection()
end_time_bisection = time.time()

start_time_newton = time.time()
for _ in range(num_trials):
run_newton()
end_time_newton = time.time()

time_bisection = (end_time_bisection - start_time_bisection) / num_trials
time_newton = (end_time_newton - start_time_newton) / num_trials
result_bisection = sum_results_bisection / num_trials
result_newton = sum_results_newton / num_trials

num_decimals = len(str(root))
format_str = "{:." + str(num_decimals) + "f}"
def format_decimal(x):
return format_str.format(x)

print("Num Trials:             ", num_trials)
print("True Root:              ", format_decimal(root))
print("Epsilon:                ", format_decimal(epsilon))
print("")
print("Bisection Method Result:", format_decimal(result_bisection))
print("Newton's Method Result: ", format_decimal(result_newton))
print("")
print("Bisection Method Time:  ", format_decimal(time_bisection))
print("Newton's Method Time:   ", format_decimal(time_newton))


Tags: