Blog, by date: 2012_mar

from the desk of travis johnson.

fibonacci miles and kilometers (from 2012/03/29)

In my running, I have been trying to keep track in kilometers. This presents a couple problems: Somehow, my mind still thinks in miles, which is weird because I do not really have that good of an idea exactly how far a mile is, either. Or someone wants to know how far a 5k is. Or, when I was running the 2011 Chicago Marathon, there would be kilometer postings between the mile markers. Anyway, it is handy to convert between them, but a bit of a pain.

It turns out that the ratio of adjacent Fibonacci numbers are a decent approximation to the unit conversion between miles and kilometers. I decided to look into it a bit.

First, in case you have never seen or do not remember what Fibonacci numbers are, they are a sequence of numbers where the first two fibonacci numbers are and , and then each number after that is the sum of the immediately prior two. Mathematically, this is written as

$f_0 = 0, f_1 = 1, f_n = f_{n-1} + f_{n-2},$

which gives rise to the sequence

You can actually come up with a closed form solution for Fibonacci numbers, which is borderline incredible, using the recursion relationship given above. If you assume that f_n=lambda^n , then you get

$f_{n+2} = f_{n+1} + f_n implies lambda^{n+2} = lambda^{n+1} + lambda^n$

Then canceling a lambda^n from both sides, and rearranging you get that

You can use the trusty quadratic formula to solve this, it gives

$lambda^*_{pm} = frac{-(-1)pm sqrt{(-1)^2 - 4(+1)(-1)}}{2(1)} = frac{1pmsqrt{5}}{2}$

Clearly the $n^{th}$ Fibonacci number is not just this messy looking irrational fraction to the $n^{th}$ power, so we need one more trick. Introduce a couple of constants c_1 and c_2 , and let

$f_n = c_1(frac{1+sqrt{5}}{2})^n + c_2(frac{1-sqrt{5}}{2})^n$

Now, since we want f_0=0 and any number to the zeroth power is 1, we have that f_0=c_1+c_2=0 , or that c_1=-c_2 . Then $f_n = c_1((frac{1+sqrt{5}}{2})^n - (frac{1-sqrt{5}}{2})^n)$ . The final step is requiring that f_1=1 . This gives that

$f_1 = c_1(frac{1+sqrt{5} - 1 + sqrt{5}}{2}) = c_1 (frac{2sqrt{5}}{2})equiv 1 implies c_1 = frac{1}{sqrt{5}}$

Now, finally, we have that

$f_n = frac{1}{sqrt{5}} left( left(frac{1+sqrt{5}}{2}right)^n + c_2left(frac{1-sqrt{5}}{2} right) right)$

It seems I have run a little off track. What does all of this have to do with running? Well, the Fibonacci numbers eventually approach this fancy lambda_+ we came up with earlier, and it turns out that lambda_+ = 1.618 . It also turns out that one mile is about 1.609 kilometers. That is just 0.56% error! Sweet!

There is a catch though. Some Fibonacci ratios are better than others:

$f_n/f_{n-1}$	approximation	error
1/1	1	37.8%
2/1	2	24.2%
3/2	1.5	6.7%
5/3	1.666	3.5%
8/5	1.6	.58%
13/8	1.625	.97%
21/13	1.615	.37%

It looks to me like a sweet spot is at the 8 kilometer/5 mile mark. So now you can see that 25 miles is 40 kilometers, or whatever distance you wanted to know about in the first place.

digital photography (from 2012/03/29)

Recently I've decided to dedicate a slight bit of time to get a bit better at taking pictures. I'd always wanted to get a truly nice camera, and the opportunity presented itself, so I decided to go for it and bought a Nikon D5100 DSLR. I also ended up getting a complete steal on the Nikon 55-200mm DX VR lens, which was pretty awesome. Project 365 would be a great move from here, since I'm certainly no photographer, but it's been fun just learning about it all the ins and outs and how it all works together. In any case, I did start a Flickr: drtraviscj account which I'll be posting stuff.

