You have a Very Large Number, expressed as an binary integer, in the memory of a machine that allows for byte-wide operations. For some unfathomable reason, you need to determine if this number is evenly divisible by 17.
Without using long division or repeated subtraction, and without ever performing a multiply or divide on a number greater than eight bits long, how can you determine if your number is divisible by 17?
Once you know this technique, what other potential divisors can you test for using this method?
Express the bytes as hex pairs. Subtract each high digit from the corresponding low digit and add the result to a running sum. When the entire number has been processed, repeat the operation on the sum, iteratively until the sum is just one digit. The value of that digit is the original number mod 17.
Add all digits instead of subtracting alternate ones. the result is the original number mod 15.
In any base, the alternate difference of the digits yields N mod base+1, while the sum of the digits yields N mod base-1.
Work in octal, and get divisibility by 7 and 9.
I once proved it. Can you?
Jerry
--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
If I gather that you can permit the entire 8 bit field to be out of balance so long as it comes out balanced on 8 bit boundaries, it's just combinatorial stuff. 70 ways to select 4 '1's out of 8 bits. (n!/[r!*(n-r!)]) The notation is usually just a big paren with n on top and r on bottom.
Since this is RS-232 signaling I might also assume it's asynch, and then the start and stop bits plus the long mark times that may intervene between byte transmissions may need accounting for. But then you said it's not RS-232 signaling since it is AC coupled, which isn't RS-232 which specifies a DC path, so all bets are off.
Wow. I didn't know about the N mod base+1 rule; I was thinking add all the bytes together (to get the number mod 255), then check the resulting one-byte number for divisibility by 17 ('cause 255 is 15 * 17).
Live and learn.
(but note that on my proposed machine, my method's probably faster because you don't have to shift and mask for 8-bit access the way you would for 4-bit access).
I once proved the N mod base-1 rule, but I can't remember the details; I'm going to look at Jon's proof.
This is an interesting problem from a mathematical point of view. I'm a programmer, so I have hacked a small program (see below), which calculates it for n bits, because this was faster and more safe than when I try to derive it mathematically. Then I searched the sequence at NJAS and found this one:
formatting link
So for N bytes there are (8*N)!/((4*N)!)^2 possible combinations.
For practical reasons (would be bad to have 10 bytes with 0 and 10 bytes with 0xff) I would simply use some standard bi-phase encoding, like AES-3 or Manchester.
(loop for bit from 1 to 24 with number = 2 do (loop for i to (1- number) with test = 0 finally (format t "~a ~a~%" bit test) do (loop for j to bit with sum = 0 and b = i finally (when (= sum (/ bit 2)) (incf test)) do (when (= (logand b 1) 1) (incf sum)) (setf b (truncate b 2)))) (setf number (* 2 number)))
--
Frank Buss, fb@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
The techniques are very broadly applied. I mentioned the alternating approach. But just find the first multiple of the desired divisor that yields a '1' in the units position of any base you want to work in. For example, with the case of the base-10 value of 17, but working in base-16, it's just a factor of 1 since 1 times 0x11 produces a value that has a '1' in the units digit. (We want stuff that goes modulo to the base we are working in, resulting in 1.) Because it's just a factor 1, a number is divisible by 0x11 iff taking the least digit times 1 from what remains is itself divisible by 0x11.
Examine 0x58BB3:
Current Last Digit Without last digit Subtract last digit
Which is just what was mentioned at the outset -- alternating addition and subtraction of hexadecimal digits.
...........
This works for most anything you want to play with.
For any N, think of N = Z*x + 1*y, where Z is the system base and y is a digit in that base. x is what remains on the left side after removing y. If W is your divisor, you want to find a multiplier that when multiplied by W produces a '1' in the units digit. (The reason will be obvious in a moment.) Call that number P. Then for N to be divisible by W, it must be the case that N-P*y is also divisible by W. (Think about it.) If that is the case, and we already have N=Z*x+y, then Z*x+y-P*y must be divisible by W. But this is just Z*x-(P-1)*y and we've already asserted that P has a '1' in its units digit. So this means that P-1 must be Z*p (where p is just (P-1)/Z.) So this means Z*x-Z*p*y must be divisible by W, which means that Z*(x-p*y) must also be divisible. Assuming we don't have the confusion that D has a common factor with Z (and that can be handled as well), then it must be the case that (x-p*y) is the part that divisible by W, since Z isn't divisible by W. So we just need to look at that part. But that part has 'b' which is the part of the number without the units digit minus the units digit times p. And then this can repeat.
For example, take the factor 27, which is 0x1B. What multiple of 0x1B yields a '1' in the units? 0x51 is a multiple of 0x1B. Following the logic here, p is 0x5 (0x51 - 1 divided by the base which is 0x10). So we just need to take the upper digits and subtract 0x5 times the units digit. Then repeat.
Examine N=0xB03D and D=0x1B. P=0x51, p=0x5:
Current Last Digit Without last digit Subtract last digit
You guys are professionals, so the quiz appeared to be too basic for you. Here is more complicated: Suggest a systematic procedure to map the natural numbers 0...N into the abovementioned DC balanced code and back for the general case of M bit words. LUT is not a solution.
Vladimir Vassilevsky DSP and Mixed Signal Design Consultant
If you're not worried about channel bandwidth, why not simply transmit N, followed by N^0xFFFF (to as many bytes width as required)? You balance the line and you get a simple method to check for single-byte transmission errors.
One major problem with DC balance and async comms is that you can't let the line sit idle. You have to have continuous transmission or the stop bits destroy the balance. In situations like this hardware helps! ;-)
RS-232 is a partial connector specification (25 pins) and a voltage specification (respond to so-and-so, withstand such-and-such) amd stuff about start and stop bits. The number of data bits is not part of the specification, nor is the inclusion of parity or any other error control. This is an interesting problem, but poorly put. As posed, 256 codes can be achieved by using one start bit (space), one stop bit (mark), eight data bits, and even parity. Many UARTs can be so configured.
Jerry
--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
Just send even-parity SYNC when there's no other data. That costs one symbol, but it's no words than synchronous communication. DEL might be a better choice to help recovery from framing errors.
Jerry
--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here.
All logos and trade names are the property of their respective owners.