brute force

(redirected from Bruteforce)

brute force

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.

brute force attack

The systematic, exhaustive testing of all possible methods that can be used to break a security system. For example, in cryptanalysis, trying all possible keys in the keyspace to decrypt a ciphertext. See dictionary attack. See also brute force programming.

brute force programming

Programming a solution to a problem by using the most straightforward method. However, it is typically not a very elegant solution or one that is flexible for future changes, but it gets the job done. The proverbial brute force programming example is creating the most efficient and least costly route for visiting multiple venues and returning home ("the traveling salesman problem"). Brute force programming tests every possible routing combination; whereas other mathematical algorithms obtain the results more quickly when the number of venues is large. See hard coded. See also brute force attack.
References in periodicals archive ?
Then, the bruteforce method and map method for constructing SWG pairs are introduced and the complexities are analyzed.
Morton and Mareels presented a bruteforce solution to determine the status of each switch in order to minimize system loss in a radial distribution system [9].
This approach represents a substantial cost-savings over the "bruteforce" method of deploying a grid of Doppler profilers and provides better spatial resolution compared to traditional transect surveys.
Best order quantity ([Q.sup.*]) which minimizes the fuzzy total cost is found by bruteforce search algorithm which is a very general problem-solving technique that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's statement.
We see bruteforce numerical solution of models, complete solutions of special cases, and clever approximations around the special solved cases.
One more fact, that is somewhat ironic, is that it is the very nature of distributed, grid-based computing that enables the breaking down of many encryption algorithms (for example, by a fast bruteforce search across the complete space of available keys).
1) The minimax computation is basically a bruteforce search: If implemented as formulated here, it would examine every node in the game tree.
But history has proven over-and-over that mathematical and scientific ingenuity can find ways around the bruteforce, thousand-light-year accelerator, approaches.