check if an unsigned binary number is divisible by 15

Question

I'm a computer science student and I got stuck on this question for hours.

We have a binary unsigned number X, represented by 12 bits. We would like to build a system with 1 bit output - Y, that will be '1' if X is divided by 15 without a remainder.

The only components we can use are:

• 4 bit adder, having also C0 (carry) as input, and C4 as output.
• 1 single NOR gate with 3 inputs.

I did find a pattern. If I'll calculate 2^i % 15 for 0<=i<=11 (since it's 12 bits), then for I'll get a sequence 1248 1248 1248.

And if I have 0001 1110 1111 then I can just multiple all the digits, sum them, and check if my number is divisible by 15.

0 + 0 + 0 + 8 + 1 + 2 + 4 + 0 + 1 + 2 + 4 + 8 = 30

The problem is, I have no clue how to implementing it, and if it is even efficient.

I would love some help.

Answer 1

Do you know how to check for divisibility by 9 in base 10?

Add all the digits using base 10 arithmetic. If the result has multiple digits, repeat the process. Stop when you have one digit. If the digit is 9, the original number was divisible by 9. This works because the divisor being tested is base-1. For instance 45 is divisible by 9, and the digits sum to 9, only one adder is needed for two digits. 999 is too, two adders are needed for the three digits.

So now do you have a hint of how to test for divisibility by 15 when you have base 16 arithmetic facilities to hand?

Answer 2

The technique is similar to what you would do to check if a number is divisible by 9 in decimal. We need split the number into four bit digits and then add the digits together repeatedly until we have a single digit left.

Lets call the digits X Y Z

c1,r1 = X + Y
c2,r2 = Z + r1 + c1
c3,r3 = r2 + 1

IF X,Y,Z is divisible by 15 then c2,r2 is also divisible by 15. Furthermore c2,r2 is less than 0x1e. So if r=15 then the original number was divisible by 15. We test if r is equal to 15 by adding one and looking at the resulting carry flag.

What is puzzling me is what the nor gate is supposed to be for.

Answer 3

The full answer:

As @Neil_UK said, I have 12 bits, and if I want to check if that number is divisible by 15, I will take the 12 bits, and look at them as 3 numbers in base 16.

I add the three numbers together, while always adding the carry to the next adder.

After adding them all, I will get as a result some number. As I said, we want to see if the number is divisible by 15, and because the numbers are in base 16, so if the result is 15 - the number is divisible by 15.

If that number is 15, in binary 1111, so if I will add 1 to 1111, I will get carry 1 and 0000.

If that number is 0, in binary 0000, so if I will add 1 to 0000, I will get 0001.

This is where the NOR comes to play.

The number is divisible by 15 if the last 3 digits are 0.

The circuit:

For example:

1111 1111 1111:

• 1111+1111 + 1 = carry 1 and 1111
• 1111 + 1111 + carry 1 = carry 1 and 1111
• 1111 + carry 1 = carry 1 and 0000
• NOR(0,0,0)=True

0001 1001 0101: (405):

• 0101+ 1001+1= 1111
• 1111 + 0001 = carry 1 and 0000
• 0000 + carry 1 = 0001
• NOR(0,0,0)=True