У меня есть метод для деления многочленов с остатком. Он хорошо работает для многочленов, коэффициенты которых делятся точно. Но при попытке разделить, например 2*x^3-18*x^2+....
на 7.00000(много нулей)0000028*x^2 + 5*x + ...
возникает проблема. Первым делом делятся коэффициенты при старших членах: 2*x^3 / 7.000...000028*x^2
. Получаем 0.285714....53*x
. Дальше необходимо умножить полученное значение 0.2857....53*x
на делитель 7.00000...0000028*x^2 + 5*x + ..
и вычесть из делимого многочлена 2*x^3-18*x^2+...
. Так мы получаем остаток уже степени 2. Но из-за проблем с точностью вычисления, после вычитания я получаю не многочлен степени 2, а вот такой 2.220....E-16*x^3 - 6*x^2 + ....
. Понятно, что на самом деле возле x^3
стоит почти ноль, но из-за того, что по факту это не так, алгоритм зацикливается. Как правильно решить эту проблему, чтобы не изобретать велосипедов?
3 ответа
Вы просто старшую степень всегда вычитайте полностью! Зачем же потом опять множить?
(ax^3+bx^2+cx+d) / (ex^2+fx+g) => // первый член - ax/e
Остаток: (bx^2+cx+d - (afx^2/e+agx/e))
, дальше делите его...
При члене x^3
коэффициент по определению нулеdой!
Более-менее понятно? жутко не хочется строить все это в TeX'е...
Вы не указали никакого кода, который помог бы решить проблему, ведь она зависит от того, как именно вы сравниваете числа типа double
. Я догадываюсь, как вы это делаете, а потому предлагаю после произведённых вычислений делать следующее. Если некое число по абсолютному значению меньше чем заданная заранее точность, например, const double EPS = 1e-8
, то намеренно делаем это число равным нулю. Типа того:
if (abs(a) < EPS) a = 0.0;
Был бы код, я бы конкретно показал, где и как это сделать, но, думаю, вы уже и так поняли.
Переписать алгоритм. Он должен только один раз определять степень многочлена, а потом работать так, что на каждой итерации обрабатывается только суффикс массива. Ну и с нулём надо сравнивать с некоторой точностью, как написали в других ответах.
-
Это больше похоже на комментарий, чем на ответ. "Когда ваша репутация достигнет бла-бла-бла вы сможете оставлять комментарии". ;) Ладно, сам вопрос без кода -- так что пусть остаётся.– A K26 янв 2017 в 13:05