puzzle
in [General Programming]
|
Prev: Algorithm book recommendation?
Next: TaskScheduler.dll
From: blmblm on 27 Jun 2005 15:09 In article <42c035bb.498454239(a)news.sbtc.net>, Richard Harter <cri(a)tiac.net> wrote: >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, Um .... Wouldn't it be more correct to say that the average size of the integers is *at least* O(log(n))? because it seems to me that the significant thing is not how many integers you have, but the range of possible values. In other words, if you're dealing with 32-bit signed integers, and you don't know anything about their values, doesn't your XOR operation have to take into consideration all 32 bits? >which makes the xor solution O(n*log(n)) >operations. If n can be arbitrarily large, this makes a kind of sense, but it certainly seems counterintuitive, or at least to not apply to the case in which XOR is a constant-time operation. ? well, maybe you agree with that part, since you didn't comment on the following paragraph. >>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. -- | B. L. Massingill | ObDisclaimer: I don't speak for my employers; they return the favor.
From: Randy Howard on 27 Jun 2005 18:22 In article <1119869166.855842.33180(a)f14g2000cwb.googlegroups.com>, spinoza1111(a)yahoo.com says... > 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. What is the concern? Even the PDP-11 (from the 11/40 on IIRC) had XOR. What modern processors do not? Can anyone name one? If so, can you demonstrate that the C compiler for that processor can not generate reasonably efficient and reliable code for the "^" in question here? > I conclude that the XOR solution is junk, in part because I didn't > think of it, Amazingly transparent. So much so I actually suspect a sockpuppet here. > It requires either a magic transformation of integers into their > binary representation, Now I know why somebody came up with "There are 10 kinds of people in the world: those who understand binary and those who don't". They must have been thinking of you. Hint: What do you think a computer must do to "magically transform" integers into binary? -- Randy Howard (2reply remove FOOBAR) "I don't really care about being right you know, I just care about success." --Steve Jobs
From: Richard Harter on 28 Jun 2005 01:32 On 27 Jun 2005 19:09:54 GMT, blmblm(a)myrealbox.com wrote: >In article <42c035bb.498454239(a)news.sbtc.net>, >Richard Harter <cri(a)tiac.net> wrote: >>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, > >Um .... Wouldn't it be more correct to say that the average size of >the integers is *at least* O(log(n))? because it seems to me that >the significant thing is not how many integers you have, but the >range of possible values. In other words, if you're dealing with >32-bit signed integers, and you don't know anything about their >values, doesn't your XOR operation have to take into consideration >all 32 bits? Correct. It should be o(n*log(n)) where small o() is a lower bound. > >>which makes the xor solution O(n*log(n)) >>operations. > >If n can be arbitrarily large, this makes a kind of sense, but it >certainly seems counterintuitive, or at least to not apply to the >case in which XOR is a constant-time operation. ? well, maybe you >agree with that part, since you didn't comment on the following >paragraph. The counterintuitiveness arises because it is customary to assume primitive operations have constant cost. What's really going on is that instructions have builtin parallelism that is sufficient for the size of entities that we are actually interested in. We don't see the log(n) factors because we aren't interested in very large n. > >>>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. > >-- >| B. L. Massingill >| ObDisclaimer: I don't speak for my employers; they return the favor. 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 28 Jun 2005 12:19 On Tue, 28 Jun 2005 15:46:27 +0100, Ben Bacarisse <ben.usenet(a)bsb.me.uk> wrote: >On Tue, 28 Jun 2005 01:01:08 -0700, spinoza1111 wrote: > >> Given enough of anything, anything will work. The point being that the >> problem is O(n^2) and not O(n) because you have to introduce a >> conversion magical from the standpoint of theory to make it O(n) > >It is not usual to ascribe complexities to problems. It can be done, but >it is very hard (problems are usualy assigned to broader categories like >P, NP, NP-Hard and so on). For the *problem* to be O(n^2) you would have >to show that *any* algorithm that solves it required *at least* O(n^2) >time (or whaterv the measure was). > >Two algoroithms have been outlined that are O(n) if the size of the >numbers is bounded: not one, two. One uses XOR, the other partitions the >array about (ideally) its median element. How on earth can the problem be >O(n^2) then? Oddly enough, he is correct, albeit I doubt for the reasons he imagines. The standard definition of O() is that the function inside the O() is bigger than the function on the left side. IOW f(x) = O(g(x)) => There exists X and positive C such that for all x>X |f(x)| <= C*|g(x)| What this implies is that something that is O(n) also is O(n*n) etc. Many programmers and computer scientists (including myself) have fallen into the habit of treating O() as meaning "the same size", i.e., there are positive constants C1 and C2 such that C1*|g(x)| <= |f(x)| <= C2*|g(x)| We really do want O() to mean "bigger than" because in analysis we often have a bound without knowing whether it is the best bound possible. In 1976 Knuth suggested Theta as a notation for being of the same order. I suppose it has become standard but it certainly is cumbersome in ordinary text. > >If you exclude XOR, for bouned numbers, the same solution can be written >using a *constant* number of divisions and odd/even tests (mod 2 >operations) in place of each XOR. The result is an O(n) algorithm that >does not use XOR. If you insist on sticking with your O(n^2) claim you >must at least falsify the arguments that these two algorithms are O(n). As a note sorting the array is a much more general solution (when applicable) because it permits us to identify all discrepancies. [snip sage comments on the value of puzzles] 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: Ben Bacarisse on 28 Jun 2005 13:55
On Tue, 28 Jun 2005 16:19:13 +0000, Richard Harter wrote: > f(x) = O(g(x)) => There exists X and positive C such that for > all x>X > |f(x)| <= C*|g(x)| > > What this implies is that something that is O(n) also is O(n*n) etc. You are, of course, quite correct. I had hoped to finesse this point by trying to ascibe a meaning to the phrase "this problem is O(f(x))" which, if it is to mean anything useful, must mean that all algorithms to solve it are Omega(f(x)). But I should not have done so without introducing the less well known Omega notation! [Omega (also introduced by Knuth in '76) being the lower-bound equivalent to big-O such that f is Theta(g) iff f is Omega(g) and also O(g).] Re-reading my rant, I see that I use absurd phrases like "at least O(n^2)" which, while it may have a colloquial meaning, is almost a mathematical oxymoron. The notation is there for a reason and I should have used it. > We really do want O() to mean "bigger than" because in analysis we often > have a bound without knowing whether it is the best bound possible. In > 1976 Knuth suggested Theta as a notation for being of the same order. I > suppose it has become standard but it certainly is cumbersome in > ordinary text. They are certainly standard, but not just cumbersome in text. It is also fiddly to get the techincalities right to show that, say, the time complexity of an algorithm is Theta(f(n)) where showing it to be O(f(n)) for the "best possible" f you can think of is usualy easier. -- Ben. |