Java vs Javascript: Speed of Math

Java vs Javascript: Speed of Math

Last week I’ve created a ray marcher 3d engine which renders the Mandelbulb. And I’ve translated it into pure Javascript a couple of days later. After the translation I decided I should optimize the code a little for speed, so I made some speed improvements in the Javascript code. The main optimization was using an array for the vector3d instead of a class/function.

Rendering the Mandelbulb on a 400x400 canvas now took just 1850ms in Javascript (Chrome, V8). Which is very fast! Even faster than my Java implementation (running on Java 1.6.0.33 -server, which was faster than Java 7). But the Java code didn’t have some of the speed optimizations. So I re-translated the Javascript code back to Java. It produced the following numbers (lower is better performance):

Comparing Javascript and Java

What has happened here? The output is the same, why is Java so much slower than Javascript? I would have suspected the opposite…

I fired up the profiler to see what was causing the Java code to be so slow, and it turned out the method it spend most time in was Math.pow(). Other slow methods were Math.acos(), cos(), sin() etc. It turns out that the Math library isn’t very fast, but there is an alternative, FastMath. Apache Commons has implemented a faster Math library for commons-math. Lets see what changing Math.* to FastMath.* does to the performance:

compare2

This is already much better. But still the method causing most delay is FastMath.pow(). Why is Javascript so much faster? The method is made so you can calculate the power of two doubles, not only integer values. But I’m only doing Integer powers (7 and 8 to be precise). So I decided to implement my own method:

private double fasterPow(double d, int exp) {
	double r = d;
	for(int i = 1; i<exp; i++) {
		r *= d;
	}
	return r;
}

Warning: This isn’t the same as Math.pow/FastMath.pow!

compare3

The speed with this new method is much better and seems comparable with Javascript. Maybe this is an optimization the V8 engine does by default? Who knows.

The slowest method in the program now is FastMath.acos. From highschool I know that acos(x) can also be calculated as atan(sqrt(1-x*x)/x). So I created a own version of acos. When benchmarked, the different methods: Math.acos(), FastMath.acos() and FastMath.atan(FastMath.sqrt(1-x*x)/x), the result is again surprising:

compare4

The custom acos() function is a bit faster than FastMath.acos() and a lot faster than Math.acos(). Using this function in the Mandelbulb renderer gives us the following metric:

compare5

So it turns out that with a bit of tweaking we can get the Java version faster than Javascript, but I would have never imagined Java would be slower in the first place. The Chrome V8 guys really did an amazing job improving the speed of their Javascript VM. Mozilla isn’t far behind, they are getting +/- 2200 ms in the benchmark. Which is also faster than Java.Math and FastMath! It seems that V8’s math implementation has some optimizations that Java could really use. The tricks used above don’t make any difference with the Javascript version.

Edit 1: Is Javascript faster than Java?

Well surprisingly in this case it is. With the code a 100% the same, using arrays as vector and Math.* the code actually runs faster in my browser!

Edit 2: People have been asking me: What could have been done to make it faster in Java? And, why is it slow?

Well the answer is twofold:

1) The Math libraries are made for ‘double’ in Java. Having a power() method work with doubles is much harder than working with just integer numbers. The only way to optimize this would be to overload the methods with int-variants. This would allow much greater speeds and optimizations. I think Java should add Math.pow(float, int), Math.pow(int, int) etc.

2) All the Math libraries have to work in all situations, with negative numbers, small numbers, large numbers, zero, null etc. They tend to have a lot of checks to cope with all those scenario’s. But most of the time you’ll know more about the numbers you put in… For example, my fastPower method will only work with positive integers larger than zero. Maybe you know that the power will always have even numbers…? This all means that the implementation can be improved. The problem is, this can’t be easily achieved in a generic (math) library.


Introducing: mandelbulb.js

Introducing: mandelbulb.js

This afternoon Will (the friend I mentioned in this previous post) showed up again on Google Talk.
He set me a new challenge: “How about translating your 3d engine/mandelbulb code into pure Javascript?”

First Mandelbulb render, full of programming bugs

This seemed impossible, but I quickly realized the code I had was very easy to convert. It is my first piece of Javascript larger than 10 lines I think, but it is working!

If you have a bit of time:

mandelbulb.js

Any Javascript developers who would like to take the code and improve on it (trust me, there is more then enough room for improvement) go ahead! I’m releasing it under creative commons, do with it what you like, just be sure to mention me!

