Operations on polynomials (on cp-algorithms)

Revision en1, by adamant, 2019-03-10 17:50:13

Hi there!

During preparation of Oleksandr Kulkov Contest 1 I started writing some template for polynomial algebra (because 3 problems in contest in one or another way required some polynomial operations). And with great pleasure I'd like to report that it resulted in this article on cp-algorithms.com (English translation for e-maxx) and this mini-library containing all mentioned operations and algorithms (except for Half-GCD algorithm). I won't say the code is super-optimized, but at least it's public, provides some baseline and is open for contribution if anyone would like to enhance it!

Article also provides some algorithms I didn't mention before. Namely:

  • Interpolation: Now the described algorithm is and not as it was before.
  • Resultant: Given polynomials A(x) and B(x) compute product of Ai) across all μi being roots of B(x).
  • Half-GCD: How to compute GCD and resultants in (just key ideas).

Feel free to read the article to know more and/or use provided code :)


  Rev. Lang. By When Δ Comment
en2 English adamant 2019-03-10 17:51:29 225
en1 English adamant 2019-03-10 17:50:13 1311 Initial revision (published)