Divide-and-Conquer Multiplication | Science News

ADVERTISEMENT

SUPPORT SCIENCE NEWS

Science News is a nonprofit.

Help us keep you informed.


Math Trek

Divide-and-Conquer Multiplication

By
9:38am, February 11, 2007

Most people know just one way to multiply two large numbers by hand. Typically, they learned it in elementary school. They're often surprised to find that there are a variety of ways to do multiplications, and each such algorithm has advantages and disadvantages. Moreover, grade-school multiplication can be far from the best method available in certain contexts.

Slight differences in the efficiency of multiplication algorithms can make a huge difference when calculators or computers do the work. Computers worldwide perform enormous numbers of multiplications each day. In most computers, each operation consumes mere microseconds, but multiplied by the number of computations performed, the differences in time taken can be significant. So, the general question of how quickly two n-bit numbers can be multiplied has not only great theoretical importance but also practical relevance.

Indeed, when it comes to multiplying two numbers, the best (or fastest) way to do it

This article is only available to Science News subscribers. Already a subscriber? Log in now. Or subscribe today for full access.

Get Science News headlines by e-mail.

More from Science News

From the Nature Index Paid Content