Jun 5, 2009

Newton's Iterative Method

Once in a while when you're doing math processing, it is useful to be able to estimate the zeroes of a function (if f(x) = 0, then x is a zero of f). An example is square roots. A square root of n is simply the zero of f(x) = x2 - n. This is a really useful operation.

I'm going to talk about Newton's Iterative Method, which is a way of estimating a square root. I say estimating because since most square roots are irrational numbers, it is impossible to represent them accurately using floating point arithmetic. So we just get as close as we can to it.

There are other ways of calculating square roots. The square root of n can also be expressed as eln(n)/2. However this is slower to calculate.

How does this method work? Well to understand it fully you need to understand calculus, however with square roots the calculus is really simple so you can just take my word for it if you don't know calculus.

Let's try to find the square root of 2. Our function is therefore:
f(x) = x2 - 2
The derivative1 f′ of this function is 2x.

We start off with a guess. Let's say 1. If you want you can start off with any other number except zero (I'll explain why you can't use zero in a bit), but I'm going to start with 1.

What we want to do now is find the linear approximation (first order Taylor series if you want to be more pedantic) of f around the point x = 1. We'll call this point x0 The function, we'll call it T, for a linear approximation is:
T(x) = f(x0) + f′(x0) * (x - x0)
For our function, it looks like this:
T(x) = x02 - 2 + 2x0(x - x0) = 2x0x - x02 - 2
At x0 = 1, we have:
T(x) = 2x - 3

Now for the more interesting part. Let's look at a picture of these two functions (the blue line is the x-axis):

We want to find out where the linear approximation hits the x-axis. By setting T to zero and solving for x we get:
x = x0 - (x02 - 2) / 2x0 = 1.5
We now use this 1.5 as our new x0, except that we will call it x1. Now we plug that into our formula:
x = x1 - (x12 - 2) / 2x1 = 1.416667
Call that x2, plug that in again, we get:
x = x2 - (x22 - 2) / 2x2 = 1.414216
We're getting pretty close eh?

When do we stop looping? Well, since we can't get absolute precision, we can stop looping when the xi is within a certain threshold of some error:
while |f(xi)| > ε
do iterative method
You can set this ε to whatever you want. A higher value will mean less precision but more speed - however the iterative method moves pretty damn quickly toward the zero so it is not a huge deal.

There's a few catches. What would happen if we used a guess of zero? Well, we'd end up with a divide-by-zero error. Basically the linear approximation to f would be flat, and never touch the x-axis.
What would happen if we used a negative guess? Well, that leads to a more interesting discussion. Newton's Iterative Method finds local zeroes. The closest zero to a negative number (say -1) is not around 1.41421. It is close to -1.41421, which is the other square root of 2. When there are multiple zeroes to a function, the iterative method will tend toward which ever one it is sloping toward. So if you're trying to find the zero of a function that crosses the x-axis several times, choose your initial guess wisely!

Finally, here's an interesting problem. Try finding the square root of -1 using this method. Try it with different guesses.

1If you don't know what a derivative is, it is the function which tells you the slope of f at any given value of x.

Jun 4, 2009

Glassfish, JRuby and Initialization Parameters

Sometimes in your Rails app you may want to pass some variable to your program, via an environment variable or something. With a regular Rails app, you can just do `export VAR_NAME=something` and it will detect it just fine. However if you're deploying in a container-based server like Glassfish or Tomcat, you'll have to pass the config values in a different way because it doesn't seem to pick up the enviroment variables.

You can do this with your warble config. If you haven't already done so, create your warble config file like this:
jruby -S warble config
This will create a file at config/warble.rb in your Rails app. Inside there you'll see all sorts of config settings for the JRuby environment.

What I wanted to do was output the SVN info on the site, so that when we were testing in the Glassfish environment we could see what revision we were working with. So I just had this little snippet of code:
`svn info` =~ /Revision: (\d+)/
revision = $1.to_i
Spit that out on the page somewhere and everyone can see what revision they're working with!

