Хорошо. Тогда помогите осознать такую фразу, взятую из перевода одной очень известной книги:
«Если A(x) и B(x) - полиномы степени не выше n, их произведением (product) С(х) является полином степени не выше 2n - 1, такой что C(x) = A(x)B(x) для всех x из соответствующего поля.»
«Не выше n», значит самая большая степень есть n, и тогда утверждение «не выше 2n - 1» ложно.
встречал в некоторых книгах, что степень по числу коэффициентов определяют, тогда наивысшая степень при n коэффициентах будет n-1. хотя, скорее всего, слово «степень» тут уже неуместно
Да, ссылка хорошая. Но у меня перевод 2-го издания, а ссылка на errata на странице 2-го издания отправляет на 3-е издание, а там 30-й главы вообще нет в «проблемном» списке.
Просмотрщик amazon.com очень аккуратно отключает возможность просмотра результатов поиска с определением, содержание - пожалуйста, индекс - извольте, но не текст главы...
«Заметим, что degree(C) = degree(A) + degree(B), откуда вытекает, что если A - полином степени не выше Na, а В - полином степени не выше Nb, то С - полином степени не выше Na + Nb - 1. Тем не менее, поскольку полином степени не выше k является также полиномом степени не выше k + 1, мы будем говорить, что произведение С является полиномом степени не выше Na + Nb.»
Здесь неправильный перевод. В оригинале предложение звучит по-другому:
For polynomial multiplication, if A(x) and B(x) are polynomials of degree-bound n, we say that their product C(x) is a polynomial of degree-bound 2n — 1 such that C(x) = A(x)B(x) for all x in the underlying field.
Any integer strictly greater than the degree of a polynomial is a degree-bound of that polynomial. Therefore, the degree of a polynomial of degree-bound n may be any integer between 0 and n — 1, inclusive.
Похоже, они действительно степень полинома определяют как-то по-своему :) Как уже говорили выше, если считать с нуля, т.е. «наш» полином степени N обзывать «их» полиномом степени M=N+1, то «наш» полином степени 2N превратится в «их» полином степени 2N+1, т.е. 2M-1.
Ёжкин кот! ведь до этого в переводе приводился термин «граница степени» (degree-bound), но потом слово «граница» куда-то исчезло. И как, спрашивается, после этого покупать переведённые книги? Кот в мешке получается...
А кто сказал, что степени полиномов должны совпадать? Не выше n - значит pow(A(x)) <= n && pow(B(x)) <= n. Тогда если, скажем pow(A(x)) = n -1, а pow(B(x)) = n, то pow(C(x) = A(x)*B(x)) = pow(A(x)) + pow(B(x)) = 2n - 1.