Sources:
In Introduction to Computation and Programming Using Python, Guttag provides this code (modified) for finding the integer cube root of an integer.
def int_cube_root(n):
result = 0
while result ** 3 < abs(n):
result += 1
if result ** 3 != abs(n):
return '{} is not a perfect cube'.format(n)
else:
if n < 0:
result = -result
return result
int_cube_root(7)
'7 is not a perfect cube'
int_cube_root(8)
2
"The algorithmic technique used in this program," Guttag writes, "is a variant of guess and check called exhaustive enumeration. We enumerate all possibilities until we get to the right answer or exhaust the space of possibilities."
The term guess and check is used in algebra to refer to a trial and error approach to solving equations.
The term brute force is perhaps more often used to mean what Guttag means by exhaustive enumeration.
Guttag's subsequent remarks downplay the value of algorithmic optimization:
"At first blush, this may seem like an incredibly stupid way to solve a problem. Surprisingly, however, exhaustive enumeration algorithms are often the most practical way to solve a problem. They are typically easy to implement and easy to understand. And, in many cases, they run fast enough for all practical purposes. [...] try finding the cube root of 1957816251. The program will seem to finish almost instantaneously."
%%time
int_cube_root(1957816251)
CPU times: user 791 µs, sys: 1 µs, total: 792 µs Wall time: 796 µs
1251
%timeit int_cube_root(1957816251)
1000 loops, best of 3: 791 µs per loop
"Now," Guttag continues, "try 7406961012236344616."
%%time
int_cube_root(7406961012236344616)
CPU times: user 1.37 s, sys: 7.04 ms, total: 1.38 s Wall time: 1.38 s
1949306
%timeit int_cube_root(7406961012236344616)
1 loop, best of 3: 1.34 s per loop
"As you can see," Guttag concludes, "even if millions of guesses are required, it’s not usually a problem. Modern computers are amazingly fast. It takes on the order of one nanosecond — one billionth of a second — to execute an instruction. It’s a bit hard to appreciate how fast that is. For perspective, it takes slightly more than a nanosecond for light to travel a single foot (0.3 meters). Another way to think about this is that in the time it takes for the sound of your voice to travel a hundred feet, a modern computer can execute millions of instructions."
However, Guttag then provides this code (modified) implementing an algorithm to find an approximation to a square root:
def my_sqrt(n, epsilon):
step = epsilon ** 2
guesses = 0
result = 0.0
while abs(result ** 2 - n) > epsilon and result * result <= n:
result += step
guesses += 1
if abs(result ** 2 - n) >= epsilon:
return 'Failed ({} guesses)'.format(guesses)
return '{} ({} guesses)'.format(result, guesses)
Here we use exhaustive enumeration to find an approximation that lies within the constant episilon
of the actual answer. The example Guttag provides, of using it to find an approximation of the square root of 25, demonstrates that, as he puts it, "exhaustive enumeration is a search technique that works only if the set of values being searched includes the answer":
my_sqrt(25, 0.01)
'4.999000000001688 (49990 guesses)'
Of course, if we reduce our epsilon
value to 1, the number of guesses needed is much fewer:
my_sqrt(25, 1)
'5.0 (5 guesses)'
But this is not possible if we want to find an approximation of the square root of 2, for example, since the square root of 2 is not a rational number.
my_sqrt(2, 1)
'Failed (1 guesses)'
my_sqrt(2, 0.01)
'1.410699999999861 (14107 guesses)'
"The time has come," Guttag concludes, "to look for a different way to attack the problem. We need to choose a better algorithm rather than fine tune the current one."
In Introduction to Algorithms, Cormen et al. describe their insertion sort implementation as taking an incremental approach, processing one element of the collection to be sorted at a time. They contrast this incremental approach with so-called divide and conquer approaches.