| 词条 | Kronecker substitution |
| 释义 |
Kronecker substitution is a technique named after Leopold Kronecker for determining the coefficients of an unknown polynomial by evaluating it at a single value. If p(x) is a polynomial with integer coefficients, and x is chosen to be both a power of two and larger in magnitude than any of the coefficients of p, then the coefficients of each term of can be read directly out of the binary representation of p(x). One application of this method is to reduce the computational problem of multiplying polynomials to the (potentially simpler) problem of multiplying integers. If p(x) and q(x) are polynomials with known coefficients, then one can use these coefficients to determine a value of x that is a large enough power of two for that the coefficients of the product pq(x) to be read off from the binary representation of the number p(x)q(x). Since p(x) and q(x) are themselves straightforward to determine from the coefficients of p and q, this result shows that polynomial multiplication may be performed in the time for a single binary multiplication.[1] See also
References1. ^{{citation | first1 = Joachim | last1 = von zur Gathen | author1-link = Joachim von zur Gathen | first2 = Jürgen | last2 = Gerhard | title = Modern Computer Algebra | publisher = Cambridge University Press | year = 1999 | isbn = 978-0-521-64176-0 | pages = 243–244 | url = https://books.google.com/books?id=AE5PN5QGgvUC&pg=PA245 }}. {{algebra-stub}} 1 : Computer algebra |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。