Getting rid of the branch cut

September 15th, 2008

The video I made for Saturday's post made me wonder what the picture would look like if you didn't have a branch cut at all - if you make the logarithm function generate all of its multiple values (or equivalently, choose a sheet of the Riemann surface at random). Computers can't count up to infinity so the random method must be used. We can't make all the sheets equally likely as their number is unbounded so we need to pick some distribution. I chose a method that's rather simple to implement - I just roll a (virtual) dice until a 1 or a 6 comes up, and subtract the number of 2s and 3s from the number of 4s and 5s (a 1D random walk). That makes positive and negative numbers equally likely, but makes small (positive or negative) numbers more likely than large ones.

Here is the result:

Square roots

The infinite tower is transformed into a fractal fern-like structure. I was surprised at how different this looked from the second image on this post - while the non-principal branches are not visited very often, they cover a lot of space so make a lot of difference to the image.

Don't start big projects

September 14th, 2008

If you have a big project to do, it's very difficult to get started because big projects are so daunting. Most people have probably experienced sitting down to start some project, getting a wave of anxiety about it and then thinking "I'll just refresh my news feed one more time/play one more game of solitaire before I get started". Days and days can pass this way.

The trick is, of course, to not start big projects at all - instead to start a small project and hope it grows into a big project. The trouble is that it's difficult to start modifying a project that's already big if you didn't start it yourself, since even learning enough to make a tiny change is itself a dauntingly big project.

If you can't pick a small project instead of a big project, the thing to do is divide up the project into smaller ones (which itself isn't necessarily a very big project at all - it's just writing down a short list). Then pick a sub-project and just go and do it (recursing as necessary). If you are at all susceptable to procrastination, it's important to avoid looking at the entire list - just concentrate on the one small part of it that's next and forget the rest. Completing one small part gives the satisfaction and mental energy required to start the next one.

It is for this reason that I don't think I could ever write a novel. A small piece of a novel isn't self-contained and independently useful the way that a small piece of a computer program can be, so you don't get that sense of satisfaction from completing it.

One problem I often had at Microsoft was scheduling and estimating time for large projects. Many other programmers I know have the same problem. In order to estimate accurately you need to do a full walk of the tree of sub-projects until each sub-project is no more than a day's work, add up the number of sub-projects and give that as the number of days. That's going to be gross overestimate, of course, since if you know a sub-project is going to be less than a day's work, chances are you know enough about it to do it much quicker than that. But managers (in my experience) prefer it when people overestimate than when they underestimate as it reduces risk. If you desire tighter bounds on your estimate you can figure this out with some practice, by multiplying the number of sub-projects by the average fraction of a day it actually takes to do a sub-project.

The trouble with schedules that are vastly overestimated is that they don't convey any sense of urgency - if you know in the back of your mind that you have three times as much time as you need to do a project, chances are you'll procrastinate for the first two thirds of that time. Then when the project takes longer than you estimated (as projects invariably do), you overrun the allotted time and look less than competent. Trying to achieve the delicate balance between a schedule that is achievable and a schedule that will motivate you sufficiently is difficult.

Scheduling is also very demotivating work in itself because that big list of sub-projects (and the corresponding long stretch of time) looks very daunting, and you don't even get the satisfaction of completing each part as you tick it off the list. I'd much rather not have any schedule at all, and just work at my own pace. I find that "trying to be finished as soon as possible" motivates me much better than "trying to be finished by date X". Managers do like to know when things will be finished, though.

I think the ideal way to cope with this would be to work one project ahead - work on project X+1 while management thinks you're working on project X. Then when you're asked to schedule project X+1 you'll know exactly how long it takes because you've just finished it. Add in a little extra time in case project X+2 takes longer. I never managed to get to this state, though - mostly because I was continually playing "catch up" and also because we weren't planning sufficiently far ahead that I had any idea what project X+1 would be at the start of project X's officially allotted time.

Adjusting the branch cut

September 13th, 2008

The second image in this post was quite popular, so I decided to make a movie out of it.

There aren't really many parameters in the equations used to make this image, though - (the functions are just negative, exponential and logarithm). The colouring is arbitrary but modifying it wouldn't make a very interesting movie. The zoom factor is fairly arbitrary as well but zooming very much in or out would make the image take much longer to render (besides which, zooming movies have been done to death). About the only other arbitrary thing about the image is the choice of branch cut for the logarithm.

This describes a way of adjusting the branch cut in a continuous way, and this is the movie I made by adjusting theta from -4.5 to +4.5 radians:

High quality 640x480 11Mb DivX avi version.

This took about three days to render. I could have done it faster, but my laptop gets uncomfortably warm when both its cores are fully utilized. Also, a problem with Vista networking was causing the other machine I was using to keep getting disconnected from my laptop every few frames.

Cheating in online games

September 12th, 2008

Many modern online games go to great lengths to try to prevent players from cheating - some of them quite invasive. I hope that in the future our computer systems are architected to make it trivial to subvert such malware, but where does that leave players of on-line games who want to avoid playing against cheaters?

Well, I hope that in the future, online games are designed in such a way that cheating is impossible - that is, no information sent to a player's computer that would allow them to gain an unfair advantage and no information received from a player's computer is trusted to be untampered-with. In such a game, a player would be allowed to use whatever client software they like, and would be encouraged to use client software that gives them the best odds. Serious golf players pick the clubs that give them the best advantage, tennis players pick the best tennis rackets and so on - why should on-line gaming be any different?

