C++ polynomial best-fit-curve finder

As part of my ongoing VCV Rack module development efforts, I had reason to take a trip down the rabbit hole of finding the polynomial curve that passes through any given collection of points (x_j, y_j). Based on reading stuff about sinc-interpolation, and the theory behind it, I ran into a nifty way of solving this problem as a side-effect.

I created a C++ class template for efficiently finding a polynomial

f(x) = \sum_{j=0}^{n-1} K_j x^j

For any arbitrary list of n points (x_j, y_j). It exists as a pair of template classes Interpolator and Polynomial. They allow real-valued x and real- or complex-valued y.

Here it is, if anyone is interested. It is MIT-licensed, so have fun! Even if you aren’t interested in the C++ code, you might find it fun to read the outline of the math ideas there on the repo’s front page.


So could be used for resampling

Maybe? I needed a quadratic interpolation to help speed up evaluation of a sinc function multiplied by a Blackman window, as part of a resampler for a module I’m currently working on. It uses a window of 11 samples centered on the nearest integer sample, and I interpolate a sample at a nearby non-integer sample.

So I don’t use the interpolator directly for resampling, but as an optimization step for a more traditional approach.

Maybe directly using this on the audio data could work in theory (I’m not sure). But the major problem would be efficiency. There is significant overhead coming up with a new polynomial every time you need a new sample.

The intention of this code is to create a polynomial once, then re-use it many times. That would be the efficient use case.

For an offline renderer it’s not a problem

Maybe could be implemented on GPU?

Yeah, it would be pretty cool to see what happens if you feed it a few thousand points and use it to resample them at a different rate (or even a variable rate). The polynomial generator is O(n^2) so that could take quite a while to find the polynomial for that many points! But I’d love to see what happens if someone tries this.

could be a new sound generator technology

Maybe a sharp sound and soft sound a the same time…Granular resampling

But a faster way would be to use filter on chunk

as @cosinekitty mentioned already, optimal re-sampling is quite well understood (sinc filter). The world isn’t really crying out for something new there. Meanwhile in VCV is was big step forward to get people to stop using drop/repeat sample for rate conversions.

1 Like