On Sun, 05 Apr 2009 18:36:35 -0500, Tim Wescott <tim@seemywebsite.com> wrote:>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?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 0x58BB3 0x3 0x58BB 0x58BB-0x3= 0x58B8 0x58B8 0x8 0x58B 0x58B -0x8= 0x583 0x583 0x3 0x58 0x58 -0x3= 0x55 0x55 0x5 0x5 0x5 -0x5= 0x0 !!! divisible! But this continued subtraction is the same as: Subtract last digit 0x58BB - (0x3) = 0x58B8 0x58B - (0xB - 0x3) = 0x583 0x58 - (0xB - (0xB - 0x3)) = 0x55 0x5 - (0x5 - (0xB - (0xB - 0x3))) = 0x0 !!! or, 0x5 - 0x5 + 0xB - 0xB + 0x3 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 0xB03D 0xD 0xB03 0xB03 -0xD*0x5= 0xAC2 0xAC2 0x2 0xAC 0xAC -0x2*0x5= 0xA2 0xA2 0x2 0xA 0xA -0x2*0x5= 0! ............ Now try out a few in base 10. Jon
A Puzzle for Today
Started by ●April 5, 2009
Reply by ●April 6, 20092009-04-06
Reply by ●April 6, 20092009-04-06
On Mon, 06 Apr 2009 06:11:07 GMT, Jon Kirwan <jonk@infinitefactors.org> wrote:>Assuming we don't have the confusion that DI mean, "Assuming we don't have the confusion that W... Sorry. Jon
Reply by ●April 6, 20092009-04-06
On Mon, 06 Apr 2009 06:11:07 GMT, Jon Kirwan <jonk@infinitefactors.org> wrote:>0x5 - (0x5 - (0xB - (0xB - 0x3))) = 0x0 !!! > >or, > 0x5 - 0x5 + 0xB - 0xB + 0x3Sorry, this is also messed up. Should be: 0x5 - (0x8 - (0xB - (0xB - 0x3))) = 0x0 !!! or, 0x5 - 0x8 + 0xB - 0xB + 0x3 ... Jon
Reply by ●April 6, 20092009-04-06
Vladimir Vassilevsky wrote:> > > Tim Wescott wrote: > >> 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. > > Perhaps you meant (a<<4) + a; good question for job interview. > > Here is the question I like: > > We have to transmit RS-232 by the AC coupled line. Hence the signal has > to be DC balanced, i.e. have equal amount of ones and zeroes. How many > bit combinations like that can be made of one byte? How about the > general case of the block of N bytes?Use even parity. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●April 6, 20092009-04-06
> Vladimir Vassilevsky wrote: > >>We have to transmit RS-232 by the AC coupled line. Hence the signal has >>to be DC balanced, i.e. have equal amount of ones and zeroes. How many >>bit combinations like that can be made of one byte? How about the >>general case of the block of N bytes?[...] 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 http://www.abvolt.com
Reply by ●April 6, 20092009-04-06
In article <ffoCl.25951$YU2.25005@nlpi066.nbdc.sbc.com>, antispam_bogus@hotmail.com says...> > > > > Vladimir Vassilevsky wrote: > > > >>We have to transmit RS-232 by the AC coupled line. Hence the signal has > >>to be DC balanced, i.e. have equal amount of ones and zeroes. How many > >>bit combinations like that can be made of one byte? How about the > >>general case of the block of N bytes? > > [...] > > 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. > >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. Mark Borgerson
Reply by ●April 6, 20092009-04-06
In article <ffoCl.25951$YU2.25005@nlpi066.nbdc.sbc.com>, antispam_bogus@hotmail.com says...> > > > > Vladimir Vassilevsky wrote: > > > >>We have to transmit RS-232 by the AC coupled line. Hence the signal has > >>to be DC balanced, i.e. have equal amount of ones and zeroes. How many > >>bit combinations like that can be made of one byte? How about the > >>general case of the block of N bytes? > > [...] > > 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. > >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! ;-) Mark Borgerson
Reply by ●April 6, 20092009-04-06
"Mark Borgerson" <mborgerson@comcast.net> wrote in message news:MPG.2443b8fbe3408ab498979a@news.motzarella.org...>> > 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! ;-)ISTR that this was solved many years ago by the Post Office / BT with its HDB3 format.
Reply by ●April 6, 20092009-04-06
Vladimir Vassilevsky wrote:> > > >> Vladimir Vassilevsky wrote: >> >>> We have to transmit RS-232 by the AC coupled line. Hence the signal >>> has to be DC balanced, i.e. have equal amount of ones and zeroes. How >>> many bit combinations like that can be made of one byte? How about >>> the general case of the block of N bytes? > > [...] > > 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 > http://www.abvolt.comRS-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. �����������������������������������������������������������������������
Reply by ●April 6, 20092009-04-06
Mark Borgerson wrote:> In article <ffoCl.25951$YU2.25005@nlpi066.nbdc.sbc.com>, > antispam_bogus@hotmail.com says... >> >> >>> Vladimir Vassilevsky wrote: >>> >>>> We have to transmit RS-232 by the AC coupled line. Hence the signal has >>>> to be DC balanced, i.e. have equal amount of ones and zeroes. How many >>>> bit combinations like that can be made of one byte? How about the >>>> general case of the block of N bytes? >> [...] >> >> 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. >> >> > 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! ;-)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. �����������������������������������������������������������������������
