Полином точность оценки, умножение против деление

Question

скажем у меня есть многочлен х, делится на степени х:

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

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

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

благодаря

Answer 1

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

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

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

Answer 2

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

Керниган и Plauger состояние в их античном, но отличной книге «Elements of Programming Style», что:

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

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

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

Answer 3

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

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

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

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

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

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

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

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

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

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