# IT (the number of variables required to swap two numbers)

Page 1 of 3
Goto page 1, 2, 3  Next

 843375.  Sat Sep 03, 2011 8:18 pm Often it's assumed, i.e. general ignorance, that swapping two numeric variables requires a third numeric variable: A=7 B=3.141 C=A (A=7, B=3.141, C=7) A=B (A=3.141, B=3.141, C=7) B=C (A=3.141, B=7: swapped) Spoiler-alert: But that's wrong, there's theoretically (without rounding errors of binary reality, extra CPU cycles it takes don't matter, and so on) no need for a third variable at all. A=7 B=3.141 A=A-B (A=3.859, B=3.141) B=B+A (A=3.859, B=7) A=B-A (A=3.141, B=7: swapped) Great. But what about QI's minus 7 and a minus 3.141? A=-7 B=-3.141 A=A-B (A=-3.859, B=-3.141) B=B+A (A=-3.859, B=-7) A=B-A (A=-3.141, B=-7: swapped)

 843380.  Sat Sep 03, 2011 8:54 pm I assume this is about the most efficient algorithm for sorting?

843386.  Sat Sep 03, 2011 11:47 pm

 iamannoying.com wrote: Often it's assumed, i.e. general ignorance, that swapping two numeric variables requires a third numeric variable: A=7 B=3.141 C=A (A=7, B=3.141, C=7) A=B (A=3.141, B=3.141, C=7) B=C (A=3.141, B=7: swapped) Spoiler-alert: But that's wrong, there's theoretically (without rounding errors of binary reality, extra CPU cycles it takes don't matter, and so on) no need for a third variable at all. A=7 B=3.141 A=A-B (A=3.859, B=3.141) B=B+A (A=3.859, B=7) A=B-A (A=3.141, B=7: swapped) Great. But what about QI's minus 7 and a minus 3.141? A=-7 B=-3.141 A=A-B (A=-3.859, B=-3.141) B=B+A (A=-3.859, B=-7) A=B-A (A=-3.141, B=-7: swapped)

Klaxxon!!!!

But, lets clear up the equations first....
For a bit of clarity:
a=7, b=4.141

 Quote: A=7 B=3.141 A=A-B (A=3.859, B=3.141) B=B+A (A=3.859, B=7) A=B-A (A=3.141, B=7: swapped)

becomes

A=a
B=b
A=A-B (A=a-b, B=b)
B=B+A (A=a-b, B=b+(a-b)=a)
A=B-A (A=a-(a-b)=b, B=a)

no need for the "but what if [contrived a and b]" to find a pair that wont work.

But, why the klaxxon? The reality is that A=A-B or, for any calculation on modern CPU architecture* there are many more numeric values required. Putting aside address registers, for which you would probably use at least 2 for each variable, then there is still the hidden numeric value in the accumulator. At some time there exists in the machine A, B and A-B.
You might say that CPU architecture is not relevant here, that the QI is only concerned with high level coding, that I think is a bit contrived and missing the point since the high level language requires and instructs the CPU to generate and use the third variable.

*A Turing machine could almost get away without a 3rd value, requiring just 1 extra bit of it.

843387.  Sat Sep 03, 2011 11:57 pm

 bobwilson wrote: I assume this is about the most efficient algorithm for sorting?

Depends on what you define as efficient.
Nowadays* speed is everything, although intense CPU speed is used to make up for pathetically slow code. If speed is your criterion then the pigeon hole sort is the fastest. If space is also important then the bubble sort is fav. If coding time is tops then ripple is the way to go.

*[best Yorkshire accent]
I remember when' 1 GB 'ard drive were £1,5000.
Loxxury, I remember when' memory were £1-00 per 1 bit k. Tell that t' youth o' today they'll think yer daft.
[/best Yorkshire accent]

 843416.  Sun Sep 04, 2011 4:48 am I added the minus numbers for the ease of the reader, it should of course work with any sign. That's also the reason for the use of 3.141, on paper you can replace that with "sqrt(2)" and it'll still work. Long version: A=7 B=sqrt(2) A=7 - sqrt(2) A=A - B B=sqrt(2) + 7-sqrt(2) B=B + A A=sqrt(2)+7-sqrt(2) - 7-sqrt(2) A=B - A No need for the klaxxon-reflex, it's just about the popular claim that a (real, declared) third variable is required, like in the first example. That'll still be teached in schools! The third variable isn't (always) required. The question just is about the number of extra variables, and the intended right answer is 0. It's not about the lowest level indeed. It also isn't related to efficiency as such. For one a few assignments are replaced by several math operations. Please note I'm not sure how to show this on tv, because there are rules involved. If you have a box with 5 apples and I have a box with 3 apples, we'll need a third box to swap apples in a box. But the math-solution may require us to store apples in our hands, the register, and/or to remember numbers of apples, and the audience may wonder why the person with 5 apples didn't just give 2 apples to the other person. In a way, the math-solution also uses a third variable: NewA=OldA-OldB But that is neglecting the fact that you don't have to use a real third variable. I think I can write the assignment-solution in a "programming language" close to the level of bare metal, brainf*ck. Untested: +++> A=3 ++< B=2 [>>+<<-]> C=A [<+>-]> A=B [<+>-] B=C In C: cell[0]=3; cell[1]=2; /* C=A */ while (cell[0]>0) { cell[2]++; cell[0]--; } /* A=B */ while (cell[1]>0) { cell[0]++; cell[1]--; } /* B=C */ while (cell[2]>0) { cell[1]++; cell[2]--; } On tv you'll have to explain that cell[2] is a variable using the assignment method, but since brainf*ck has no registers you'll have to call the same cells registers with the math-method. So you decomposed the underlying issues, but the question would be just about the number of extra (declared) variables required for a swap, which always is an operation above the lowest level. The klaxxon would be too trigger-happy, so to speak. In reality the math-method is QI, but assignments are preferred (and used) instead. Nevertheless the claim that a third variable is required remains false. Basic math works too.[/b]

 843429.  Sun Sep 04, 2011 5:48 am [quote="bobwilson"]I assume this is about the most efficient algorithm for sorting?[/quote] An interesting sorting method is the near-linear competition sort. Assuming each tennis player has a fixed performance, the true winner of Wimbledon always played against the true second best tennis player (in any possible round, not just the final). The winner won 7 rounds, isn't it? You'll need 3 additional rounds to find the second best player, by finding the best of the 7 losers. In the end the problem is the same, in a way. Too much math to be efficient. I've seen it in a school book, with an overexcited author. The concept looked good on paper, the math (and overhead) is killing it. Results, including this competition sort: [url]http://users.comlab.ox.ac.uk/ian.collier/rexxla/sorting/[/url] Just like the math-method is about twice as slow as the assignment-method.