However the hard part is getting this into the WAR. What you have to do is pass it as a parameter in the warble config, like this:
config.webxml.svn_revision = revision
When warble runs, it will output this into the web.xml file within the WAR, which will get passed to your server.

To access this value from within the Rails app, you need something like this:
if defined?(JRUBY_VERSION)
revision = $servlet_context.getInitParameter("svn_revision")
end
If you're only ever running in JRuby then you don't need the if defined? junk.

The $servlet_context object is a Java object that represents the servlet context. I actually don't really know what that is, but a quick search of the docs gives a handy bit of info and the one you want is the getInitParameter method.

Jun 3, 2009

Find What You Like In Your Language(s)

After one has been programming for several years and has messed around with enough languages, you start to notice that you like some languages better than others (and feel the need to tell the world this). This type of feeling is completely subjective and usually based on experiences with the different languages, and is quite different from programmer to programmer. I've met programmers who refuse to use any language that is interpreted or run inside a VM, at the same time I've met programmers who refuse to use any language that doesn't use garbage collection - for completely different reasons (if you must know, the first ones hated wasting the users' time/resources, the second ones hated wasting their own time/resources).

I'll share my story with you. I like to program in Ruby - in case you haven't noticed at this point. However, I also still like to program in C++. Anybody who has seen both of these languages (or have even met people who are fans of either language) can be completely boggled as to why, myself included. They are so completely different that it is almost surprising to say they are both imperative languages (you can get more different by going into functional languages like FORTH, but we won't go there right now).

However I've realized there are three things that I like about coding - freedom, elegance, and speed. It's really difficult to find a language where you can have all three of these while still having the available libraries for me to make games or web apps in (the only apps that I really like to program it seems). Freedom is present in both C++ and Ruby - it is the idea that there are many ways to solve a given problem. This is what really turned me off Java1 and to a lesser extent, Python2; and makes me pick C++ over C.
It is the other two that these two languages are at odds with. You don't really get faster than C++ - unless you're a whiz with assembly, which I am not. C might be faster, but I loves me the STL and the Boost. With C++ you have access to OO solutions and the security of a rigid type system (although I have to say I was amazed by the wonderful combination of flexibility and security in Haskell's type system). It seems like if I can write code that is really fast, not too much else matters - for example I ditched the std::complex class in favour of three doubles for my fractals implementation, it was a speed increase of like 10x which basically made it go from taking several seconds per frame to pretty much real-time. It's probably because g++ decided to put those doubles as floating point registers or something, where the complex objects were just being stored in RAM. I could probably find out for sure by doing an ASM dump of the code, but it's late and I'm going to sleep soon. Maybe I'll post on it some other time. Anyway, it finally occurred to me to upload this (a few months late), so take a look:


ASIDE: After watching this video I realized that this has been converted from screen capture to Ogg/Vorbis to AVI to FLV - if you want the code to watch it yourself, you can grab it here. It requires SDL and a C++ compiler.

At the same time though, Ruby is expressive. I can say what I want to say easily (more so than with pretty much every other language I've used - maybe I still have my head in the box and need to branch out more) and elegantly. It is the aesthetics of the language which appeals to me at a higher level. One thing that annoyed me when using Python was when I wanted to do string processing - Ruby's regex handling is amazing, especially when coupled with the OO aspect. And long method chains seem to have a much nicer flow to them than something like foo1(foo2(foo3(x))), so long as you don't have too many blocks thrown in. And finally, the fact that EVERYTHING is an object, and EVERYTHING works like an object (sorry Python, you're nice and all but things like len(str) annoyed me from this perspective), and finally EVERYTHING is modifiable. While Ruby's monkey-patching can be a royal pain in the ass even when used by people who know what they are doing, it is basically the language designer's way of saying, "I don't know everything. Have at 'er." I respect that a lot and think that it is a great way to make the language evolve.

So, what is it that you like?

1Note that I am not saying Java is bad - I know plenty of good programmers who I respect that love Java (and/or Python for that matter). I'm just saying that its way of doing things are not really the way I like doing things, I find myself fighting it more often than not.
2I actually kinda like Python. I respect it because it does what it wants to do really well - basically saying there is one way to do something, and not getting in your way while you do it. A thing that I love and hate about Python is that it removes the need for the thought, "I can think of multiple, equally good ways of doing this, but which is the most elegant?" With Python you just do whatever works. It bugs me and relieves me at the same time because sometimes I can think of a solution that is more "elegant", but not really any better (and possibly worse).

Jun 1, 2009

KDE, revisited

The other day I posted about me trying out KDE, and my first impressions of it. I've been using it a bit since then to see how I like it.

Initially it blew me away, since the default look and feel is much nicer than GNOME. It's not grey and brown anymore, there are smooth animations and fading effects, etc. etc. It feels much more modern and appeals on a more aesthetic level.

However after I started using it more, there was just a few too many things that annoyed me for me to really want to keep using it. I will probably try and see how to fix some of the problems but for now it is easier just to stick with GNOME.

Here's a list of the annoyances I've had. Note that a lot of them I could probably fix by either searching through their settings panels, or scouring the Internet. However it is just easier for me to switch back to GNOME, which is already pretty much the way I like it.
  • Panel widget sizing - the widgets on your panels seem to have no maximum size, so they just expand to fill up the whole panel. This is really really annoying, because the little cashew thing on the right hand side overlaps the widget that is furthest to the right. Also if you like to use programs like Avant Window Navigator (AWN) like I do, there is no need for the "task manager" widget that shows the open windows. However if you remove it, the other widgets will expand to take up the entire space. Nothing like a clock widget that is 300 pixels across. I ended up having to split the one panel into two, with a huge gap in the middle. Kinda broke the aesthetic aspect there.
    This was something that I did try to look up online how to fix. Apparently there is a "Spacer Widget" that you can get that just takes up empty space, however it was not available through their auto-download thing and I didn't really feel like searching for it. On top of that it feels like a rather ugly way of handling this.
  • Cashews. The little cashew thing is for tweaking settings. It's nice to have it right there in front of you the first time you try KDE because that way you have easy access to make your tweaks. However after you make your tweaks, they are still there in the way of what you are trying to do. A good alternative would be that you right-click on the panel and go to "Settings". Oh wait, they do that. So why would they have the cashew thing?
  • Desktop - Where did all the files on my desktop go? I put lots of files on my desktop either for quick and easy access, or for reminders of a program that I'm supposed to check out - although it is surprisingly easy to forget the things that are right in front of you all the time.
  • The menu - I like the favourites part. And the search feature. However I have counters: with a dock there isn't really a need for the favourites list, because you just put your favourite programs on the dock. And the search feature seems to only be useful for me since the damn menus are a bit more of a pain to navigate! With old-school menus I just need to mouse over things and they open. If I open the wrong menu, it is trivially easy to go back to another one since I can still see it (and am likely still looking at it). Instead with KDE, it is a bit more work to actually have to navigate to the menu, so you just type it in the search field instead. I suppose some people may prefer this over the GNOME menus but I'm not sure if I do.

Anyway these are the little things here and there that I didn't like so far. I'll probably switch back and forth between KDE and GNOME until I get KDE working the way I want it, or when I finally get completely annoyed and stick it out with the less nice aesthetics of GNOME.

May 30, 2009

KDE

I'm giving KDE a shot with kubuntu-desktop. So far it seems pretty slick! The interface reminds me of SPORE.
Out of the box it is much more visually appealing than GNOME, and some of the feature seem kinda nifty. It seems they took some hints from Mac and Vista, where it seems like GNOME is still sticking it out with the minimalist idea.

Only problem so far: avant-window-navigator crapped out right away, but I just restarted it and it seems to work fine.

I'll post more on this later, maybe even give some tips on how to get things working under it if I run into problems.

May 14, 2009

SVN plugin for Vim

For those of us too lazy to use an IDE or fancy graphical front-ends to SVN, here's a nice little plugin for vim to help you with commit messages:

http://www.vim.org/scripts/script.php?script_id=978

When you use 'svn commit' and it opens vim, it will show two windows: one with the normal SVN commit message, and the other with the output of 'svn diff', which is handy when you want to remember what you had changed.

A shortcut that is very handy to know for this is Ctrl+W+W (that is, hold Ctrl and hit w twice), which is to switch between vim windows.

To install it, just drop the script in ~/.vim/ftplugin, and make sure that your ~/.vimrc file has the following:
filetype plugin on

May 10, 2009

Identity

Not too long ago someone I know wrote a post about identity and the question, "Who are you?" He says that our usual answer to this question is first our name, and then our occupation; he then goes to say that this answer is wrong.

After reading this, I found myself asking the same question - Who am I? No, who am I really? Rob? Well, yes, but a name is simply a label used to identify you. Kinda like a variable in your code if you named your variables Valerie or Steve or something - which would make for horrible programs, maybe we should all name our children when they're 20 or something after what they do, like Makes-Good-Hot-Chocolate or something. Those native peoples had something going there.

However after a fair bit of thought on the matter, I inevitably came to the thought, "Well, if I'm trying to figure out who I am, what is identity?" That is another slightly tricky one to put your finger on. Fortunately I went on vacation last week, so I had plenty of time to sit around and ponder.

I came to the following answer, feel free to debate: your identity is defined by what do you and/or what you believe. It is a collection of what I'll call "identity elements". I am a professional software programmer - why? Because I program software professionally. I am an amateur software programmer - I write code in my spare time for no real reason other than to see what happens. I make wine, play guitar; I believe in mostly free markets and science. I could go on like this for a long time. The accumulation of these identity elements is what makes up your identity.

It gets more complicated than that: some identity elements have more weight to them. Which of these elements has the higher weights is heavily influenced by your society and consequently (most of the time) the weight that you yourself apply to them. In Canada and most of the Western world it seems that your job has a higher weight than what you do Saturday nights - although if you do really weird things on your Saturday nights then perhaps that will more heavily influence the weight of that element, but then again "weird" is also defined by the society in which you live.

When you find that your identity is not really what you want it to be, then you're at a bit of an identity crisis. Maybe this crisis is better defined as lack of job satisfaction, boredom, feeling like you're not doing anything with your life, who knows. They're all pretty much rooted in the same thing.

So what to do? I suppose I'll play expert on this topic for a little while, although I am far from the ideal person to do so. I'd say look at these identity elements and see what you can do to affect the ones that you are not happy with. If you are not enjoying your job, why not try and figure out why? See what you can do to change it.
Sometimes you can't do anything to change these major aspects. Maybe you can't just quit your job, or change your significant other, or move to a new city (or maybe you can and you're just telling yourself you can't). In this case, it is important for your mental health to turn to the other elements of your identity and focus on improving those - and oftentimes it is much easier to change those than in the larger elements.

Rereading this, I noticed that part of this is about attaching yourself to some label(s). Many people believe that removing these labels is a good thing - reminds me of high school with the "anti-conformist" kids who shunned labels and sheeplike behaviour, meanwhile all of them seemed to be moving in the same direction and doing what each other was doing; all they did was trade one label in for another.
I don't think that these labels are completely bad, the important part is simply realizing what the labels are and arranging your labels in a way that satisfies you.

Keep in mind that change takes time. If you want to change your job, it is not a good idea to just drop it and quit (I've sorta done this, not a good idea!), instead just keep going, searching while you're working, or if you really hate it maybe save up some cash so that you can spend some time looking for a new job without worrying too much about finances.
Set goals for yourself and work to attain those goals. Don't expect them to be attainable immediately, and don't despair when it seems like your goals are so far away that they are out of reach. When I graduated from university I had lots of debt - maybe not as much as some people I know, but it certainly seemed like a lot to me. My goal was to pay that down as soon as possible, and not too long ago I did (yay!). Now I have new goals - finish studying! Learn French!

Perseverance is the key to attaining your goals. I know it is hard, but the rewards when you complete those goals are well worth the effort. Thanks for reading.