puzzle
in [General Programming]
|
Prev: Algorithm book recommendation?
Next: TaskScheduler.dll
From: pete on 16 Jun 2005 07:55 spinoza1111(a)yahoo.com wrote: > > pete wrote: > > spinoza1111(a)yahoo.com wrote: > > > > > I still don't see the actual XOR solution. > > > > /* BEGIN new.c */ > > /* END new.c */ > It's 6-16 in Hong Kong. Therefore this was just published in response > to my challenge. Thanks. The continued presence of the challenge "I still don't see the actual XOR solution." is what indicates that it was a response. Unless by "challenge" you're talking about your further ranting in this "gem" of yours: http://groups-beta.google.com/group/comp.programming/msg/c14367c39bdfa29c?hl=en "The problem is that you're too chickenshit to post the solution." "So, chump, what's the XOR solution? " .... which you posted in response to something I posted 10 minutes after posting a solution, regardless of what time you have in Hong Kong. > I would remark that you appear incapable of explaining it. No, I don't > need an explanation. But many visitors do, No. Nobody else does. > And, I had to issue the challenge. I had to beat it out of you, It's not the case that we all knew the solution and were reminded. The case is that we all understood the hint. "hint: xor" --Emlyn Corrin Everybody else understands the solution but you. > and it is code and not an explanation. Nobody asked for an explanantion. You said "I still don't see the actual XOR solution." and now you do. But Anyway, It's based on: 1 The result of an integer XORed with zero is equal to the original value of the integer. 2 The result of an integer XORed with itself is equal to zero 3 XOR is commutative a ^ a is 0 0 ^ b is b a ^ a ^ b is b a ^ b ^ a is b 1^2^3^4^5^4^3^2^1 is 5 You have years of experience with XOR, probably from before I was even born, you said, but there's nothing complicated going on here. How could you not be able to put this together yourself? You're Stupid! > Proves my point. You're Stupid! Actually, your point was best made in this post: http://groups-beta.google.com/group/comp.programming/msg/342dee0e391f670d?hl=en > spinoza1...(a)yahoo.com says... > > Gerry Quinn wrote: > > Precisely because K is small relative to O, > > you can change it by changing code details. > > Small relative to O? K represents a positive real number. > Exactly how do you compare that with the name of a (quasi-) function? K small relative to O?!!! Wow!!! No concept of what Big O is, and you're the only one. Stupid, you can't understand Big O, because you're Stupid. For everybody else: http://www.google.com/search?hl=en&ie=ISO-8859-1&q=%22Big+oh%22+notation -- pete
From: Christopher Barber on 16 Jun 2005 10:06 spinoza1111(a)yahoo.com wrote: > Very cool. Of course, I would have illustrated this with an example. > > Next, you should be able to post a recursive correctness proof. Like you did for your algorithm? > One real problem, however, with the XOR algorithm is that it assumes > that your programming language can like C coerce to pure bit strings, > and that this operation won't do something horrible. Most modern > languages don't even permit these monkeyshines. Not true. Most modern languages do support bitwise operations on integers. What languages are you thinking of that do not? True that many languages will not let you access the bit-pattern of arbitrary data structures. > The validity of the operation for a floating point array forces the > compiler implementor to guarantee that all floating point values will > have the same bit pattern if they are equal. This guarantee in the case > of fp simply isn't made in general, and the algorithm as actually > implemented for a floating point array will FAIL as a result. Yes, that is correct, but the problem specified *integers* not floating point numbers. > It won't even work on an integer array if there are separate > representations of negative and positive zero. Nearly all, but not all, > modern machines use twos-complement which means that all integers have > a unique bit pattern. I don't think there are *any* modern machines not using twos-complement integers. Can you name one? But you are correct that the posted XOR algorithm depends on a twos-complement integer representation. Note that for either floating point or ones-complement you can fix the representation problem normalize all values to a canonical representation before applying XOR. This doesn't change the time complexity of the algorithm. > This means, I am sad to say, that the claim that the OP's problem is > even solved by the XOR solution is complete malarkey, and that the > puzzle is malpractice, and that the problem IS O(n^2) as far as we no. > This "O(n)" solution is bullshit. You are completely wrong. There are other O(n) solutions that require an extra data structure such as a bit-array or hash table. There are O(n log n) solutions that don't require an external data-structure. Clearly the problem is *not* O(n^2). The only way this problem would be O(n^2) would be if it stipulated a linked-list representation, excluded use of XOR and did not allow use of external data structures. - Christopher
From: spinoza1111 on 16 Jun 2005 11:58 Christopher Barber wrote: > spinoza1111(a)yahoo.com wrote: > > > Very cool. Of course, I would have illustrated this with an example. > > > > Next, you should be able to post a recursive correctness proof. > > Like you did for your algorithm? > > > One real problem, however, with the XOR algorithm is that it assumes > > that your programming language can like C coerce to pure bit strings, > > and that this operation won't do something horrible. Most modern > > languages don't even permit these monkeyshines. > > Not true. Most modern languages do support bitwise operations on integers. > What languages are you thinking of that do not? True that many languages will > not let you access the bit-pattern of arbitrary data structures. Incorrect. Only C lets you "see" the bitwise representation of an integer. Using XOR, you just happen to get lucky, in the sense that XOR just happens to be independent of bigendian and smallendian. But the corrupting effect of this puzzle is that it will teach the tyro to keep on the lookout for bitwise stunts and sooner or later, said tyro will find some stunt that does depend on the order of bits. > > > The validity of the operation for a floating point array forces the > > compiler implementor to guarantee that all floating point values will > > have the same bit pattern if they are equal. This guarantee in the case > > of fp simply isn't made in general, and the algorithm as actually > > implemented for a floating point array will FAIL as a result. > > Yes, that is correct, but the problem specified *integers* not floating > point numbers. It didn't state that the language, in which the algorithm was written in your case, had to support coercion of integers to bit strings. News fa-lash: this is unusual outside C. > > > It won't even work on an integer array if there are separate > > representations of negative and positive zero. Nearly all, but not all, > > modern machines use twos-complement which means that all integers have > > a unique bit pattern. > > I don't think there are *any* modern machines not using twos-complement > integers. Can you name one? Not off the top of my head. But keep in mind that there are all sorts of compact and embedded processors out there in computerland. Also, you seem to me blind to the responsibility of the programmer to not in fact make correctness depend on a nonobvious quirk of the machine, which is what this false "solution" does. > > But you are correct that the posted XOR algorithm depends on a twos-complement > integer representation. > > Note that for either floating point or ones-complement you can fix the > representation > problem normalize all values to a canonical representation before applying > XOR. This doesn't change the time complexity of the algorithm. That won't work if the values are available only once, as in the case of an array which is being altered by another thread. Complexity theory is interested in abstract algorithms as opposed to tricks which from the stand point are a deus ex machina. This bogus puzzle teaches the tyro to hope to get lucky. > > > This means, I am sad to say, that the claim that the OP's problem is > > even solved by the XOR solution is complete malarkey, and that the > > puzzle is malpractice, and that the problem IS O(n^2) as far as we no. > > This "O(n)" solution is bullshit. > > You are completely wrong. > > There are other O(n) solutions that require an extra data structure such as a > bit-array or hash table. There are O(n log n) solutions that don't require an > external data-structure. Clearly the problem is *not* O(n^2). Problems are only at arm's length order anything. Sure, if you introduce constraints they map onto different orders but the XOR example shows that in real programming, you can change the order. But this makes it all the more important to have a theory independent of tricks. > > The only way this problem would be O(n^2) would be if it stipulated a > linked-list representation, excluded use of XOR and did not allow use of > external data structures. On the one hand, you can introduce constraints. On the other, you can find a deus ex machina. Therefore the theory does not categorise algorithms once and for all, it allows us to speak about properties of algorithms. But owing to corporate surveillance and its Benthamite potential, the speech is silenced by posters who have to treat the theory as a set of dead answers. I had to beat the XOR solution out of you. I may have heard it in graduate school but it is a fairly useless bit of information. XOR has some interesting properties, it is true, and this may be because unlike And, Or and Not considered as individual operators, you can build all of propositional logic on top of a single Xor operator. But its use requires that everything be coerced to a bit string and this is COMPLETELY retro. As I've shown, floating point numbers can be "equal" with different bit patterns. You suggest normalizing them but for any arbitrary application this can lose information depending on the numerical analysis requirements, of that application. In general, the only responsible way for two objects to be compared for equality is to be as straightforward as possible, and use a==b in C, or a=b in a language for normal people. For bit strings, equality is understood. For integers, equality is understood (but may not be equal itself to bit-string equality on some arbitrary machine). For everything else, "equality" is somewhat of a mystery. Consider strings which may be lower or upper case, ponder floating point numbers which for a given problem may be equal if different by less than some application-dependent epsilon, and cudgel thy brains like Second Gravedigger about objects which can be incompareable or compareable only by special rules. The puzzle's XOR solution violates a background constraint, that one should never use more than one way to determine something. It replaces a==b with XOR and there is as I've shown no guarantee over the useful potential life of the program that this assumption will be even remembered. I had to beat the XOR solution out of you. And I then had to be the one to bring the whole party to an end by mentioning oh by the way, you get around the problem only if you use a deus ex machina and a quirk of the C language. And I had to perform both operations in a climate of systematic harassment and an attempt to silence useful discussion.
From: CBFalconer on 16 Jun 2005 12:00 spinoza1111(a)yahoo.com wrote: > CBFalconer wrote: >> spinoza1111(a)yahoo.com wrote: >>> >> ... snip ... >>> >>> I still don't see the actual XOR solution. >> >> ^ represents XOR, as in C. a and b are any fixed arbitrary value. >> Then the following lemmas hold: >> >> a ^ b ^ a == b >> a ^ a == 0 >> a ^ 0 == a > > OK, now you're talking. I had to beat it out of you, but I > appreciate the thought. I've used XOR but only in assembler. .... snip 80 odd lines of ??? ... I don't know what you are smoking, but it had a better effect on Coleridge. We should send that person from Porlock more often. -- Chuck F (cbfalconer(a)yahoo.com) (cbfalconer(a)worldnet.att.net) Available for consulting/temporary embedded and systems. <http://cbfalconer.home.att.net> USE worldnet address!
From: Christopher Barber on 16 Jun 2005 13:32
spinoza1111(a)yahoo.com wrote: > > Christopher Barber wrote: >>>One real problem, however, with the XOR algorithm is that it assumes >>>that your programming language can like C coerce to pure bit strings, >>>and that this operation won't do something horrible. Most modern >>>languages don't even permit these monkeyshines. >> >>Not true. Most modern languages do support bitwise operations on integers. >>What languages are you thinking of that do not? True that many languages will >>not let you access the bit-pattern of arbitrary data structures. > > Incorrect. Only C lets you "see" the bitwise representation of an > integer. C, C++, C#, Java, VB all support efficient bitwise operations, including XOR, on integers. What language are you thinking of that doesn't support this? > Using XOR, you just happen to get lucky, in the sense that XOR just > happens to be independent of bigendian and smallendian. It doesn't "just happen" to be independent of byte order, it is an inherent quality of the operation. > But the > corrupting effect of this puzzle is that it will teach the tyro to keep > on the lookout for bitwise stunts and sooner or later, said tyro will > find some stunt that does depend on the order of bits. Any "stunt" involving XOR will not depend on the order of the bits. >>>The validity of the operation for a floating point array forces the >>>compiler implementor to guarantee that all floating point values will >>>have the same bit pattern if they are equal. This guarantee in the case >>>of fp simply isn't made in general, and the algorithm as actually >>>implemented for a floating point array will FAIL as a result. >> >>Yes, that is correct, but the problem specified *integers* not floating >>point numbers. > > It didn't state that the language, in which the algorithm was written > in your case, had to support coercion of integers to bit strings. News > fa-lash: this is unusual outside C. You only need bitwise operations on integers. You don't need to be able to coerce integers to bit strings. BTW, there is no such data structure as a "bit string" in C, and there is no coercion involved for integers. >>>It won't even work on an integer array if there are separate >>>representations of negative and positive zero. Nearly all, but not all, >>>modern machines use twos-complement which means that all integers have >>>a unique bit pattern. >> >>I don't think there are *any* modern machines not using twos-complement >>integers. Can you name one? > > Not off the top of my head. But keep in mind that there are all sorts > of compact and embedded processors out there in computerland. Yes, I know, but I would be very suprised to find any kind of processor using ones-complement. Furthermore, many recent languages explicitly specify that integers are represented using twos-complement. >>Note that for either floating point or ones-complement you can fix the >>representation >>problem normalize all values to a canonical representation before applying >>XOR. This doesn't change the time complexity of the algorithm. > > That won't work if the values are available only once, as in the case > of an array which is being altered by another thread. Huh? If another thread is altering the thread and you are not using some kind of lock, then there isn't any algorithm that will provide reliable results. >>The only way this problem would be O(n^2) would be if it stipulated a >>linked-list representation, excluded use of XOR and did not allow use of >>external data structures. > > On the one hand, you can introduce constraints. On the other, you can > find a deus ex machina. Therefore the theory does not categorise > algorithms once and for all, it allows us to speak about properties of > algorithms. > > But owing to corporate surveillance and its Benthamite potential, the > speech is silenced by posters who have to treat the theory as a set of > dead answers. You keep spewing this "corporate surveillance and Benthamite potential" mantra. What does it mean? Whose speech is being silenced? > I had to beat the XOR solution out of you. I think you are mixing posters up. Most of us didn't bother to post the solution, because as you can see, it is very simple, and because we didn't want to spoil it for people that had not figured it out yet. > I may have heard it in > graduate school but it is a fairly useless bit of information. XOR has > some interesting properties, it is true, and this may be because unlike > And, Or and Not considered as individual operators, you can build all > of propositional logic on top of a single Xor operator. Are you claiming you can implement the other bitwise operators using XOR? - Christopher |