A surprising amount of math and physics goes into building a tuner, particularly a tuner that can adapt to a variety of circumstances - as banjoist Holland Hopson once said, "computers are bad at listening." However, using a bit of cleverness, we can get pretty close to that holy grail of accurate pitch detection.
The Pocket Orchestra tuner uses a time-domain approach to determining the fundamental frequency of the signals it receives. To break down that statement a bit - fundamental frequency is, for our purposes, the true pitch of the note being played. A time-domain approach simply means that Pocket Orchestra determines the fundamental frequency of the note being played by analyzing how the sound wave looks different over time. This is accomplished through a technique called autocorrelation.
Autocorrelation is a measure of how well a graph matches up with itself at different points in time. Take a sine wave for example - sine waves are periodic with the interval 2π. At time 0, the sine wave will match up perfectly with itself. At time 0.01 the sine wave will still match up pretty well with itself, but not as well as at time 0. At time π, the sine wave will be perfectly out of phase with itself - this is the worst match. At time 2π, the sine wave will match up with itself perfectly again! Autocorrelation gives a number to each of these points and plots them on a new graph - higher numbers correspond with a better match. If we imagine the sine autocorrelation graph, it will have maxima at multiples of 2π and minima at multiples of π that are not also multiples of 2π. This idea holds true for any periodic function - this graph is the autocorrelation of the sound data from my whistle:
Now the function that models my whistle is not as simple as a sine wave; however, it is still periodic. Each of those maxima represent when my whistle matches up really well with itself, and each of the minima represent when it is perfectly out of phase with itself. That first peak tells us what the period of our signal is, and period is directly related to frequency!
Every quarter of a second, Pocket Orchestra takes exactly 32,768 (2^15) samples of sound data from the microphone. Using the Weiner-Khinchin theorem, the discrete autocorrelation of the samples is calculated. Then the derivative of the autocorrelation is calculated and the x-coordinate of the first relative maxima is assumed to be the period of the function (only a few conversions to get it to frequency). However, since the data is discrete and not continuous, the relative maxima of the data collected is almost certainly not the actual relative maxima of the autocorrelation of my continuous whistle - there simply isn't enough accuracy. Pocket Orchestra takes advantage of the fact that near the relative maxima the autocorrelation function approximates a parabola. Using the calculated relative maxima and the points on either side, a parabola is calculated and its vertex is assumed to be the true relative maxima and thus the true period of the function.
At low frequencies, periods are quite large and this additional level of pitch approximation is not significant. However, at high pitches this quadratic interpolation technique can be the difference between an error of 100 Hz and an error of 1 Hz.
Other techniques exist for finding the fundamental frequency of a signal - frequency domain approaches take advantage of the Fourier transform, for example. Autocorrelation remains one of the best ways to write an efficient tuner for everyday use, though, and it is my preferred method.