Anonymous user
Talk:Polynomial synthetic division: Difference between revisions
→Dup?
(→Dup?) |
(→Dup?) |
||
Line 14:
::: I am the author of the first draft with Python code. I do not agree this is a dup: the computational complexity is totally different between the two (O(n*m) here while the other is recursive until you go down to the quotient, thus roughly O(n*m*q) where n and m are the length of both polynomials and q the recursion depth), and the approach is quite different (we only work on the coefficients instead of accounting for the degrees in a recursive fashion). This can be seen as an extension of the Horner's scheme (which is commonly used to evaluate polynomials). What may confuse you is that on the page for Polynomial long division, some snippets are actually implementing synthetic division instead of polynomial long division, so I guess it would be more logical to move these snippets here instead of the other way around. To my knowledge, synthetic division is the fastest algorithm ever to divide polynomials, I think this reason alone is sufficient to promote a page dedicated to it. --[[User:Lrq3000|Lrq3000]] ([[User talk:Lrq3000|talk]]) 06:38, 14 June 2015 (UTC)
::: About the ordering of coefficients, I have added a note about that. Indeed, I reused the exact same example input from the Polynomial long division page, but reversing the order. I think this ordering is a better fit to easily implement Synthetic Division. The loops could be reversed inside the function but I guess this would just make things more confusing, but that's possible if you really want to follow the same convention. --[[User:Lrq3000|Lrq3000]] ([[User talk:Lrq3000|talk]]) 06:49, 14 June 2015 (UTC)
| |||