title: Canonical coefficients from Newton polynomial
body: <p>A while ago I implemented a Polynom approximation for a game I programmed.</p>
  
  <p>I am using Newton's pyramide method.
  It took me quite a while to figure it out, but my solution requires to calculate the binomial coefficients and I also have to sum up all the coefficients for the final coefficient of each power (since solving this problem is similar to squaring, cubing.. terms and calculating the binomial coefficients)</p>
  
  <p>For example:
  pick k out of n of the bionomeal terms and add them<br>
   one pick is multiplied<br>
   a*(x+b)<em>(x+c)</em>(x+d) ==> a*x^3 + a*x^2*(b+c+d) + a*x(bc+bd+cd) +a*b*c*d<br>
   so b*c*d would be one pick b*c and b*d too</p>
  
  <p>My question now is:
  Is there a way calculating the Polynominterpolation with the newton scheme without having to calculate all the bionomial coefficients?</p>
  
  <p>My code:
  <a href="https://github.com/superphil0/Polynominterpolation/blob/master/PolynomInterpolation.java" rel="nofollow">https://github.com/superphil0/Polynominterpolation/blob/master/PolynomInterpolation.java</a></p>
  
  <p>It works pretty good, although if one gives too many points it will be rather slow
  because of the selection of terms which have all be summed up</p>
  
  <p>(I am really bad at explaining this in english, I hope someone can understand what I want to know though)</p>
  
  <p>cheers</p>