843531.  Sun Sep 04, 2011 11:10 am

 iamannoying.com wrote: So you decomposed the underlying issues, but the question would be just about the number of extra (declared) variables required for a swap, which always is an operation above the lowest level. The klaxxon would be too trigger-happy, so to speak. In reality the math-method is QI, but assignments are preferred (and used) instead. Nevertheless the claim that a third variable is required remains false. Basic math works too.[/b]

It is only a band of language complexity that the question is relevant to. Base level languages need the extra variable.
Mid range sure, the trick works.
High level would use "swap(a, b)" or "a b swap"
Ultimate AI level will be "look, just do it will ya"

For me its just a tad contrived, seems to attract nitty gritty quibbling as did the "you cant define left and right" topic.

 843664.  Sun Sep 04, 2011 5:25 pm I think it boils down to explicit vs. implicit directives to the processor. Using a third declared variable is an explicit instruction whereas using the maths assignments is an implicit instruction to temporarily use a 3rd value even if it is only in the accumulator, provided the numerical format will fit, if it wont fit then there is little alternative to storing the new value and then moving the pointer to that value. However, with conscientious coding and a decent optimiser then writing { [declare C] C=A A=B B=C } could compile to code that only swaps the pointers to A and B, certainly a language with swap(a, b) would do this.

843738.  Mon Sep 05, 2011 3:04 am

The processor doesn't really matter? My original statement mentioned "variables":

 Quote: Often it's assumed that swapping two numeric variables requires a third numeric variable:

This implies any programming language which support variables as such, so no raw assembly or brainf*ck, and so on. It also implies the use of (0 or more) variables, and the programming language hides the (unknown) processor's internal solutions.

Of course it's possible to decompose the statement, and each remark may be right on its own, but a language with a swap(a,b) function nor assembly is part of the statement/context. Nor is a CPU with some built-in swap-instruction.

 843740.  Mon Sep 05, 2011 3:12 am Where's the OO'ish "a b swap" coming from? With an unknown number of involved variables under the swap()-hood, isn't it? .code oriented object of line a read people way the exactly is this that claiming of sort professor Austrian an seen have I, but I've some doubts about that concept.

843883.  Mon Sep 05, 2011 12:36 pm

 Quote: IT (the number of variables required to swap two numbers)

In IT a third or more variables ARE required. In maths, no. Just because you dont explicitly declare something does not mean that you are not requiring it, the whole point of high level languages is just that.

Your question is equivalent to not having to tell someone to lift a dead cat to get it out of a box (without tipping or breaking the box). You gotta lift the cat, just because you dont have to tell someone that does not mean you dont need them to do it.

 844116.  Tue Sep 06, 2011 8:14 am The number of characters in the IT-related subject line doen't allow for a legally perfect definition. The text below it mentions "a" programming language with variables, by definition also including basic math capabilities. It's not about internal registers, it's not about hardware/boxes. And it's not about functions, which may or may not hide the way it works. It's about a typical school-claim, you'll need a true third variable to swap two other numeric variables. You don't. I don't know what "Your question" is, have you read it back?

 844279.  Tue Sep 06, 2011 11:21 pm Why not use the SWAP or XCHG instruction that any middling CPU will have...

 844346.  Wed Sep 07, 2011 8:02 am I choose to use a programming language that allows the use of "null" (also know as "undefined") values in variables. Since the result of any arithmetic operation where one of the operands are "null" will yield the result "null", your method won't work if (only) one of the original values are "null" . You will also receive very poor marks for code readability when your code is peer reviewed.

844610.  Thu Sep 08, 2011 3:17 pm

 Dix wrote: "null" (also know as "undefined") values in variables.

Ouch.

No, they're very different things. "Null" is a definite value, while "undefined" is no value at all. "Null" represents an empty set, such as might be returned by a database query, in order to distinguish between that and a value like 0. "Undefined" is what you get if you attempt to reference a variable or object that doesn't exist or hasn't been initialised.

Neither of these should be confused with NaN, which is the result of a calculation that does not yield a real number -- division by zero, or the square root of -1, for example.

Page 1 of 3
Goto page 1, 2, 3  Next

All times are GMT - 5 Hours

Display posts from previous:

Forum tools
User tools