точность вычисления полинома, соотношение умножения и деления

Question

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

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

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

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

Спасибо

Answer 1

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

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

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

Answer 2

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

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

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

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

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

Answer 3

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

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

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

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

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

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

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

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

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

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