I didn't read the whole thing, but the variable swapping I did was always using method A. I didn't know what B or C would even do at first glance, although it's possible that syntax is somewhere back there under cobwebs...
but it's nice to know that the simple method I know is decently good. (c=
Oh, I totally agree! It's interesting that both Methods B and D rely solely on operators that define groups over the integers (note that subtraction isn't abelian, but it's still a group). I wonder if we can make a swapping mechanism that doesn't require the semblance of a temporary variable and only uses operators which don't form groups over the integers? I think we'd be limited to multiplication, division, modulo, bitwise and, bitwise or, and the 3 different shifts (and unary operators like negation and stuff). Any ideas? To make this more interesting, you aren't allowed to implement the xor swap again by just using lots and lots of NAND gates. :-)
Wait, I'm being an idiot. Subtraction over the integers is not a group because it's not associative. However, it would almost count as an abelian group if we defined it as addition with a few unary negations thrown in at opportune times.
I agree that it was a lot of effort, but there are still lots of people out there who don't yet seem to realize that the compiler is better at compiling than they are.
What is it with you harping on the style guide all the time? There is code written by other companies and organizations that either have different style guides or don't have one at all, and I've seen Method C used in their code.
It's certainly an interesting piece of analysis; I never realized it wasted space; I just figured it was unreadable, and should be skipped on that account.
Besides, I liked the style guide! There's a lot of high-density coding wisdom in there.
Also, I kept seeing "Method C" and thinking you'd found some new programming language that I'd never heard of. :-D
I never realized it wasted space; I just figured it was unreadable
Wait, what? The point of the post is that none of these methods use any extra memory (and only method D uses any extra registers), and that the naive swap is just as space efficient as the xor swap because it doesn't actually allocate the temporary variable you write in the code. I've edited the paragraph that starts with "if you use" to make that clearer.
I ran the same test a few years back, and yes, the obvious thing to do is the best. Wheeee!
FYI, I'd recommend you don't generalize the conclusion this post implies that Method E is as good as Method A. As an example, here's some C++ pseudocode:
complex array a; complex array b; complex array c; for i in 1..k c[i] = a[i] * b[i]; // choice 1 d[i] = a[i].mag(); // choice 2; note that mag is a function in the complex data type e[i] = a[i].conj() * b[i]; // choice 3; note that conj is a function in the complex data type end for In my experience, versions 2 and 3 of this function are much slower than the typed-out expansions thereof, because g++ isn't smart enough to vectorize over (even inline) std library calls. Or something like that. This was a few months back on a 64 bit Intel machine running 64 bit linux. This is true even if you apply manual loop unrolling.
Method D has undefined behavior, also
anonymous
September 22 2009, 23:39:50 UTC
Method D also has undefined behavior: signed overflow in C++ is undefined. From the 1998 c++ standard: Chapter 5 -5-: "If during the evaluation of an expression, the result is not mathematically defined or not in the range of representable values for its type, the behavior is undefined, unless such an expression is a constant expression (5.19) in which case the program is ill-formed."
Re: Method D has undefined behavior, alsobig_bad_alSeptember 23 2009, 00:45:30 UTC
Nice call! I had thought that all integers were supposed to be 2's complement (in which case it works despite the overflow/underflow), but according to paragraph 3.9.1-7, integral types can also have 1's complement or signed magnitude representations. Thanks for pointing this out!
Comments 16
but it's nice to know that the simple method I know is decently good. (c=
Reply
(The comment has been removed)
Reply
Reply
Also, have you really seen the x ^= y ^= x ^= y in code? There's no way that's allowed in the style guide.
Reply
What is it with you harping on the style guide all the time? There is code written by other companies and organizations that either have different style guides or don't have one at all, and I've seen Method C used in their code.
Reply
Besides, I liked the style guide! There's a lot of high-density coding wisdom in there.
Also, I kept seeing "Method C" and thinking you'd found some new programming language that I'd never heard of. :-D
Reply
Wait, what? The point of the post is that none of these methods use any extra memory (and only method D uses any extra registers), and that the naive swap is just as space efficient as the xor swap because it doesn't actually allocate the temporary variable you write in the code. I've edited the paragraph that starts with "if you use" to make that clearer.
Reply
FYI, I'd recommend you don't generalize the conclusion this post implies that Method E is as good as Method A. As an example, here's some C++ pseudocode:
complex array a;
complex array b;
complex array c;
for i in 1..k
c[i] = a[i] * b[i]; // choice 1
d[i] = a[i].mag(); // choice 2; note that mag is a function in the complex data type
e[i] = a[i].conj() * b[i]; // choice 3; note that conj is a function in the complex data type
end for
In my experience, versions 2 and 3 of this function are much slower than the typed-out expansions thereof, because g++ isn't smart enough to vectorize over (even inline) std library calls. Or something like that. This was a few months back on a 64 bit Intel machine running 64 bit linux. This is true even if you apply manual loop unrolling.
Reply
Reply
-- mec
Reply
Reply
Reply
Leave a comment