Yup. Applying Russian multiplication to matrices is surprisingly effective for evaluating recursive relations (it can evaluate the nth Fibonacci number in O(log

Yup. Applying Russian multiplication to matrices is surprisingly effective for evaluating recursive relations (it can evaluate the nth Fibonacci number in O(log n)) Karatsuba is also a nice 'proof-of-concept' algorithm (it shows that it is possible to do better than O(n^2) at multiplication in the simplest way possible) that's also very practical - and it has a nice anecdote behind it :)