One implication of this is that the best games will be Turing tests of a sort - a game of aiming accurately and reacting quickly won't be much of a challenge since the computer can do those things better than human players. Tasks that humans can do well but computers are poor at will need to be integral to the game.

That's not to say that games of aiming accurately and reacting quickly won't exist, but if they are played online they will be played between people who each other and trust each other not to cheat, not between strangers.

Static scoping improved

September 11th, 2008

Many programming languages have a facility (usually called "static") to allow the programmer to declare a variable which is visible only to some particular object but has storage at the program's scope - i.e. its value is the same for all instances of that object and when it changes for one it changes for all the other instances too.

One programming language feature I've never seen (but which I think would be useful) is a generalization of this - the ability to declare a variable which is only visible in a particular object but whose scope is the (lexical) parent object. I call this "outer". For top-level objects, this would be the same as static but for nested classes the scope would be that of the outer class.

One could even use the "outer" keyword multiple times to put the variable in any particular level in the object nesting tree. This doesn't violate encapsulation, since members can still only be declared inside their classes.

If you have "outer" instead of "static" (and maybe a few other more minor tweaks) any program can be turned into an isolated object inside another program - i.e. you can easily turn a program into a multi-instance version of that program with all the instances running in the same process.

Desktop security silver bullet

September 10th, 2008

Suppose there was a way to write a desktop operating system in such a way that no malware (defined as any software running on a user's system that puts the interests of its authors before the interests of the user) could have any ill-effects? Would it be implemented? Probably in open-source, but I don't think Apple or Microsoft would include such technologies. Why? Because they wish to put their interests ahead of their users, running code on customers machines which implements such malware as copy-prevention (DRM), anti-cheating mechanisms in games and debugger detectors. Such a security system would make it very easy to work around such bad behaviour (it's always possible to work around it, but currently not always easy).

If such a security mechanism is possible, I think the way to do it would be through API subversion. When process A starts process B, it can ask the OS to redirect any system calls that process B makes to process A, which can then do what it likes with them - anything from passing them on to the OS unchanged to pretending to be the OS to process B. Since malware (on a well-designed OS) will need to use system calls to find out anything about its environment, it is impossible for process B to tell whether it has been subverted or not. Any filing system operation can be sandboxed to make process B think it has changed critical system files. Even the clock APIs can be subverted to make process B think it is running as fast as it should be.

Once this infrastructure is in place, you can sandbox (say) your web browser to be able to make no changes outside its cache, cookies and downloads directories. Any untrusted processes can do essentially nothing to the system without being given permission by the user, but they can't even tell whether that permission has been given or not, so it makes no sense for them to even ask for it. This essentially solves the "dancing bunnies" problem - any requests by malware to have extended capabilities can (and most likely will) be ignored, since the user would have to go through extra steps to do so, and these steps in no way make dancing bunnies any more likely to appear.

One problem with this scheme is that the time it takes to do a system call is multiplied by the number of subversion layers it goes through. One can't use in-process calls because then the malware would be able to examine and modify the system calls by reading and writing its own process memory. So one would need to use the techniques described here.

Variable APIs should be string-based

September 9th, 2008

If you've got a big, complex application programming interface there are generally two ways to do it. You can assign an integer to each function (or method if it's an object-oriented interface) and share the mapping between integers and method names between the callee and caller, or you can provide a single function or method which takes a string.

The first way is generally used in older and more speed-sensitive code, since it has generally been a bit faster in the past (though for most purposes probably isn't significantly so now, especially for out-of-process calls - the context switch time will dwarf the string-lookup time).

The second way is used on the internet (where everything is text based and the network dominates most timings). It's also used in Windows DLLs (though this is more of a hybrid - the names are resolved to locations at DLL load time). COM, on the other hand, uses the first method (and has a lot of complicated registry/interface/type-library goo to make sure the numbers don't get out of sync).

I think that any time you have an API which is sufficiently complicated that it may change with future software or hardware releases, the string-based method is the way to go. Especially for something like this. Keeping track of all the possible variations of the mapping between method names and integers is always going to get sufficiently complicated that you might as well have the computer do it.

Triangular lattices

September 8th, 2008

A commenter wondered what the images on Saturday's post would look like using a sixth root of unity instead of a fourth. I am happy to oblige. With ω=eπi/3, this is the image with the operations z+ω, ωz, ωz:

w^z

And this is the image with the operations z+ω, ωz, zω:

z^w

Lego Technic reminiscing

September 7th, 2008

I remember with great fondness the Christmas when I received my first Lego Technic sets. It must have been 1985 or 1986. I had some other Lego sets but these were something else. I seem to recall that I wasn't old enough for them according to the age range on the box but my parents thought I was sufficiently mature.

I think I had this set:

and I may also have had a supplementary set:

I learnt a lot about mechanics from this - for example that (contrary to my initial expectations) if you made a loop of an even number of gears, it would not create a perpetual motion machine. Also, that if you made a loop of an odd number of gears they wouldn't turn at all.

I think I also had a pneumatic set at some point, probably this one, and probably for a birthday in one of the following years:

and also a motorized set. But looking at the lego catalogues which came with each set, what I really lusted after was this robot:

(I was a big fan of robots) and, especially, this car:

I had friends who had these desirable models, and it was always a lot of fun to the houses of these friends and play with their toys.

Powers involving i

September 6th, 2008

More variations:

Red: z->z+i
Green: z->iz
Blue: z->iz:

i^z

Same, but with blue: z->zi:

z^i