View previous topic | View next topic

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

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

iamannoying.com
843375.  Sat Sep 03, 2011 8:18 pm Reply with quote

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)

 
bobwilson
843380.  Sat Sep 03, 2011 8:54 pm Reply with quote

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

 
aTao
843386.  Sat Sep 03, 2011 11:47 pm Reply with quote

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.

 
aTao
843387.  Sat Sep 03, 2011 11:57 pm Reply with quote

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]

 
iamannoying.com
843416.  Sun Sep 04, 2011 4:48 am Reply with quote

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]

 
iamannoying.com
843429.  Sun Sep 04, 2011 5:48 am Reply with quote

[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.

 
aTao
843531.  Sun Sep 04, 2011 11:10 am Reply with quote

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.

 
aTao
843664.  Sun Sep 04, 2011 5:25 pm Reply with quote

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.

 
iamannoying.com
843738.  Mon Sep 05, 2011 3:04 am Reply with quote

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.

 
iamannoying.com
843740.  Mon Sep 05, 2011 3:12 am Reply with quote

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.

 
aTao
843883.  Mon Sep 05, 2011 12:36 pm Reply with quote

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.

 
iamannoying.com
844116.  Tue Sep 06, 2011 8:14 am Reply with quote

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?

 
Posital
844279.  Tue Sep 06, 2011 11:21 pm Reply with quote

Why not use the SWAP or XCHG instruction that any middling CPU will have...

 
Dix
844346.  Wed Sep 07, 2011 8:02 am Reply with quote

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.

 
rewboss
844610.  Thu Sep 08, 2011 3:17 pm Reply with quote

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:   

Search Search Forums

Powered by phpBB © 2001, 2002 phpBB Group