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 ?
But just in proportion as I regard this as not wholly a brute force, but partly a human force, and consider that I have relations to those millions as to so many millions of men, and not of mere brute or inanimate things, I see that appeal is possible, first and instantaneously, from them to the Maker of them, and, secondly, from them to themselves.
After living at the seat of the highest authority and power, after conversing with the Emperor less than three hours before, and in general being accustomed to the respect due to his rank in the service, Balashev found it very strange here on Russian soil to encounter this hostile, and still more this disrespectful, application of brute force to himself.
She saw the carnivore brushed aside as he was almost upon her, and in the instant she realized that no substanceless wraith could thus turn the charge of a maddened lion with brute force greater than the brute's.
Whereas, a few years since, he would have met the brute rush with brute force, he now sidestepped his antagonist's headlong charge, and as the brute hurtled past him swung a mighty right to the pit of the ape's stomach.
he said, feeling with confusion and annoyance that what he could decide easily and clearly by himself, he could not discuss before Princess Tverskaya, who to him stood for the incarnation of that brute force which would inevitably control him in the life he led in the eyes of the world, and hinder him from giving way to his feeling of love and forgiveness.
There might be those who would object; but such could be overcome by brute force, of which he and the lad had an ample surplus.
I can stand brute force, but brute reason is quite unbearable.
His hard, brute force darkens and confuses the spiritual element within me; but I, too, will be strong in my own way.
This look of Porthos's made the Gascon regret that he had summoned the brute force of his friend to aid him in an affair which seemed to require chiefly cunning.
He has the brute force, and his last word on any subject could always be his fist.
But when to their feminine rage the indignation of the people is added, when the ignorant and the poor are aroused, when the unintelligent brute force that lies at the bottom of society is made to growl and mow, it needs the habit of magnanimity and religion to treat it godlike as a trifle of no concernment.
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.