nospam <nospam@please.invalid> writes:> 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. > > You sum all the bytes mod 256 incrementing the sum on any overflow. > > If the high and low nibbles of the result are equal the number was > divisible by 17.I was wondering when someone would notice that you don't have to do something as complicated as an alternating sum. My implentation on the 6502 would look something like: ; number in NUM, number of bytes in X DIV17Q CLC ; clear carry LOOP ADC NUM,X ; add with carry DEX BNE LOOP ADC #0 ; add in last carry STA TEMP ; store A in EOR instruction ROR ; rotate A 4 bits ROR ROR ROR TEMP EQU *+1 EOR #0 ; exclusive or doesn't care about carry AND #$0f ; isolate bottom 4 bits ; accumulator is zero and Z is set if NUM contains a multiple of 17 Scott -- Scott Hemphill hemphill@alumni.caltech.edu "This isn't flying. This is falling, with style." -- Buzz Lightyear
A Puzzle for Today
Started by ●April 5, 2009
Reply by ●April 9, 20092009-04-09
Reply by ●April 9, 20092009-04-09
Mark Borgerson wrote:> In article <_0sDl.28619$TD1.19465@newsfe18.iad>, jya@ieee.org says... >> Mark Borgerson wrote: >>> In article <6NGdnU3SoawI9UDUnZ2dnUVZ_u-dnZ2d@web-ster.com>, >>> tim@seemywebsite.com says... >>>> arachnoid wrote: >>>>> On 8 avr, 16:44, Tim Wescott <t...@seemywebsite.com> wrote: >>>>>> Habib Bouaziz-Viallet wrote: >>>>>>> Le Sun, 05 Apr 2009 18:36:35 -0500, Tim Wescott a �crit : >>>>>>>> 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. >>>>>>> Is the % operator (modulus) of the C language can do the trick ? >>>>>>> HBV >>>>>> First, the underlying operation is a divide, which I ruled out, and >>>>>> second the % operator only works for data that is within the word size >>>>>> of the machine. >>>> > >>>>> oooh i see, may be you're focused on performance/size code to achieve >>>>> this ? >>>>> >>>> No, it's a _puzzle_. >>>> >>>>> A very large number ... what is a very large number ? >>>>> (long long int) type (64bits) seems as large as a universe for me :-) >>>>> >>>> Name a number of bytes -- it's at least one longer than that. >>>> >>>> >>> Not possible. The number can only be as large as (N-X) where N is the >>> memory available and X is the amount the machine needs to run the >>> algorithm. >> Why do you assume that the number needs to be in RAM? > > I didn't. I carefully chose the word 'memory'. That could include > RAM, ROM, even external memory such as virtual memory on disk or > some other storage medium. >>> A search for "divisibility 17" will yeld a number of algorithms. The >>> all seem to require either recursive or repetitive operations and >>> operations on the last digit of a number in decimal representation. >>> I don't know if the algorithms can be rewritten to work on binary >>> numbers. >> I described a simple method using HEX digits that translates to binary >> with only a shift in viewpoint. "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." >> > > As I said, the algorithms seems to involve iteration. In the case of > your algorithm, it seems to also require enough memory for both > the number and the sum---which could be arbitrarily large. > > Mark BorgersonWhenever the sum threatens to become too large, the iteration can begin on it, reducing it to a single byte, then the original process can continue. However, since nybbles are alternately added and subtracted, the likelihood of the sum going very large is remote. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●April 9, 20092009-04-09
Vladimir Vassilevsky wrote:> 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?Interesting. I once had to design such a code for an RF modem that required DC balanced modulation. I didn't need DC balance over a short distance, so ended up using two groups of codes, one DC balanced and the other off by one. If an off by one code was sent, then the next off by one code would always be off in the opposite direction. -- Thad
Reply by ●April 9, 20092009-04-09
In article <m363hdy0b7.fsf@hemphills.net>, hemphill@hemphills.net says...> nospam <nospam@please.invalid> writes: > > > 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. > > > > You sum all the bytes mod 256 incrementing the sum on any overflow. > > > > If the high and low nibbles of the result are equal the number was > > divisible by 17. > > I was wondering when someone would notice that you don't have to do > something as complicated as an alternating sum. My implentation on > the 6502 would look something like: > > ; number in NUM, number of bytes in X > > DIV17Q CLC ; clear carry > LOOP ADC NUM,X ; add with carry > DEX > BNE LOOP > ADC #0 ; add in last carry > STA TEMP ; store A in EOR instruction > ROR ; rotate A 4 bits > ROR > ROR > ROR > TEMP EQU *+1 > EOR #0 ; exclusive or doesn't care about carry > AND #$0f ; isolate bottom 4 bits > > ; accumulator is zero and Z is set if NUM contains a multiple of 17 >LOL! How well is that going to run from ROM? I haven't seen self- modifying code since my Apple II programming days. That code also might have a problem with a number longer than 256 bytes. ;-) Mark Borgerson
Reply by ●April 9, 20092009-04-09
In comp.dsp Thad Smith <ThadSmith@acm.org> wrote:> Interesting. I once had to design such a code for an RF modem that > required DC balanced modulation. I didn't need DC balance over a short > distance, so ended up using two groups of codes, one DC balanced and the > other off by one. If an off by one code was sent, then the next off by > one code would always be off in the opposite direction.That is also what some forms of ethernet do. -- glen
Reply by ●April 9, 20092009-04-09
nospam <nospam@please.invalid> wrote:>>Once you know this technique, what other potential divisors can you test >>for using this method?>beats me.Actually I think if you are working with n bits then anything 2^n - 1 is divisible by can be tested. If the input number is summed n bits at a time the n bit result will be divisible by the number if the input was. For bytes that would be 3, 5, 15, 17, 51, 85 ? High nibble = low nibble is just an easy test for divisible by 17 --
Reply by ●April 9, 20092009-04-09
Mark Borgerson <mborgerson@comcast.net> writes:> In article <m363hdy0b7.fsf@hemphills.net>, hemphill@hemphills.net > says... >> nospam <nospam@please.invalid> writes: >> >> > 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. >> > >> > You sum all the bytes mod 256 incrementing the sum on any overflow. >> > >> > If the high and low nibbles of the result are equal the number was >> > divisible by 17. >> >> I was wondering when someone would notice that you don't have to do >> something as complicated as an alternating sum. My implentation on >> the 6502 would look something like: >> >> ; number in NUM, number of bytes in X >> >> DIV17Q CLC ; clear carry >> LOOP ADC NUM,X ; add with carry >> DEX >> BNE LOOP >> ADC #0 ; add in last carry >> STA TEMP ; store A in EOR instruction >> ROR ; rotate A 4 bits >> ROR >> ROR >> ROR >> TEMP EQU *+1 >> EOR #0 ; exclusive or doesn't care about carry >> AND #$0f ; isolate bottom 4 bits >> >> ; accumulator is zero and Z is set if NUM contains a multiple of 17 >> > LOL! How well is that going to run from ROM? I haven't seen self- > modifying code since my Apple II programming days.Heh. I did that just for grins.> That code also might have a problem with a number longer than 256 bytes. > ;-)True, but I did say "something like". Alter as necessary for actual requirements. Scott -- Scott Hemphill hemphill@alumni.caltech.edu "This isn't flying. This is falling, with style." -- Buzz Lightyear
Reply by ●April 15, 20092009-04-15
Vladimir Vassilevsky ha escrito:> 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?I'd encrypt the data with a modern stream or block cipher with a randomly selected key. That makes it indistinguishable from random, which is DC balanced. This approach gives the full 256 combinations per byte. Best regards, Marc
Reply by ●April 15, 20092009-04-15
On Apr 15, 12:40�pm, jetm...@hotmail.com wrote:> Vladimir Vassilevsky ha escrito: > > > 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? > > I'd encrypt the data with a modern stream or block cipher with a > randomly selected key. �That makes it indistinguishable from random, > which is DC balanced. > > This approach gives the full 256 combinations per byte. >Doesn't that cause a bit of a problem if the data happens to match the 'random' encrytion. Being random it is possible (if unlikely) that a significant stream of data could turn into a long string of 1s or 0s.
Reply by ●April 15, 20092009-04-15
jetmarc@hotmail.com wrote:> Vladimir Vassilevsky ha escrito: > >>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? > > > I'd encrypt the data with a modern stream or block cipher with a > randomly selected key. That makes it indistinguishable from random, > which is DC balanced.1. Random is balanced only over the infinite time. 2. There is a possibility of matching the data and the key stream, although unlikely.> This approach gives the full 256 combinations per byte.Not a solution. Vladimir Vassilevsky DSP and Mixed Signal Design Consultant http://www.abvolt.com
