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@perl.org 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.
Re: swapping two numbers
Although x could overflow in this case, where it wouldn't with an xor, right? Leonid Grinberg wrote: not in-place cause it's 3 lines, but does not use an external temporay value, and should be language-independent: x = x + y y = x - y x = x - y (IIRC my high school BASIC teacher taught us that) Yeah, that works. Who said that it can't be 3 lines.
Re: swapping two numbers
On Jun 23, 2006, at 5:01 PM, David Westbrook wrote: Michael R. Wolf wrote: not in-place cause it's 3 lines, but does not use an external temporay value, and should be language-independent: x = x + y y = x - y x = x - y (IIRC my high school BASIC teacher taught us that) This works: $a -= $b = ($a += $b) - $b; Chris -- Chris Dolan, Software Developer, http://www.chrisdolan.net/ Public key: http://www.chrisdolan.net/public.key vCard: http://www.chrisdolan.net/ChrisDolan.vcf
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 only way to get a better government is to get better voters. (Moral from Groo The Wanderer #109 (Epic))
RE: SPUG: swapping two numbers
M I was digging through some old code and came across a proof that I
had done
M that you can swap two numbers in place (i.e. without using an
external
M temporary value).
M Of course, in Perl, we can just do this:
M ($x, $y) = ($y, $x)
M But I was challenged (at a GSLUG meeting) to do it in a
language-independent way.
M Since the guy mentioned he had known the solution for 20+ years, I
descended into
M bit-flipping land and came up with a solution.
M (BTW: I'm not sure why my first gut reaction was right. I guess
I've been in the
M business long enough. There's no way my conscious mind came up with
this solution!!!
M Nevertheless, my subconscious came up with this solution within about
3 seconds.
M Brains are amazing!!!)
M I present it here as an interesting piece of code:
M #! /usr/bin/perl -w
M use warnings;
M use strict;
M my $iterations = shift @ARGV || 10;
M for (my $i = 0; $i $iterations; $i++) {
M my ($orig_a, $a) = (int(rand 1000)) x 2;
M my ($orig_b, $b) = (int(rand 1000)) x 2;
M # Original solution:
M #$a = $a ^ $b;
M #$b = $b ^ $a;
M #$a = $a ^ $b;
M # Refined to use op=
M #$a ^= $b;
M #$b ^= $a;
M #$a ^= $b;
M # Utilizing op= value, factored onto one line
M #$a ^= ($b ^= ($a ^= $b));
M # Refined to remove unnecessary parens
M$a ^= $b ^= $a ^= $b;
'Algorithms with Perl' has your original, refined solution in the
Crytography chapter (pg. 539 'Swapping values with XOR') but not
the nice, de-cluttering refinement.
--
Charles DeRykus
