[time-nuts] Linear or quadractic fit algorithms for small microcontrollers?

[Magnus Danielson]

Hi Tim,

On 12/26/18 4:53 PM, Tim Shoppa wrote:
> I know we discussed this many years ago, probably in context of the HP
> Smartclock patent, but I've forgotten all the details.
> 
> Say I have a circular buffer of up to several dozen time and offset values.
> The intent was to sample at regular intervals but some samples are missing.
> Are there simple microcontroller-oriented algorithms - integer math, no big
> scratch arrays - for doing linear or quadractic fits and maybe even
> excluding some outliers?
> 
> Instead of using arrays for circular buffers, if there are algorithms that
> "age out" the older samples so that they get lesser and lesser weight, and
> also give linear and/or quadractic fit coefficients, that's even neater.
> For example exponential smoothing.

You could either do linear regression or the type of least square
fitting that I did, which did away with the large matrixes altogether.

Here is one variant of the article:
https://arxiv.org/abs/1604.01004

The benefit is that you only need to build the sums C and D, and using
knowledge about how many N samples, you can do both phase and frequency
estimation from the same values. This should work very well in a small
microcontroller.

What is not covered in the above article is linear drift, but it can be
approximated using two frequency readings. I've developed an extension
for linear drift, it's just not published yet.

The HP SmartClock used least-square estimation, but as far as I have
been able to reverse-engineer, it was not very fancy but more classical
matrix stuff.

Cheers,
Magnus