puzzle
in [General Programming]
|
Prev: Algorithm book recommendation?
Next: TaskScheduler.dll
From: pete on 25 Jun 2005 08:34 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? -- pete
From: Richard Harter on 25 Jun 2005 20:18 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. 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: spinoza1111 on 27 Jun 2005 06:46 Richard Harter wrote: > 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. 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. If it has to be carried out for each number you are still order(n), where n is the number of elements in the original array, but the execution time formula is multiplied by the average length of each number. And, of course, this solution doesn't address change to floating point. I conclude that the XOR solution is junk, in part because I didn't think of it, and in part because it sucks. It requires either a magic transformation of integers into their binary representation, acceptable in practical contexts, but theoretically unacceptable. And implemented on the practical plane in all but contexts where you happen to need extra efficiency for a god-faith reason, it generates fragile code. What part of el a gance don't you boys understand? > > > 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: Richard Harter on 27 Jun 2005 10:45 On 27 Jun 2005 03:46:06 -0700, spinoza1111(a)yahoo.com wrote: > > >Richard Harter wrote: >> 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. > >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. I'm not quite certain what "calculation of the next digit in the loop" is supposed to mean. Be that as it may, one can do the xor without using extra storage other than the cumulative result. The code would be something weird and wonderful, but it would be O(log m) per word. > >If it has to be carried out for each number you are still order(n), >where n is the number of elements in the original array, but the >execution time formula is multiplied by the average length of each >number. This is incorrect since, given the puzzle statement, the average length of each number is at least O(log n). A better statement is that the cost is at least O(n*log(n)). > >And, of course, this solution doesn't address change to floating point. Quite right. It's not part of the problem space. > >I conclude that the XOR solution is junk, in part because I didn't >think of it, and in part because it sucks. It requires either a magic >transformation of integers into their binary representation, acceptable >in practical contexts, but theoretically unacceptable. And implemented >on the practical plane in all but contexts where you happen to need >extra efficiency for a god-faith reason, it generates fragile code. Your conclusions and your reasoning are your own. Enjoy them. > >What part of el a gance don't you boys understand? It's a puzzle; it was stated as a puzzle. The xor solution is simple and elegant. Arguing that xor is an O(log(m)) operation is not germane - arithmetic operations on integers are also O(log(m)). One could quibble that the puzzle didn't clearly state what operations were permissable. That is a fair objection; however listing permissable operations would have given the game away. OTOH the puzzle and its solution are not particularly relevant to programming because the situation is artificial - it is very much a special case. 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: pete on 27 Jun 2005 11:05
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/30f8fce5a5dd6c42 Anyone else familiar with XOR and checksums? -- pete |