News for hackers. Stuff that matters.
Re:From Roots to Polynomials by nullc on Wednesday August 10, 2022 @09:32PM (#32420587)
Pieter Wuille pointed out to me that you can:

  def coeffs_from_roots(roots):
    coefs=[1]
    for r in roots:
      coefs=[-r*coefs[0]] + [coefs[i]-r*coefs[i+1] for i in range(len(coefs)-1)] + [1]
    coefs.reverse()
    return coefs
That's merely quadratic, rather than taking exponentially many multiplications.

There are no comments on this comment yet.