Subj : Re: puzzle
To   : comp.programming
From : Gerry Quinn
Date : Tue Jun 28 2005 12:35 pm

In article <1119942810.636779.116860@g43g2000cwa.googlegroups.com>, 
spinoza1111@yahoo.com says...
> moi wrote:

> > Most of us use base-2 (binary computers)
 
> I've already shown how these dull, empirical replies such as "most of
> use base-2 computers" and "my favorite laundry list of programming
> languages all permit access to a binary representation" don't address
> the need to minimize your theoretical assumptions, AND how this
> apparently "only theoretical" consideration creates crap code in
> pragmatic space.

Actually, the XOR solution generalises to any data that can be 
canonically represented as a two-coloured image, which is an operation 
accessible to any general purpose computer, irrespective of how its ALU 
operates.  Clearly it works on any data that can be canonically 
represented.  XOR-like operations can be generalised further to a 
variety of bitwise processes operating on multi-coloured images, where 
each bit goes through a finite cycle of colours/values.  It's a logical 
operation more than it is a base-2 arithmetic operation - it is just 
convenient that the most useful form of it comes naturally with base-2 
arithmetic hardware.

> > > 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)
 
> 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), one
> that has practical results in the form of obfuscated code.

Conversion of data to a canonical binary form is 'magical from the 
standpoint of theory' now?  As compared to what operation?

> A grown up programmer would avoid the XOR solution UNLESS it was needed
> *in extremis* to save time. But this "puzzle" makes it central to
> complexity theory, which is just bullshit.

Complexity theory deals with the properties of arbitrary algorithms.  
No algorithm becomers 'central' to it by being analysed using it.  If 
complexity theory failed to deal equally with all algorithms, it would 
be useless.

- Gerry Quinn

.