1
$\begingroup$

I was showing my son how to cast out nines the other day. He noted that based on the way it worked, we should be able to cast out 7s when we work with octal. We tested this in several bases and it seems to work. I am assuming the chance for false positives increases with the decrease in radix (but I don't actually understand the theory well enough to be sure). But then we got to binary where everything seemed to be a false positive (my son got a huge kick out of the false positive when I showed it to him).

First question: Are there any articles on check sums (like casting out nines) for other radix and their false positives. And other methods that avoid the false positives?

Second question: Is there any check sum for binary that doesn't take longer than the actual calculation (right now we convert to another base and check it, but that takes longer than actually doing the operation)?

Third question: Also, I have seen one book that talked about casting 11s (alternate subtracting and adding the number up starting from the right, and adding 11 if it is negative). Has anyone seen a detailed explanation of it? We could not make it work in other bases--any suggestions?

  • 0
    Since you mentioned both octal and binary, you may be interested in extending this to groups of digits. After all, octal is just binary, when you take the bits in groups of three. Similarly for hexadecimal. Works with decimals, too. For example $999=27\cdot37$, so you can check remainders modulo $37$ as follows: $123456789\equiv 123+456+789=1368\equiv1+368=369,$ and once you are down to 3 digits only then do something else. Similarly $1001=7\cdot11\cdot13$, so modulo 13 (or 7 or 11) it goes like $246531\equiv-246+531=276.$2011-09-06

1 Answers 1

3

In any radix $\rm\:b\:$ once can cast out $\rm\:b\pm1$'s just as one can cast out $9$'s and $11$'s in decimal arithmetic. This works so simply and effectively because $\rm\ b\: \equiv\: \pm 1\ \ (mod\ \ b\mp 1)\:,\:$ therefore

$\rm\qquad c_0 + c_1\ b + c_2\ b^2 + c_3\ b^3 + c_4 b^4\:+\:\cdots\:\equiv\ c_0 \pm c_1 + c_2 \pm c_3 + c_4\:\pm\:\cdots\ (mod\ b\mp 1)$

This "check" won't reveal all arithmetical errors, i.e. there can be many "false positives", since the check only verifies that expressions agree modulo some small number, e.g. agreeing mod $10$ means only that they have the same final digits. However, one can use many coprime moduli and this will suffice to check natural expressions with values below the product of the moduli (see the Chinese Remainder Theorem = CRT). This is the heart of modular computation techniques - which you can read about in most textbooks on computer algebra, e.g. Knuth, TAOCP, vol. 2, Seminumerical Algorithms, or von zur Gathen: Modern Computer Algebra. See also my many prior posts here on casting nines, 91's, etc.