How To Multiply Numbers By Multiplying Other Numbers Instead


I do read other people’s mathematics writing, even if I don’t do it enough. A couple days ago RJ Lipton and KW Regan’s Reductions And Jokes discussed how one can take a problem and rewrite it as a different problem. This is one of the standard mathematician’s tricks. The point to doing this is that you might have a better handle on the new problem.

“Better” is an aesthetic judgement. It reflects whether the new problem is easier to work with. Along the way, they offer an example that surprised and delighted me, and that I wanted to share. It’s about multiplying whole numbers. Multiplication can take a fair while, as anyone who’s tried to do 38 times 23 by hand has found out. But we can speed that up. A multiplication table is a special case of a lookup table, a chunk of stored memory which has computed ahead of time all the multiplications someone is likely to do. Then instead of doing them, you just look them up.

The catch is that a multiplication table takes memory. To do all the multiplications for whole numbers 1 through 10 you need … well, not 100 memory cells. But 55. To have 1 through 20 worked out ahead of time you need 210 memory cells. Can we do better?

If addition and subtraction are easy enough to do? And if dividing by two is easy enough? Then, yes. Instead of working out every pair multiplication, work out the squares of the whole numbers. And then make use of this identity:

a \times b = \frac{1}{2}\left( \left(a + b\right)^2 - a^2 - b^2\right)

And that delights me. It’s one of those relationships that’s sitting there, waiting for anyone who’s ever squared a binomial to notice. I don’t know that anyone actually uses this. But it’s fun to see multiplication worked out by a different yet practical way.

Author: Joseph Nebus

I was born 198 years to the day after Johnny Appleseed. The differences between us do not end there. He/him.

2 thoughts on “How To Multiply Numbers By Multiplying Other Numbers Instead”

  1. Enjoyed your thoughts here.

    The trick is used in math to reduce a x b to squares in a number of places. I do not see any reason to do in practice. But perhaps am wrong. Thanks for refering to us.

    Best

    Dick

    Like

    1. Well, thank you for giving me something neat to think about.

      I admit I don’t know a case where I’d do a real problem using this. If I were tasked with building a fast integer-multiplication circuit, for example, and couldn’t go looking up what real professionals do, I would probably use some version of the Russian Peasant/Ancient Egyptian method. This because I know that can be done using bitwise rotations and addition and those are usually pretty fast electronic operations. But finding new ways to do familiar things is always good fun.

      Like

Please Write Something Good

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.