多项式进位问题
在一片CRC算法的文章中,谈到了一多项式进位
http://www.csm.ornl.gov/~dunigan/crc.html
比如 1101 * 1011(都是二进制)
(x^3 + x^2 + x^0)(x^3 + x^1 + x^0)
= (x^6 + x^4 + x^3
+ x^5 + x^3 + x^2
+ x^3 + x^1 + x^0) = x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0
At this point, to get the right answer, we have to pretend that x is 2
and propagate binary carries from the 3*x^3 yielding
x^7 + x^3 + x^2 + x^1 + x^0
为什么3*x^3 会导致 x^5 + x^4 都为0了
[解决办法]
因为3*x^3这个系数3太大了，在2进制下就会产生进位，如果进制很大，就OK了。
[解决办法]
读下去
The point is that IF we pretend that we DON'T know what x is, we CAN'T
perform the carries. We don't know that 3*x^3 is the same as x^4 + x^3
because we don't know that x is 2. In this true polynomial arithmetic
the relationship between all the coefficients is unknown and so the
coefficients of each power effectively become strongly typed;
coefficients of x^2 are effectively of a different type to
coefficients of x^3.
他的目的就是解释，在多项式算术中，是不可以做3*x^3导致x^5 + x^4这种事的。如果已经懂为什么的话完全可以跳过这段。
