## Tuesday, March 06, 2012

### How to divide by 9 really, really fast (and why it works)

An interesting post on Hacker News shows tricks for dividing by 9. The fastest trick goes like this. Suppose you want to do 53876 / 9 in your head. You do the following:

1. The first digit is going to be the same as in the left hand side, so it's 5.

2. The second digit is the first digit plus the second digit: 5 + 3 = 8

3. The third digit is the previous answer plus the third digit: 8 + 8 = 16. Because that's bigger than 10 carry it to the digit above (which is now 9) and just take the rest. So it's 6.

4. The fourth digit is previous answer plus the fourth digit: 16 + 7 = 23. Again carry the tens to the preceding digit (which now becomes 8) and you're left with 3.

5. The last digit is the sum of all the digits: 23 + 6 = 29. For this final digit it's necessary to work out how many times 29 can be divided by 9 (it's 3). That gets added to the previous digit which becomes 6. The remainder (29 - 9 x 3 = 2) is the remainder of the whole calculation.

So, reading off the digits 53876 / 9 = 5986 remainder 2.

Why does this work? To show why I'll do a smaller example of a three digit number (with digits a, b, c) being divided by 9. The calculation abc/9 can be written as:
(a x 100 + b x 10 + c) / 9

=  a x 100 + b x 10 + c
-------   ------   -
9         9     9

=  a x (11 + 1/9) + b x (1 + 1/9) + c/9

=  a x 11 + b x 1 + (a + b + c)
-----------
9

=  a x 10 + a x 1 + b x 1 + (a + b + c)
-----------
9

=  a x 10 + (a + b) + (a + b + c)
-----------
9

So, the first digit depends on a and any carry from (a + b), the second digit depends on (a + b) and any carry from the final term, and the only division left is the division of (a + b + c) by 9 and so that's where the remainder comes from.

Exactly the same pattern appears for longer numbers. Just be sure to carry; for very long numbers there could be a lot of carrying.

Labels:

If you enjoyed this blog post, you might enjoy my travel book for people interested in science and technology: The Geek Atlas. Signed copies of The Geek Atlas are available.

<$BlogCommentBody$>

<$BlogCommentDateTime$> <$BlogCommentDeleteIcon$>

<$BlogBacklinkControl$> <$BlogBacklinkTitle$> <$BlogBacklinkDeleteIcon$>
<$BlogBacklinkSnippet$>