More later.

tjtestharness - a language-agnostic DVCS unit-test/continuous integration tool (from 2012/03/26)

I've been wanting to have a way to visualize which unit tests(or sets of them) passed for a given commit, if for no other reason than the sense of accomplishment from watching boxes turn yellow, then green, as they pass tests. The trouble is, I write code in a lot of different languages for a lot of different projects. I also don't want to bother with running unit tests individually–I want them to run as I perform commits.

My main project right now is working on a fast quadratic programming(QP) solver for series of related QPs, and in turn using that QP solver as the basis for a sequential quadratic programming method with a penalty globalization. It's working okay, but there's a lot of levels to the project, and it's easy to make a change in one place in the code that has far-reaching effects on other parts. It's also got a very complicated structure for testing, because of the nature of nonlinear programming. Testing runs something like

First, need to check the most basic version of the QP solver itself, and how robustly it solves the most basic QPs.
Next we start adding in bells and whistles: We use a couple different types of numerical algorithm approaches.
There are also two functionally identical but yet distinct approaches to actually formulating the QP.
A layer up from all of the QP solver, we're simultaneously building onto a nice penalty SQP method–which itself has many options and tweakable parameters.
A layer up from that, we're testing the penalty SQP method on many different nonlinear programs. They might require different settings in terms of tolerance parameters(standard tolerance might be difficult to reach in a given problem, for example.)
A layer up from that, we're also testing the penalty SQP method on mixed integer nonlinear programs. This involves solving many, many NLPs.

So there's a lot of levels and layers and levers and settings. What was happening is that I would change some parameter and eventually it'd get checked into the repository, and that wouldn't play nice with other codes.

I realized that I wanted some unit testing to automate this testing process, and document how it should be run, and soforth. But I also wanted the video game-style insta-rewards vibe to it, along the lines of the Panic Status Board(albeit less professional.) I also didn't want to spend a ton of time on it. I planned out the interface and databases over some beers with my roommate one night and wrote the entire thing in Django the next evening. I wanted it to run automatically on every repository commit. I also wanted it to try to make some sense out of Python, MATLAB, and C, since I use all three extensively. It should also actually be able to build a project from scratch, and every build should run from nothing–this enforces the rule that the repository is self as self-contained as possible. Finally, I also wanted to be able to look back at the actual run log of that unit test and see how or why it failed(and also have instructions on which repo/commit to checkout to see the bug in action).

My basic idea was that I wanted some program that kept a database of projects I'm working on, displayed some commits from those projects, showed the status of any test_*.{exe,mat,py} commands it could run. Okay, so I need a table of projects, one of commits, and another of tests. Originally I built it that way, but I wasn't sure how to get columns uniformly figured out. So I decided to split the 'test’ table into 'Tests’ and 'TestResults’, which worked out nicely.

The other tricky part was figuring out how I should add commits to the database, and how tests should get run. I ended up writing a fairly nice script for the commits to put in .githookspost-commit, though it requires the kludgy 'git push origin master’ in the post-commit as well. This is causing a bit of trouble with modifying commits(ie, it breaks the other script and causes extra merges/commits.) The not-so-interesting side was the one that peeks into the database, grabs the 'test’ (which is basically just a shell-script to run), and runs it. It also pushes the data back to the database when it's done.

Django is a really amazing framework. The entire coding part of the project went together in about 8 hours. I'm still not happy with it. I've got a laundry list of stuff to add here:

check for executable test_. (this is basically done, along with subdirectory test checking)
it'd be nice to move the actual unit testing to a server instead of my laptop. But maybe it's safer to not have the interface EVER web-pointing.
Big one: time/datestamp in the commit rows, to tell when you did it.
button to undisplay old commits, or a limit of how many commits show on the main page. This could get out of hand REALLY fast.
collapse commit sha1 (did this, should add: re-expand commit sha1's)
button to rerun tests(did this).

If you're interested, check it out at code.traviscj.com's tjtestharness.