

Recent ArticlesClojure 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 ... LISP is a generalpurpose programming language and is the secondoldest 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 opensource tools has advantages beyond the obvious economic ones. With the opensource database MySQL in mind ... 
Some Programming MagicIntroductionWhat 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 wellknown 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 ProgramNo 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 HomeSo 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 CarefullyHere'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 a_{0} and b_{0}, respectively, then: {a = a_{0}; b = b_{0}} a := a + b; {a = a_{0} + b_{0}; b = b_{0}} b := a  b; {a = a_{0} + b_{0}; b = (a_{0} + b_{0})  b_{0} = a_{0}} a := a  b; {a = (a_{0} + b_{0})  a_{0} = b_{0}; b = a_{0}} Given that we didn't constrain the inputs a_{0} and b_{0} in any way, then we can conclude that it will work for any values of a_{0} and b_{0}. 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 TrickDespite 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? Simon White 