Casting Out Nines - Arithmetic trick to check a multiplication | Hacker News Reader

Casting Out Nines - Arithmetic trick to check a multiplication

mathworld.wolfram.com

33 pointsSandB0x13 comments

Casting out elevens is a related check, and only slightly harder; you add and subtract alternate digits, starting from the end. So 380258203 is congruent to 3-0+2-8+5-2+0-8+3 mod 11, i.e. -5, which is (congruent to) 6 mod 11. The advantage it has over casting out nines is that it catches all digit transpositions and most inadvertent shifts. 12345 × 67890 is, mod 11, 3 × 9 = 27, which is 5 mod 11. 838102050 is also 5 mod 11, but none of the eight numbers you can obtain by transposing two adjacent digits in it are 5 mod 11, while they are all congruent to 838102050 (0) mod 9. Similarly, if you shifted one of the partial products over by one place by accident while adding up the final product, your result would fail the casting-out-elevens check unless that partial product was 0 mod 11.

If you like this kind of stuff, there are a couple of fun mental math books I can recommend:

http://www.amazon.com/Speed-Mathematics-Secret-Skills-Calcul...

http://www.amazon.com/Secrets-Mental-Math-Mathemagicians-Cal...

It's really baffling that people don't teach this stuff in school.

Along these lines, here's how to do square roots in your head.

Let s be the number whose square root you wish to find, and p be the nearest perfect square. You can then approximate √s ≈ √p+(s-p)/(2√p).

Example: √33 ≈ √36+(33-36)/(2√36) = 6 - 3/12 = 6-¼ = 5¾ = 5.75. Actual √33 = 5.74456…

I am a math tutor and taught this to one student who didn't have a square root button on their calculator (albeit I taught it as a calculator trick rather than mental math). He picked up on it pretty quickly.

You can look at this as linear extrapolation using d[x²]/dx = 2x, which is Newton's Method. Taking √p as your initial guess, your new guess is (√p + s/√p)/2 = √p + (s/√p - √p)/2 = √p + (s-p)/(2√p). You can go for another iteration if you want a really accurate square root, which roughly doubles your number of accurate digits each time: 5.75 + (33 - 5.75²)/(2·5.75) ≈ 5.744565, while the correct answer is closer to 5.74456264653802865980. At that point, though, I think it's probably easier to calculate it as (5.75 + 33/5.75)/2.

You can even use this approach for taking square roots of fairly large numbers, just using the squares of single digits — factor the initial number into a power of 100 and a number between 1 and 100. For example, 80802363 is 80.802363 × 100³, so its square root is close to 9 × 10³.

Edit: fixed stupid braino in first sentence.

I also really like the simple-but-awesome tricks for multiplications:

1) (a + b)(a + c) = a(a + b + c) + bc.

Example: 13 14 = 10 * (13 + 4) + 34. You learn to "see" 13 14 --> 170 + 12 = 182.

2) (a + b)(xa + c) = a(xa + c + xb) + bc

Example: 22 * 62 = 20(62 + 32) + 22 = 1364. Here you would see that 60 = 3 20, so you add 3 * 2 to 62 to get 68, multiply by 20 to get 1360, and then add 2*2.

Edit: Er, my stars are turning into italics. You get the idea.

Try copying and pasting × or ⋅.

Or use a compose key: http://canonical.org/~kragen/setting-up-keyboard.html.

It's really baffling that people don't teach this stuff in school.

It's not taught at school because schoolteachers are already struggling with teaching much simpler mathematics.

http://www.aft.org/pdfs/americaneducator/fall1999/amed1.pdf

http://www.nctq.org/resources/math/

http://www.ams.org/notices/200502/fea-kenschaft.pdf

http://www.aft.org/pdfs/americaneducator/fall2009/wu.pdf

I do teach casting out nines as part of the curriculum I have developed for the supplementary mathematics courses I teach as my main current occupation. I have found some very old books in which casting out nines was a routine subject (a check on pencil-and-paper arithmetic back when almost no one had access to an adding machine) as well as theoretical treatments of number theory that explain why casting out nines (or casting out elevens) works--most of the time--to catch computation errors.

Many of these techniques, and other techniques mentioned in the interesting replies in this thread, are standard parts of the mathematics curriculum in some other countries to this day. Even today when everyone in developed countries have access to inexpensive hand calculators, it's still considered good mathematics pedagogy to expose learners to topics of this kind in Singapore, in Taiwan, in the better schools in China, and in much of eastern Europe.

Thank you for posting those. I'll take a more careful look tomorrow morning, but my quick perusal of the Kenschaft article has been sobering :(

Related HN discussion (divisibility by 7; 48 comments):

http://news.ycombinator.com/item?id=1852210

A question of naivety--why bother with checking by "casting out 9's". Isn't it simpler to simply redo the calculation and check if you get the same result? If you're concerned that you multiplied wrong isn't it just as likely you'll perform a bad check calculation resulting in a false negative/false positive?

Speaking from painful experience: my problem with redoing the calculation is that whatever I did tends to stick in memory, with the inevitable result that I do exactly the same mistake again.

Check calculations like this are much easier to do mentally, and provide a rough measure of confidence in the rightness of the result.

Casting out nines has a couple of advantages over simply redoing the calculation:

• as the other commenter mentioned, it's much less likely that you'll repeat the same error, because you'd have to do it in a totally different way;

• if the numbers are more than two digits, it's much less work to do casting out nines than to redo the calculation. Multiplying 38020562 by 95942, using the standard algorithm, you have to do 40 digit multiplications, 32 carries, and then sum five six-digit partial products (about another 25 additions) to get your final sum of 14 or so digits; that's a total of 97 operations. Checking it by casting out nines involves only about 26 operations, which can be simplified further by casting out some nines ahead of time — 95942, for example, is obviously 2 mod 9 because the other digits are 9, 9, and 5+4 = 9.

(Side note: is it worthwhile to use Karatsuba multiplication to multiply 38020562 by 95942 by hand?)

Reply on news.ycombinator.com