The code can be found here: https://github.com/royvanrijn/mandelbulb.js

I’ve already included one improvement by Will himself, scanlines to smooth up the rendering (good for inpatient people!).


Mandelbulb rendering

Mandelbulb rendering

Last friday a friend of mine was talking about ray marching, the Mandelbulb and programming his own 3D fractal engine. He also kind of challenged me to do the same… So I picked up the challenge and set to work on my own 3D (CPU only) ray marching fractal engine (in Java). It was a very steep learning curve for a programmer with limited math knowledge, but I’m pretty pleased with the first results!

My first 3d engine (tm)

On sunday I had the first things ready, lighting (Blinn-Phong), soft shadows, but still I had no perspective build on (all rays travelled in the same direction) and I had no way to change the view point/camera position:

Simple ray marching example, wrong perspective, two balls and a cube

Next step was to render something other than spheres and cubes, and get the camera position under control, that breakthrough came monday evening:

First Mandelbulb render, full of programming bugs

My first mandelbulb! The perspective is still flat and it misses detail, we’ve also rendered through the camera/near field.
So I made some more improvements and managed to render a nice wallpaper for myself:

First Mandelbulb render, full of programming bugs

Yesterday I’ve been playing around with optimizing the code a little bit (less memory usage, already twice as fast as it was, but still slow). And I’ve added some glow and the ability to add ‘distance fog’. Also I’ve recorded my first movie, just to show some moving fractals:

(yes, it has a glitch with the pink mandelbulb, can’t be bothered to fix…)


Rotoscoping in Prince of Persia

Rotoscoping in Prince of Persia

This afternoon I was reading about rotoscoping. Rotoscoping is a technique where an artist takes a filmed movie and animates a drawn (cartoon) character frame by frame. The end result is highly realistic. The technique was first used in 1915’s with an ink cartoon called Out of the Inkwell and has been used in many cartoons since.

But what about video games?

It turns out that Prince of Persia was the first computer game to use rotoscoping. That game brings back a lot of good memories to me, and probably everybody my age.

After a quick search I found this little gem of a video:

The person in the video is David Mechner. He is the younger brother of Jordan Mechner, the creator of Prince of Persia.
Jordan used the clips shown above to rotoscope the movements of the main character in the game.

I had never realised why I loved Prince of Persia so much in my youth. But now I think it is probably because of rotoscopy! The animations are so realistic and life like, it has brought a whole new level of realism into video games.

Here is another video of Jordan, showing even more rotoscoping in Prince of Persia:

And the icing on the cake, a video about rotoscoping in Mortal Kombat 1:


Getting started: Arduino Mega

Getting started: Arduino Mega

A couple of days ago I’ve received my Arduino Mega in the mail. Together with a breadboard, some plug-wires and Arduino-starters kit (with some resistors, capacitors, and a couple of sensors).

arduino_mega

Arduino?

The Arduino is a handy little board with micro controller. It allows you to connect your computer using USB to the micro controller and easily program and upload the program to the board. I’m a very experienced programmer with almost no experience in electronics.

I know what a resistor is and what it does, but I have no idea how/when to use which resistor. But I’d love to learn more, maybe even build some toy robots in the end. A final goal would be to have a working humanoid with 20+ servo’s, but that goal might be a bit out of reach…

The examples

The first thing I’ve done after unboxing the Arduino was plugging it in my laptop and browsing to the arduino.cc website. There you can download the Arduino IDE.

