Re: swapping two numbers

On Sun, Jun 25, 2006 at 12:31:19AM -0700, Larry Rosler wrote:
> > From: Philippe "BooK" Bruhat
> > Sent: Saturday, June 24, 2006 04:10
> > To: fwp@xxxxxxxx
> > Subject: Re: swapping two numbers
> >
> >
> > Le vendredi 23 juin 2006 ? 17:40, Samy Kamkar ?crivait:
> > > Although x could overflow in this case, where it wouldn't with an xor,
> > > right?
> >
> > I've quickly tried to overflow it, but I didn't manage to break it.
> > It looks like even if you overflow x with the first addition, you
> > cross the border in the other direction when doing the substraction.
> >
> > --
> >  Philippe "BooK" Bruhat
> 
> The issue has nothing to do with overflow; everything to do with loss of
> precision.  Subtraction of two nearly equal numbers, or addition of two
> numbers of opposite sign and nearly equal magnitude) followed by a second
> similar computation can produce results with few or no significant bits.
> 
> The only correct way to perform these in-place swap operations is to treat
> the operands as bit patterns and use the xor operation.

I disagree.

If we are talking about non-integers (or integers whose magnitude
exceeds the available precision), xor isn't even a possibility in pure
perl; +/- is the only possiblity, with the loss-of-precision you
mention restricting which values it will perfectly work for.

But if we are talking about integers, so long as the intermediate
values stay in a fully representable range (usually 53 bits) there's
no problem with the +/- approach; the xor approach, on the other hand,
will only work correctly with operands representable as unsigned ints
of the size chosen by perl's configure (under no integer) or signed
ints (under use integer).

Either way, xor is the loser.