точность полиномиальной оценки, умножение и деление

Question

допустим, у меня есть многочлен от x, деленный на степень x:

p = (a + x(b + x(c + ..)))/(x**n)

эффективность в стороне, что было бы более точным численным расчетом, выше или с использованием деления:

p = (((a/x + b)/x + c)/x + ...)

спасибо

Answer 1

Теоретически не должно быть никакой разницы - если значения рассчитываются точно с «бесконечной» точностью.

Керниган и Плаугер в своей старинной, но превосходной книге « Элементы стиля программирования » утверждают, что:

Один мудрый программист однажды сказал: «Числа с плавающей точкой похожи на маленькие груды песка; каждый раз, когда вы перемещаете одну, вы теряете немного песка и получаете немного грязи».

В целом у подразделения немного меньше операций, что означает, что у него немного меньше возможностей терять песок и добывать грязь.

Детальный анализ, вероятно, потребует рассмотрения коэффициентов (a, b, c и т. Д.), А также, возможно, значения x - то, что работает при огромных значениях x, может не сработать, когда x близко к нулю, или наоборот.

Answer 2

Я думаю, что разница минимальна, если только не существует вероятность, что x**n переполнится или опустится, в этом случае вам следует использовать второе выражение.

Два выражения отличаются в двух местах:

1. Порядок вычисления обратный (..., c, b, a) для первого выражения и (a, b, c, ...) для второго выражения. Какой из них лучше, зависит от значения коэффициентов.
2. Первое выражение имеет .../x**n в конце. Как объясняет Джонатан, по этой причине можно ожидать, что второе выражение будет более точным, поскольку в нем меньше операций. Однако я думаю, что .../x**n вызывает лишь минимальную потерю точности (по сравнению с другими местами, где вы теряете точность), если только x**n не переполнен или не переполнен.

Answer 3

Ответы, к сожалению, неверны.

Второе уравнение p = ((((a / x + b) / x + c) / x + ...) лишь незначительно хуже для точности и намного, намного хуже для скорости.

Почему? Относительная погрешность умножения имеет только основной линейный член и маленький квадратичный член. Деление по контрасту вводит выше, но очень маленькие термины (кубический, квартичный):

e = относительная ошибка, предполагаемая постоянная для обоих членов

a * b = a (1 + e) ​​ b (1 + e) ​​= a b (1 + 2e + e ^ 2) // умножение

a / b = a (1 + e) ​​/ b (1 + e) ​​= a / b (1 + e) ​​(1 + e + e ^ 2 + e ^ 3 + ... геометрический ряд) // раздел

Таким образом, деление всегда немного хуже, чем умножение. Из соображений скорости: деления всегда медленнее, чем умножения, нормальный коэффициент может варьироваться от 3х до 10х. Так что вложенных подразделений много медленнее, чем вложенные умножения, если вы не вычислили последний фактор x ^ n не pow (), а вложенным умножением.

x ^ n можно легко вычислить с помощью цикла, умножающего результат двойная сила = х; для (n-1) мощность * = х;

Если вы используете pow (), помните, что в большинстве случаев его удобно вычислять экспоненциальный и логарифм, занимающий гораздо больше времени, чем необходимо (100x).

Знаете ли вы, что, хотя ошибка между двойным и точным результатом остается небольшой, полиноминальные результаты очень чувствительны к изменениям x для более высоких n?! Поэтому, если вы используете более высокие n, знайте, что ваши ответы могут быть совершенно неверными потому что небольшие ошибки в x усиливаются астрономически.