In the ‘Learning’ section (http://arduino.cc/en/Tutorial/HomePage) you’ll find everything you need to get started. There are diagrams on how to wire everything into the breadboard, and there are also code examples.

Some stuff I made using the ‘Learning’ page:

  • Blinking LED (the hardware Hello World, yay!)
  • Slowly fading blinking LED
  • Knight rider, KITT LED bar
  • Tiny keyboard with 5 buttons
  • Light reactive theremin

And some projects that aren’t on the example page, but could be made using the things I’ve learned:

  • Extended keyboard with 5 buttons and LEDs!
  • Light reactive LED bar (showing the amount of light in LEDs)
  • Knock-sensor, LED shows when it ‘feels/hears’ a knock

All the above was made in a single evening! And there is much much more that you could make with the Arduino. I haven’t even started using servos and/or DC motors. The only problem left is lack of imagination!

For a programmer the code is very easy to understand, and the Arduino Programming Language used is closely related to the C/Java family.

/*
  keyboard
 
 Plays a pitch that changes based on a changing analog input
 
 circuit:
 * 3 force-sensing resistors from +5V to analog in 0 through 5
 * 3 10K resistors from analog in 0 through 5 to ground
 * 8-ohm speaker on digital pin 8
 
 created 21 Jan 2010
 modified 9 Apr 2012
 by Tom Igoe 

This example code is in the public domain.
 
 http://arduino.cc/en/Tutorial/Tone3
 
 */

#include "pitches.h"

const int threshold = 10;    // minimum reading of the sensors that generates a note


// notes to play, corresponding to the 3 sensors:

int notes[] = {
  NOTE_A4, NOTE_B4,NOTE_C3 };

void setup() {

}

void loop() {
  for (int thisSensor = 0; thisSensor < 3; thisSensor++) {
    // get a sensor reading:

    int sensorReading = analogRead(thisSensor);

    // if the sensor is pressed hard enough:

    if (sensorReading > threshold) {
      // play the note corresponding to this sensor:

      tone(8, notes[thisSensor], 20);
    } 
  }
}

The language has borrowed a lot of syntax from C, but there are some tricky issues (in the eyes of a programmer). For example:

int sensorValue = analogRead(A0); 
String stringThree = "Sensor value: " + sensorValue;
Serial.println(stringThree);

This little piece of code above gives unpredictable results because ‘stringThree’ never got an initial value before you started concatenating different data types. Instead you’ll have to do:

int sensorValue = analogRead(A0); 
String stringOne = "Sensor value: ";
String stringThree = stringOne + sensorValue;
Serial.println(stringThree);

Weird…! But I really suggest trying out the Arduino, give it a chance and you’ll probably like it and learn a lot about electronics and microcontrollers.


We are now cached

We are now cached

Yesterday we (at JPoint) invited Stefan Tilkov over for a discussion about REST and RESTful services. He knows a lot about the subject and could educate us and help with any questions.

One of the things he mentioned was: If you don’t use caching, you are an idiot.

Where do websites cache?

There are multiple tiers where caching of websites is done, and is useful.

Browser cache

The best cache you can have is the cache inside the browser. If a website knows it has the latest version, it can just read it from disk. There is absolutely no reason to go online.

Proxy cache

The second type of cache would be the proxy cache. As you would have guessed this is a proxy and it does caching. It sits between the user/browser and the internet gateway. This cache sees all the requests and stores pages that can be cached. If another user requests a webpage that hasn’t changed it can provide the page instantly.

Reversed proxy cache

You could also have a cache between the internet and the content providing server. If the server processes the request it might need to access databases and maybe other slow resources to build up the webpage. The resulting page can than be cached on the providing side in a “reverse” proxy cache. All subsequent requests can just be provided from the cache, as long as the page is still fresh.

Making pages cacheable

If you maintain a website, or you create web applications, you should be aware of caching. After Stefan’s rant, I’m completely convinced about that. If you don’t do anything all the requests will always go into the server and over the internet. There are HTML ways to control caching (META-Tags etc) but this just doesn’t work, and shouldn’t be used (!). So what could we do?

Expires header

When sending a page back to the user you are able to set some HTTP headers. And “expires” is one of them.
An example:

Expires: Fri, 11 May 2012 18:19:42 GMT

This indicates that the current page is valid until the timestamp. Then it ‘Expires’. Easy!

The only problem is generating the timestamp, it can be a bit tricky. Also you’ll have to be sure you’ve set the time correct on your system. Also, the next time you update the page, you have to also update the timestamp!

Cache-Control headers

With HTTP 1.1 there is a new class of headers called “Cache-Control”. These headers are more powerful than the Expires header.
To enable caching using Cache Control headers you can set:

Cache-Control: max-age=3600, must-revalidate

The “max-age” is time in ms that the current page is valid. And by adding “must-revalidate” we tell the cache it should obey our max-age. If you don’t want an object to be cached you can use:

Cache-Control: no-cache

Refreshing cached data

The two methods described above will tell the cache if the content is cacheable. But what happens when the max-age or Expires timestamp expires? There are smarter ways to update the cache instead of getting the latest content from the server.

Last-Modified

Websites should always set the response header called “Last-Modified”. This is a timestamp of the moment a webpage last changed.

Last-Modified: Fri, 11 May 2012 18:19:42 GMT

When a cache has expired (max-age or Expires) and has to get a new version from the server it can set the request header “If-Modified-Since” and include the timestamp.

If-Modified-Since: Fri, 11 May 2012 18:19:42 GMT

If the content on the server hasn’t been changed it’ll reply “304 Not Modified”. The cache can now keep the cached version.

ETag

With HTTP 1.1 there is also an improved method of doing the “Last-Modified”. Instead of using a timestamp (which is error prone), they’ve introduced the “ETag”. This is a tag that is completely customisable. Most of the time it will just be a hash of the content. The server sets the ETag as response header:

ETag: "686897696a7c876b7e"

When a cache can no longer use the cached version (due to max-age or Expires) is will ask the server:

If-None-Match: "686897696a7c876b7e"

The term “If-None-Match” isn’t very clear, but is means “if-etag-changed-since” and works the same way as “If-Modified-Since”. When the ETag is the same the server will reply “304 Not Modified”, it won’t send the content back.

When you are working on a web application you could just add an ETag which is the MD5 of the returning content. If the content is the same, you don’t have to send the content over the line. The only drawback to this method is that you still need to generate the entire reply to calculate the MD5 hash to see if the content has changed…! But sometimes you’ll know in advance if the content has been changed.

Improving royvanrijn.com

I’m using WordPress and I’ve found the excellent plugin “WP Total Cache”.

It will involve a bit of tweaking, because only you can decide which stuff should be cached. But I think it worked out great, press F5 right now and you’ll probably be reading this from the browser cache.


Ludum Dare #23: Itty-bitty botty

Ludum Dare #23: Itty-bitty botty

bodyIdle1The last two days I’ve been competing in a competition called Ludum Dare.

This is a short, 48 hour, contest. In this time you have to build an entire game based on a theme given at the start of the 48 hours. It is a good exercise is planning, scaling, hacking, imagining and just having fun! I really enjoyed it, and recommend you join LD24 four months from now.

The concept:

For this game I decided to stick with Java. To make it playable for as many people I decided to make an Applet. It can easily become a standalone app, or maybe an Android app…!
I loved the old point-and-click games, from Dirty Larry to The Day of the Tentacle, from Monkey Island to Gobli(iiii)ns. So that was settled.

The big pro:

Not a lot of physics or game code.

The big con:

I’d have to brush off my paint skills because point-and-click adventures are filled with graphics and animation!
One big factor in games is music, and for this contest I took some midi control code I made some years ago. This was turned into a procedurally generated music generator. Every time you play you’ll hear something new.

The result:

With visitors coming to see our little baby girl on Sunday I decided to end early.

Screenshots:
screenshot1
screenshot2

Here is my result, have fun playing the game: Itty-bitty botty!


Female coders, lighten up

Female coders, lighten up

female-sign

The Real Katie

Today I stumbled upon the following blogpost:
The Real Katie - Lighten Up

Katie talks about the sexist jokes and remarks she regularly gets in the IT/programming world, and she is sick and tired of hearing “Come on, lighten up”.

The post is moving and shows how easy it is to offend people, not by a single remark, but by hundreds of similar remarks heard before.

Not an IT problem

There is one point I don’t agree with though. I don’t think it is fair to call this an IT/programmers problem.

Let me explain:

Obviously there are a lot of jerks, assholes and plain rude people around. Most of them are men, some are women. They pick on easy targets, the minorities. Sometimes the minority is a heavy male co-worker, sometimes it is the rare female programmer.

I fully agree, we should call the bullies out more. We all should do something about this problem. Her blogpost has re-opened my eyes again to that problem. But this isn’t a IT problem… it is a minority and rude people problem, a global social problem. It happens in all professions. Katie is just unlucky to be the minority in the field of work she loves.

More women in the IT

Also, I do agree that we could use more women in the IT world. At a young age we should teach boys and girls that there is no such thing as boy-jobs and girl-jobs, and both should learn the joy of programming! If we do that the problem of women being a minority in the IT world will disappear.

BUT that won’t solve the global social problem of assholes picking on minorities.
That is something we are all responsible for.

There will always be minorities and there will always be rude people (male or female). This is something we can’t change. You can however call them out and disapprove the behavior.


Arthur Fry Day (or: Fryday)

Arthur Fry Day (or: Fryday)

Scrumboard

Inventor of the Post-It note, and part time hero.
Source: wikipedia.org

Our project is doing Scrum, and one of the main aspects of Scrum is having everything clearly visible. A great example is the scrumboard, a huge whiteboard filled with Post-It notes.

Post-It notes are perfect for this; small enough to be easy to handle; sticky enough so you can post them almost everywhere. I truly believe that without the Post-It note, Scrum wouldn’t be possible and probably wouldn’t even exist!

The hero

This all makes the real hero of the Agile movement: Arthur Fry. After somebody at 3M messed up a batch of glue, Arthur decided to add that glue to a piece of paper, creating the first Post-It notes.

Join us

This invention is much more important than the toilet, or wheel, or penicillin…! Celebrate and make the world aware of this unlikely hero, join us and celebrate Arthur Fry Day, this March 16th!

We've already started our preparations, #arthurfryday
#arthurfryday


Devoxx 2011: Talk freely available

Devoxx 2011: Talk freely available

Moments ago this tweet caught my eye:
Devoxx 2011: "What Shazam doesn't want you to know!" by @royvanrijn is now freely available @ http://parleys.com/d/2869

That means everybody can now watch my talk without any subscription! If you want to learn how algorithms like Shazam work, be sure to watch this talk. It might be easier to understand than my blog post a year ago.

Without further ado:


Levenshtein Distance Challenge: Causes

Levenshtein Distance Challenge: Causes

Today I’ve been playing around with the Levenshtein distance. The Levenshtein distance is a number which measures the ‘distance’ between two strings. For example, the distance between “test” and “rest” is one.

The challenge

A Levenshtein distance of one is the key element in a challenge I’ve been reading about. I first encountered it on williamedwardscoder’s blog.

The problem description:

Two words are friends if they have a Levenshtein distance of 1. That is, you can add, remove, or substitute exactly one letter in word X to create word Y. A word’s social network consists of all of its friends, plus all of their friends, and all of their friends’ friends, and so on. Write a program to tell us how big the social network for the word “causes” is, using this word list. Have fun!

Java solution (8.1 sec)

After some Googling and tweaking I decided to make an implementation based on the Trie structure. How this helps is excellently described by Steve Hanov. I’ve also had a peek in another Java based Trie implementation by Ximus.

I’ve been able to get the code below run in 8.1 seconds, which is pretty good. But I’ve read that there are Java implementations running in just 4 seconds…!? Maybe based on Levenshtein Automata?

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.LinkedList;
import java.util.List;

public class FriendlyCauses {

	public static void main(String[] args) throws Exception {
		FriendlyCauses s = new FriendlyCauses();
		s.find();
	}

	TrieNode[] root = new TrieNode[26];

	public void find() throws Exception {
		long timeBefore = System.currentTimeMillis();
		File wordList = new File("word.list");
		BufferedReader reader = new BufferedReader(new FileReader(wordList));

		int wordsAdded = buildTrie(reader);
		System.out.println("Done building the Trie; " + wordsAdded + " words added.");
		findFriends("causes");
		System.out.println("Amount of friends found: " + countWords(root));
		System.out.println("Total time: " + (System.currentTimeMillis() - timeBefore) + "ms");
	}

	/**
	 * This method builds the complete trie with all the words.
	 */
	public int buildTrie(BufferedReader reader) throws IOException {
		int wordsAdded = 0;
		while (reader.ready()) {
			String next = reader.readLine();
			int start = next.charAt(0) - 97;
			TrieNode current = root[start];
			if (current == null) {
				root[start] = current = new TrieNode();
			}
			for (int i = 1; i < next.length(); i++) {
				int nextIndex = next.charAt(i) - 97;
				if (current.children == null) {
					current.children = new TrieNode[26];
				}
				if (current.children[nextIndex] == null) {
					TrieNode deeper = new TrieNode();
					current.children[nextIndex] = deeper;
				}
				current = current.children[nextIndex];
			}
			current.word = next;
			wordsAdded++;
		}
		return wordsAdded;
	}

	private class TrieNode {
		// The children:

		TrieNode[] children;
		// If this node is the end of a word, store the word here:

		String word;
		// This boolean indicates that the current node is a friend.

		boolean isFriend;
	}

	// Temporary buffer of friends to investigate further:

	public List<String> friendsToFind = new LinkedList<String>();

	public void findFriends(String word) {
		friendsToFind.add(word);

		while (friendsToFind.size() > 0) {
			String friend = friendsToFind.remove(0);

			int size = friend.length();

			byte[] currentRow = new byte[size + 1];
			for (int i = 0; i <= size; i++) {
				currentRow[i] = (byte) i;
			}

			// Search the Trie for the given friend:

			for (int i = 0; i < 26; i++) {
				if (root[i] != null) {
					searchTrieForWord(root[i], i + 97, friend, currentRow);
				}
			}
		}
	}

	/**
	 * Walk the complete Trie again finding all the friends
	 */
	private int countWords(TrieNode[] ts) {
		int amount = 0;
		for (int i = 0; i < 26; i++) {
			TrieNode t = ts[i];
			if (t != null) {
				if (t.isFriend) {
					amount++;
					// Print/add t.word

				}
				if (t.children != null) {
					amount += countWords(t.children);
				}
			}
		}
		return amount;
	}

	/**
	 * Recursively walk the Trie calculating the Levenshtein distance to the
	 * given word. When a friend is found, mark it and add it to a list. The new
	 * friend needs to be processed further on.
	 */
	private void searchTrieForWord(TrieNode node, int letter, String word, byte[] previousRow) {

		int size = previousRow.length;
		byte[] currentRow = new byte[size];
		currentRow[0] = (byte) (previousRow[0] + 1);

		int minElement = currentRow[0];

		for (int i = 0; i < size - 1; i++) {
			int newCurrentRowValue = currentRow[i] + 1;
			newCurrentRowValue = Math.min(newCurrentRowValue,
					previousRow[i + 1] + 1);

			if (word.charAt(i) == letter) {
				newCurrentRowValue = Math.min(newCurrentRowValue,
						previousRow[i]);
			} else {
				newCurrentRowValue = Math.min(newCurrentRowValue,
						previousRow[i] + 1);
			}
			if (newCurrentRowValue < minElement) {
				minElement = newCurrentRowValue;
			}
			currentRow[i + 1] = (byte) newCurrentRowValue;
		}

		// If the Levenshtein distance is 1 and the node at current depth is a

		// word (and not yet friend):

		if (currentRow[size - 1] == 1 && node.word != null && !node.isFriend) {
			node.isFriend = true;
			friendsToFind.add(node.word);
		}

		if (minElement <= 1 && node.children != null) {
			for (int i = 0; i < node.children.length; i++) {
				TrieNode child = node.children[i];
				if (child != null) {
					searchTrieForWord(child, i + 97, word, currentRow);
				}
			}
		}
	}
}

Orchard Planting: Greatest Common Divisor

Orchard Planting: Greatest Common Divisor

The Orchard Planting contest from infinite search space is over. So it is time for a quick write-up.

The rules are simple, on a grid of integers, place N points on the grid to get as much 4 points on a line and never more then 4 points on a line.

My big break-through was when I figured out a way to improve the calculation speed of a solution, and make it possible to extend existing solutions (going back and forwards). To do this I used a unique vector (greatest common divisor vector) which is the same for all point on the same line:

//Calculate unique vector(hash):

doubleIntVector(int x1, int y1, int x2, int y2) {
    int stepx = x2-x1;
    int stepy = y2-y1;
    int gcd = gcd(abs(x2-x1), abs(y2-y1));
    if(gcd > 0) {
        stepx /= gcd;
        stepy /= gcd;
    }

    if(stepx < 0) {
        return (10000 * -stepx) + -stepy;
    } else if(stepx == 0 && stepy < 0){
        return -stepy; //this looks curious... but fixed a bug

    } else {
        return (10000 * stepx) + stepy;
    }
}

Now we can evaluate the points:

for point A in points 0....N {
    create list vectorsA 
    for point B in points A+1....N {
         vectorA.add( doubleIntVector(A.x, A.y, B.x, B.y) )
    }
    sort(vectorsA)
    //if vectorsA has three similair vectors you have 4 points on a line! 

    //(3> = invalid and 2 = candidate for extending!)

}

If a point has three vectors that are the same, we have a line with four points! This can be checked easily if you sort the vectors and go through them once.

Also adding and removing points becomes very easy. A lot of the GCD calculations can be cached. To remove a point, just remove the vectors it made. And to add a point, calculate all the new vectors. So in the end it basically all boils down to a lot of GCD calculations and sorting.

Was this the fastest way to calculate solutions in this contest? I don’t know, but I was really pleased when I figured it out. With a better algorithm for picking possible numbers (instead of hill-climbing) and some more processor power I bet I could have ended a bit higher up the hill.

Also: Keep an eye out for the next contest, it is going to be an interesting one! January the 13th.


Parleys: Devoxx talk published

Parleys: Devoxx talk published

The guys at Devoxx/Parleys have already processed all the talks and post-processed them. So my talk it now available at Parleys.com.
There is one drawback though, the talk is currently for subscribers only. If you don’t have one you can only watch the first two (very nervous) minutes.

If you’ve attended Devoxx you will get a free subscription in the email.

(p.s. The intro movie for all the Devoxx ‘11 talks is made by me as well!)


Neil DeGrasse Tyson and Stephen Colbert

Neil DeGrasse Tyson and Stephen Colbert

Most internet videos are a waste of time, but this one isn’t! This is an interview of Stephen Colbert (out of his normal character) with Neil DeGrasse Tyson (Hayden Planetarium director, TV science host).


The project manager and his pregnant wife

The project manager and his pregnant wife

Adding resources

Today I’ve (again) seen this quote on Twitter:

“A project manager is someone who thinks that 9 pregnant women can create a baby in 1 month”

This obviously isn’t the case. The story demonstrates that adding more people to a team won’t (necessarily) make the team more effective. Because some processes can’t be cut into smaller pieces and taken up by more people. It will even cause a bit of overhead, more opinions and thus, more time.

Our feature baby (for real)

What about one woman?

Everybody knows 9 women can’t create a baby in 1 month… so it isn’t fair to make that comparison. How about one pregnant woman and the project manager?

Four weeks into the ‘project’ the project manager has his monthly meeting with his pregnant wife:

Month #1
Project manager: “How is everything going?”
Wife: “Oh, just fine, no problems at all”
Project manager: “Is there anything I can help you with?”
Wife: “No, currently not, everything is going like it is supposed to”
Project manager: “When do you think this baby-project is going to be completed?”
Wife: “Well, it takes 9 months, so 8 months from now!”

Month #2
Project manager: “Hey, is everything still going fine?”
Wife: “Yes, still feeling fine.”
Project manager: “Is there anything I can help you with?”
Wife: “No, nothing that I can think of right now.”

Month #3
Project manager: “Hey, still working on that baby?”
Wife: “Yes, I’m starting to have a bit of morning sickness now…”
Project manager: “Oh, can I help you with that?”
Wife: “Not really, it is just something I have to live with”
Project manager: “How does this affect the release date?”
Wife: “It doesn’t, I think… but I really wish we could release a bit sooner!”

Month #4
Project manager: “Hey, still having that morning sickness issue?”
Wife: “A little bit, but it is almost gone now”
Project manager: “Still on track for the release date?”
Wife: “Yes, 5 months from now!”

Month #5
Project manager: “How is it going? Morning sickness issue resolved?”
Wife: “Yes, but I need icecream and pickles.”
Project manager: “I’m on it. Any updates about the release date?”
Wife: “ICECREAM!”

Month #6
Project manager: “Anything I can do for you right now?”
Wife: “Yes, I think you can start building that baby room”
Project manager: “When do you need it, when is the baby ready?”
Wife: “Three months from now.”

Month #7
Project manager: “The baby room is almost ready, how is that baby going?”
Wife: “Just fine, just very tired. Two more months.”

Month #8
Project manager: “I’ve got some more pickles for you!”
Wife: “You know I hate pickles :-( I’m tired…”
Project manager: “Sorry, how is the release coming along?”
Wife: “One more month.”

Month #9
Project manager: “Is the baby there yet?”
Wife: “No, not yet, I’m tired but fine”
Project manager: “But…? What about the release?”
Wife: “Go away.”

Month #9 (plus one week)
Project manager: “What is the delay? Where is my baby?”
Wife: “It isn’t here yet.”
Project manager: “How come? How did this happen!? I kept asking about the release date and you kept saying it would be done a week ago!?”
Wife: “Get out.”

Month #9 (plus two weeks)
Wife: “I’m ready! I’ve got this lovely baby for you.”
Project manager: “Great, where did it go wrong with that planning?”
Project manager: “That babyroom has been ready for weeks now, and no baby!”
Project manager: “How can we keep this from happening next time? Scrum? Lean? Agile? RUP?”
Wife: “Screw you.”

This story also has an important message in it, I’ll just leave that as an exercise for the reader.