Catalysoft   Turtle
home products articles about us contact us

Recent Articles

What's Good About Clojure?

Clojure is a relatively new language to appear on the Java Virtual Machine (JVM), although it draws on very mature roots in the form of the LISP langu ...

Should You Care About Requirements Engineering?

Recently, I (Adil) was invited to participate in a one day seminar on the subject of Requirements Engineering. Whilst I have no direct experience of t ...

Tips for Setting Up Your First Business Website

To attract all potential customers to your business you need a presence on the web. The problem is that if you haven't set up a website before, you p ...

What's Good about LISP?

LISP is a general-purpose programming language and is the second-oldest programming language still in use, but how much do you know about it? Did you ...

Open Source Tools for Developers: Why They Matter

From a developer's point of view use of open-source tools has advantages beyond the obvious economic ones. With the open-source database MySQL in mind ...

Some Programming Magic

Discuss this article >>>

Introduction

a programming magician?

What does it mean to be a magician? I'd say you would have to convince an audience that you can perform feats that they would not have believed possible. Some well-known examples from the stage are cutting a lady in half (then magically reassembling her) or making an elephant vanish into thin air. These are very clever tricks, but we all know that they are illusions, devised to trick the eyes of the onlookers into believing what they think they see, instead of what is actually there. "Very interesting", you say, "but what has all this got to do with programming?" The connection is that in this article I shall perform some programming magic.

A Simple Program

No matter what programming language you have used in the past you will have come across the idea of a variable. And unless you have been using a very pure functional programming language such as Haskell, you will also be familiar with the concept of assigning a value to a variable.

So, for instance, if I have an integer variable a, then I can assign it the value 10 by writing:

a := 10;

I have adopted the Pascal style syntax for assignment to make it clear that I mean assignment and am not making a test for equality. Similarly, if I have another variable, b, then I can assign it the value 7 by writing:

b := 7;

So far, so good; but now suppose I wish to swap the values over. That is, put the value 10 into b and the value 7 into a. How would I do that? "That's easy!", I hear you cry, you just need another variable, c, as an intermediate store, then you can write:

c := a;
a := b;
b := c;

That works, certainly, but it uses an extra variable. Is it possible to swap the values over without using an extra variable?

The answer, of course, is yes (otherwise I wouldn't be writing this article). It's just that most programmers, even those with many years of experience, don't realise that it is possible. So if I can demonstrate that it is possible, then I can justifiably claim to have performed a feat of magic!

Do Try This At Home

So if we're not allowed another variable, then what can we do to swap the values over? Why, use some arithmetic, of course! All you need is the ability to add and subtract.

If you're not already familiar with the solution to this problem, why not pick up a pen and paper and spend a few minutes to see if you can work it out. Remember the idea is to swap the values using only the assignment operator and the arithmetic operators '+' and '-'.

Now Watch Carefully

Here's how you do it:

a := a + b;
b := a - b;
a := a - b;

Let's check that this works with our example values of 10 and 7.

{a = 10; b = 7}

a := a + b;

{a = 17; b = 7}

b := a - b;

{a = 17; b = 10}

a := a - b;

{a = 7; b = 10}

More generally, if the initial values of a and b are a0 and b0, respectively, then:

{a = a0; b = b0}

a := a + b;

{a = a0 + b0; b = b0}

b := a - b;

{a = a0 + b0; b = (a0 + b0) - b0 = a0}

a := a - b;

{a = (a0 + b0) - a0 = b0; b = a0}

Given that we didn't constrain the inputs a0 and b0 in any way, then we can conclude that it will work for any values of a0 and b0.

Wow! This is like turning lead into gold. We don't need an intermediate variable? But, hold on a minute, if we don't need an intermediate variable, then why is it such a common algorithmic pattern? Where's the catch?

Well, as you might expect, there is a catch. You might be forgiven for thinking the catch is that it is too tricky to manipulate the variables as shown in the solution. However, there is something much more fundamental.

On every computer there is a limit to the numbers that can be stored as integers. Suppose, for the sake of argument, that my feeble computer can only store 4 bit numbers; in other words, any number between 0 and 15. Then, although the numbers 10 and 7 can be represented in our 4 bit numbers, the algorithm would fail because the first instruction to add a and b would cause an arithmetic overflow (because 17 > 15). The intermediate result is just too big to cope with. The possibility of such overflow errors makes it inadvisable to use this approach in practice: it's far safer just to use an intermediate variable. And, in a sense, that completes the magic trick. I've shown you how to do something you thought wasn't possible, and now you have also seen that any practical uses of that approach were just an illusion.

And For My Next Trick

Despite what I have said about this approach not working well in practice, it is fun to play around with the same basic idea and come up with alternative solutions. For example:

a := a - b;
b := a + b;
a := b - a;

Or alternatively (expounding the overflow/underflow problem, and also introducing the possibility of division by zero errors):

a := a / b;
b := a * b;
a := b / a;

Can you think of any others?

Discuss this article >>>


Simon White