brute force
<programming> A primitive programming style in which the programmer
relies on the computer's processing power instead of using his own intelligence
to simplify the problem, often ignoring problems of scale and applying naive
methods suited to small problems directly to large ones. The term can also be
used in reference to programming style: bruteforce programs are written in a
heavyhanded, tedious way, full of repetition and devoid of any elegance or
useful abstraction (see also brute force and ignorance).
The canonical example of a bruteforce algorithm is associated with the
"travelling salesman problem" (TSP), a classical NPhard problem:
Suppose a person is in, say, Boston, and wishes to drive to N other cities. In
what order should the cities be visited in order to minimise the distance
travelled?
The bruteforce method is to simply generate all possible routes and compare the
distances; while guaranteed to work and simple to implement, this algorithm is
clearly very stupid in that it considers even obviously absurd routes (like
going from Boston to Houston via San Francisco and New York, in that order). For
very small N it works well, but it rapidly becomes absurdly inefficient when N
increases (for N = 15, there are already 1,307,674,368,000 possible routes to
consider, and for N = 1000  well, see bignum). Sometimes, unfortunately, there
is no better general solution than brute force. See also NPcomplete.
A more simpleminded example of bruteforce programming is finding the smallest
number in a large list by first using an existing program to sort the list in
ascending order, and then picking the first number off the front.
Whether bruteforce programming should actually be considered stupid or not
depends on the context; if the problem is not terribly big, the extra CPU time
spent on a bruteforce solution may cost less than the programmer time it would
take to develop a more "intelligent" algorithm. Additionally, a more intelligent
algorithm may imply more longterm complexity cost and bugchasing than are
justified by the speed improvement.
When applied to cryptography, it is usually known as brute force attack.
Ken Thompson, coinventor of Unix, is reported to have uttered the epigram "When
in doubt, use brute force". He probably intended this as a ha ha only serious,
but the original Unix kernel's preference for simple, robust and portable
algorithms over brittle "smart" ones does seem to have been a significant factor
in the success of that operating system. Like so many other tradeoffs in
software design, the choice between brute force and complex, finelytuned
cleverness is often a difficult one that requires both engineering savvy and
delicate aesthetic judgment.
[Jargon File]
(19950214)
Nearby terms:
browser « BRS « BRUIN « brute force » brute
force and ignorance » brute force attack » BS
