puzzle
in [General Programming]
|
Prev: Algorithm book recommendation?
Next: TaskScheduler.dll
From: pete on 27 Jun 2005 11:12 pete wrote: > > Richard Harter wrote: > > > OTOH the puzzle and its solution are not particularly relevant to > > programming because the situation is artificial - it is very much a > > special case. > > It's a checksum puzzle. > Another one was just posted to clc yesterday. > > http://groups-beta.google.com/group/comp.lang.c/msg/f43da302b4a30a7 http://groups-beta.google.com/group/comp.lang.c/msg/f43da302b4a30a7e?hl=en > http://groups-beta.google.com/group/comp.lang.c/msg/30f8fce5a5dd6c42 http://groups-beta.google.com/group/comp.lang.c/msg/30f8fce5a5dd6c42?hl=en > Anyone else familiar with XOR and checksums? -- pete
From: Richard Harter on 27 Jun 2005 11:36 On Mon, 27 Jun 2005 15:05:05 GMT, pete <pfiland(a)mindspring.com> wrote: >Richard Harter wrote: > >> OTOH the puzzle and its solution are not particularly relevant to >> programming because the situation is artificial - it is very much a >> special case. > >It's a checksum puzzle. >Another one was just posted to clc yesterday. Saw it. Answered it. The xor solution (that was you iirc) is pretty. However it is still a special case. > >http://groups-beta.google.com/group/comp.lang.c/msg/f43da302b4a30a7 >http://groups-beta.google.com/group/comp.lang.c/msg/30f8fce5a5dd6c42 > >Anyone else familiar with XOR and checksums? > >-- >pete Richard Harter, cri(a)tiac.net http://home.tiac.net/~cri, http://www.varinoma.com Save the Earth now!! It's the only planet with chocolate.
From: Michael Wojcik on 27 Jun 2005 11:47 In article <42bdf457.350619761(a)news.sbtc.net>, cri(a)tiac.net (Richard Harter) writes: > On Sat, 25 Jun 2005 12:34:02 GMT, pete <pfiland(a)mindspring.com> wrote: > > >Richard Harter wrote: > > > >> AFAIK computing the base-two representation of a number m requires > >> O(log n) arithmetic operations. > > > >Shouldn't it be O(log(m)) instead, > >with the value of n being independant of m? > > Yes. In the worst case, the array includes all the integers that can be represented by m bits, so m is log(n), and so it becomes O(n * log(log(n)), right? Anyway, you're right that the XOR solution is only O(n) if we have a constant-time XOR operation (for any two members of the array). That doesn't mean we need direct access to the binary representation of the numbers, of course; standard COBOL has an XOR operator (b-xor) but not direct access to the binary representation. Still, my response to Edward was wrong in that regard; thanks for the correction. -- Michael Wojcik michael.wojcik(a)microfocus.com As always, great patience and a clean work area are required for fulfillment of this diversion, and it should not be attempted if either are compromised. -- Chris Ware
From: Richard Harter on 27 Jun 2005 13:27 On 27 Jun 2005 15:47:53 GMT, mwojcik(a)newsguy.com (Michael Wojcik) wrote: > >In article <42bdf457.350619761(a)news.sbtc.net>, cri(a)tiac.net (Richard Harter) writes: >> On Sat, 25 Jun 2005 12:34:02 GMT, pete <pfiland(a)mindspring.com> wrote: >> >> >Richard Harter wrote: >> > >> >> AFAIK computing the base-two representation of a number m requires >> >> O(log n) arithmetic operations. >> > >> >Shouldn't it be O(log(m)) instead, >> >with the value of n being independant of m? >> >> Yes. > >In the worst case, the array includes all the integers that can >be represented by m bits, so m is log(n), and so it becomes >O(n * log(log(n)), right? No; we're mixing m's. It's candy code - m and m's. (My apologies.) The average size of the integers is O(log( n)) so we have to examine O(log(n)) bits to do the xor, which makes the xor solution O(n*log(n)) operations. > >Anyway, you're right that the XOR solution is only O(n) if we have a >constant-time XOR operation (for any two members of the array). That >doesn't mean we need direct access to the binary representation of >the numbers, of course; standard COBOL has an XOR operator (b-xor) >but not direct access to the binary representation. Still, my >response to Edward was wrong in that regard; thanks for the correction. Richard Harter, cri(a)tiac.net http://home.tiac.net/~cri, http://www.varinoma.com Save the Earth now!! It's the only planet with chocolate.
From: moi on 27 Jun 2005 14:17
spinoza1111(a)yahoo.com wrote: > Creating the base-two representation for the XOR requires either the > calculation of the next digit in the loop for the original problem or a > data structure. Most of us use base-2 (binary computers) > And, of course, this solution doesn't address change to floating point. > Has been answered already. Given a canonical reprentation, it will work similarly. (even regardles of FP representation) > I conclude that the XOR solution is junk, in part because I didn't It is not junk. It is totally dependant on xor's unique qualities: a ^ a == 0 a ^b == b ^ a This implies that a ^ a ^ b ^ b == 0 and thus a^ a ^ b ^ b ^ x == x (even if you rearrange the LHS. or add more pairs) There is *no trick*. There is *no overflow* possible. > think of it, and in part because it sucks. It requires either a magic Just admit you did not see it. It is not the end of the world. Live with it. > What part of el a gance don't you boys understand? Syntax error. >>It's the only planet with chocolate. And they have beer && coffee, too! HTH, AvK |