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. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com Do you need to implement control loops in software? "Applied Control Theory for Embedded Systems" was written for you. See details at http://www.wescottdesign.com/actfes/actfes.html
A Puzzle for Today
Started by ●April 5, 2009
Reply by ●April 9, 20092009-04-09
Reply by ●April 9, 20092009-04-09
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. 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. Mark Borgerson
Reply by ●April 9, 20092009-04-09
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. >Possible, if you don't mind not storing the number. It can come in as a stream, go out as a stream, and the divisibility by 17 can be determined at any time that the number is declared "done". Read the thread.> > 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. > > Mark Borgerson >You haven't read the rest of the thread, then. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com Do you need to implement control loops in software? "Applied Control Theory for Embedded Systems" was written for you. See details at http://www.wescottdesign.com/actfes/actfes.html
Reply by ●April 9, 20092009-04-09
Le Wed, 08 Apr 2009 20:16:36 -0700, Tim Wescott a écrit :> 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_.Ok. 17 is a prime number so google find out for me the divibility test by 17 : http://fr.wikipedia.org/wiki/Liste_de_crit%C3%A8res_de_divisibilit%C3% A9#Crit.C3.A8re_de_divisibilit.C3.A9_par_17 Unfortunately this wiki page is in French may be you could find the same in English. Habib
Reply by ●April 9, 20092009-04-09
arachnoid wrote:> On 8 avr, 16:44, Tim Wescott <t...@seemywebsite.com> wrote: >>Habib Bouaziz-Viallet wrote: >>>Is the % operator (modulus) of the C language can do the trick ? >> >>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 ?This is a puzzle for embedded engineers. Where do you get the '%' operator from if you're coding for a Z80? A PIC? A 8051? Don't say "I let the compiler do it". Someone has to make the compiler.> A very large number ... what is a very large number ? > (long long int) type (64bits) seems as large as a universe for me :-)Even if you have a 32-bit CPU with divide instruction, testing 64 bits for divisibility by 17 requires a little thinking. Stefan
Reply by ●April 9, 20092009-04-09
In article <b86dndNLktvM40DUnZ2dnUVZ_tidnZ2d@web-ster.com>, tim@seemywebsite.com 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. > > > Possible, if you don't mind not storing the number. It can come in as a > stream, go out as a stream, and the divisibility by 17 can be determined > at any time that the number is declared "done".That doesn't match the original puzzle, then. "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." I answered the question about the number of bytes based on the memmory of the machine as originally specified. If the puzzle has changed, since your original post, I missed that part.> > Read the thread.I caught the beginning, but may have missed a few in between. I did catch and respond to the switch to DC-balanced transmissions, though.> > > > 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. > > > > Mark Borgerson > > > You haven't read the rest of the thread, then.I have now, and you didn't change the rules to allow streamed input and output until now. Mark Borgerson>
Reply by ●April 9, 20092009-04-09
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.>Once you know this technique, what other potential divisors can you test >for using this method?beats me. --
Reply by ●April 9, 20092009-04-09
In comp.dsp Stefan Reuther <stefan.news@arcor.de> wrote: (snip)> Even if you have a 32-bit CPU with divide instruction, testing > 64 bits for divisibility by 17 requires a little thinking.A little, but not so much. A little more if you only have a signed 32 bit divide. Modulo arithmetic problems seem to be a favorite for math contests (middle school and high school level, at least). -- glen
Reply by ●April 9, 20092009-04-09
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?> 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." Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●April 9, 20092009-04-09
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 Borgerson
