Well, I once tried to make a liner time function to derive the formula using an Nth degree polynomial. At the time is was just an exercise, so I gave up after the math became too much of a bitch. (I think I could do it.)
??? For N sample points you get Nth degree polynomial by creating NxN matrix and then you find the coefficients with Gauss-Jordan Elimination. I already have some C code for that lying around. That interpolation passes exactly through the reference points, but is a little curvy in between because it
requires that between each two references there exists a critical point; that's why people prefer Chebyshef or Lagrange polynomials.
This would in theory yield the best possible interpolation, if one assumes that the cache distribution follows a polynomial curve. (and you could just add new data points to the set and change your weights without recalculating the whole thing.)
You mean N-splines.
Although I'm not sure it would lead to any real benefit, as if we cached biased any consistant formula, say a quadratic (fixed time) function biased on the data we currently have in our store, then using that same formula might work just as well. I proposed this a while back under the name Node Stereotyping, and I assume something similar will be done with NGrouting. However if it would produce more accurate results, with an N-degree polynomial, and be worth while I could hash out some pseudo code. Vote yay/nay.
Ether way, you can do quadratic with N points in fixed time and no recalculation when you add a new point. So I see no reason to stay with linear.
You're right, linear interpolation is pathetic. But its hard to determine what would the best interpolation be unless we have a lot of data that would point in either polynomial or periodic direction. I'd say its more likely to be polynomial because of specialization; and FFT is a monster no matter how much we optimize it. Anybody hip for including Fortran code in Fred? ;-))
_______________________________________________ devl mailing list [EMAIL PROTECTED] http://hawk.freenetproject.org:8080/cgi-bin/mailman/listinfo/devl
