Re: puzzle



Christopher Barber wrote:
> spinoza1111@xxxxxxxxx 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 bull***.
>
> 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.

.