brute force


Also found in: Legal, Idioms, Wikipedia.

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: brute-force programs are written in a heavy-handed, tedious way, full of repetition and devoid of any elegance or useful abstraction (see also brute force and ignorance).

The canonical example of a brute-force algorithm is associated with the "travelling salesman problem" (TSP), a classical NP-hard 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 brute-force 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 NP-complete.

A more simple-minded example of brute-force 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 brute-force 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 brute-force 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 long-term complexity cost and bug-chasing than are justified by the speed improvement.

When applied to cryptography, it is usually known as brute force attack.

Ken Thompson, co-inventor 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, finely-tuned cleverness is often a difficult one that requires both engineering savvy and delicate aesthetic judgment.
References in classic literature ?
The vapor, the influence of that brute force,--it has bewildered me and obscured my perception.
They had found out about our meetings in the cave: nothing simpler than to have me kept hard at it overhead and to carry off Faustina by brute force in the boat.
This is a bit of brute force seldom resorted to except in matters of life and death, and the little "We're Here" complained like a human.
ISLAMABAD -- Sikh Intellectuals Circle while condemning the use of brute force on protesters has said that Sikh community supports the Kashmiris' inalienable right of self-determination.
With its powerful amalgam of brute force and selectivity, Deep Blue's process is not unlike what humans do, if different in the ratio of its elements.
No subjective or brute force techniques are used and if a computer at any specific address stops sending spam, their probability rating is quickly downgraded.
He called upon civilized nations to take stock of use of brute force against innocent Kashmiris.
Even a single worm or Trojan that slips through, hidden by the brute force of a DDoS attack, can compromise financial systems.
As many as 147 people were injured due to the use of brute force and firing of bullets, pellets and teargas shells by Indian troops and police personnel against mourners and peaceful protesters while 137 civilians including Hurriyet leaders and activists were arrested during the month.
Sardar Masood Khan said that India wants to suppress the indigenous Kashmir liberation movement through the use of brute force.
The speech, which came as part of a televised ceremony to mark the birth of the Prophet Mohammed, was the second time since Friday's deadly mosque attack that the Egyptian leader spoke of using brute force in the war-ravaged area.
Two days ago, Jantar Mantar was silenced using brute force by a government whose defining feature is intolerance to any form of dissent.