Regarding Haken's algorithm: It's not so hard to implement (it's essentially implemented in Regina, though at present you need to type a few lines of python to glue the bits together; a single "big red button" is on its way). However, it's hard to run, since the algorithm has exponential running time (and, depending on how you implement it, exponential memory use).
There are two facts that make Haken's algorithm easier to implement than many other normal surface decision algorithms:
- You only need to search through vertex normal surfaces, not fundamental normal surfaces (Jaco & Tollefson, 1995). Vertex normal surfaces are much easier (and much faster) to enumerate.
- The test that you apply to each vertex normal surface is relatively simple (see if it describes a disk with non-trivial boundary). For other problems (notably Hakenness testing), the test that you apply to each vertex normal surface can be far more difficult than the original vertex enumeration.
The reason Haken's algorithm is slow is that vertex enumeration is NP-hard in general. There are some tempting short-cuts: one is to run $3^n$ polynomial-time linear programs that maximise Euler characteristic over the $3^n$ possible combinations of quad types. However, experimental experience suggests that this short-cut makes things worse: solving $3^n$ linear programs guarantees $\Omega(3^n)$ running time even in the best case for a non-trivial knot. On the other hand, if you perform a full vertex enumeration (and you structure your vertex enumeration code well [1]) then you often see much faster running times in practice, even though the theoretical worst case is slower.
An aside (which has already been noted above): there are much faster heuristic tests for unknot recognition, though these are not always guaranteed to give a definitive answer. SnapPea has some, as does Regina. There are many fast ways of proing proving you have a non-trivial knot (e.g., invariants or geometric structures). One fast way of proving you have a trivial knot is to triangulate the complement and "greedily simplify" this triangulation. If you're lucky, you get an easily-recognised 1-tetrahedron solid torus. If you're unlucky, you go back and run Haken's algorithm. The interesting observation here is that, if your greedy simplification is sophisticated enough, you almost always get lucky. (This is still being written up, but see arXiv:1011.4169 for related experiments with 3-sphere recognition.)
Btw, thanks Ryan for dragging me online. :)
[1] arXiv:0808.4050, arXiv:1010.6200
