Binary Divisibility by 10
Date: 04/07/99 at 21:28:03 From: Anna Subject: Binary divisibility by 10 I was wondering how you can tell whether a binary number of arbitrary size is divisible by 10, without looking at the whole number. The maximum size of consideration is really important, and within 32 bits would be really good, although around 30 words (1 word = 32 bits) is also okay. So is looking at either the most significant or least significant end of the number. I figured out that the number has to be divisible by 2 and 5. Divisibility by 2 of a binary number is easy, but what about by 5? Or is there another way of looking at the problem? Thanks a lot.
Date: 04/08/99 at 16:54:49 From: Doctor Peterson Subject: Re: Binary divisibility by 10 Hi, Anna. This is a great question! I'd never thought much about divisibility rules for base 2 except those that carry over from base 10 (such as divisibility by 3 = 11 base 2, which is the same as the rule for 11 base 10). But I managed to find a rule for binary divisibility by 5 by using some of the same techniques. It's a little tricky, but quite workable. Then I realized that since you're really working not with individual bits but with whole bytes or words, there's a much easier way to do it. I'll first show you the strictly binary method, since it can be instructive, then I'll show you the better way, which in fact is just like the decimal rule for divisibility by 3. I'll work with the number 617283950 = 100100110010110000000101101110. First split the number into odd and even bits (I'm calling "even" the bits corresponding to even powers of 2): 100100110010110000000101101110 0 1 0 1 0 0 1 0 0 0 1 1 0 1 0 even 1 0 0 1 0 1 1 0 0 0 0 0 1 1 1 odd Now in each of these, add and subtract the digits alternately, as in the standard test for divisibility by 11 in decimal (starting with addition at the right): 100100110010110000000101101110 +0-1+0-1+0-0+1-0+0-0+1-1+0-1+0 = -2 +1-0+0-1+0-1+1-0+0-0+0-0+1-1+1 = 1 Now double the sum of the odd digits and add it to the sum of the even digits: 2*1 + -2 = 0 If the result is divisible by 5, as in this case, the number itself is divisible by 5. Since this number is also divisible by 2 (the rightmost digit being 0), it is divisible by 10. This algorithm can be applied to numbers of any size; the highest either sum can be is half the number of bits you're working with. And since the pattern repeats every 4 bits, you can work with one byte (or word, or long word) at a time, making a simple loop. Now you're asking, how did I ever figure this out? Here's what I did: I looked at powers of 2 modulo 5: 2^0 = 1 = 1 mod 5 2^1 = 2 = 2 mod 5 2^2 = 4 = -1 mod 5 2^3 = 8 = -2 mod 5 2^4 = 16 = 1 mod 5 now it repeats ... (Two numbers are equal, or more properly "congruent," modulo 5, if they give the same remainder when they are divided by 5; the sum or product of numbers that are congruent mod 5 will still be congruent.) Now a binary number is the sum of selected powers of 2. If the bits are, say, abcdef, then the number is f*2^0 = 1f = 1f mod 5 e*2^1 = 2e = 2e mod 5 d*2^2 = 4d = -1d mod 5 c*2^3 = 8c = -2c mod 5 b*2^4 = 16b = 1b mod 5 a*2^5 = 32a = 2a mod 5 ----- --------- abcdef = 2(e-c+a) + (f-d+b) mod 5 This is the formula I gave you. Now for the method I'm really recommending. Remember I pointed out that the pattern repeats every 4 bits? That's because 2^4 = 16 = 1 mod 5. Rather than work in binary, we can work in hexadecimal, just adding up the hex digits (4-bit nibbles) of the number. If this sum is divisible by 5, the number itself is. Even better, you can work with a whole byte at a time (base 256), since 256 = 1 mod 5 as well. That's about as simple as it can get: add all the bytes of the number, and if the sum is divisible by 5, the number is divisible by 5. The only disadvantage to working at this larger scale is that the sums will be larger; but for your 120-byte numbers the sum will be no more than 120*256 = 30720. If you don't want to check this for divisibity by 5 by dividing, you can apply the binary algorithm to it. Here's why this works, in simple terms: a*256^0 + b*256^1 + c*256^2 + ... + z*256^n = a*1 + b*(255 + 1) + c*(255 + 1)^2 + ... + z*(255+1)^n = (a + b + c + ... + z) + 255*(something) so if a+b+c+...+z is divisible by 5, then so is abc...z (base 256). In our example, 617283950 = 24CB016E; 24+CB+01+6E = 15E = 350 (base 10), which is divisible by 5; since 6E is even, 24CB016E is divisible by 10. - Doctor Peterson, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.