Как на компьютере вычисляются корни и др мат. функции?

[Утундрий]

Интересно, не знал о

worm2 в сообщении #1480565 писал(а):

алгоритме "Fast inverse square root".

Зацепило:

Цитата:

Точности (менее 0,2 % в меньшую сторону и никогда — в большую)[1][2] не хватает для настоящих численных расчётов, однако вполне достаточно для трёхмерной графики.

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

[Евгений Машеров]

IvanX в сообщении #1480518 писал(а):

Как по заданной погрешности $\varepsilon$ узнать кол-во итераций? Есть какая-то формула для оценки погрешности?
У меня получилось доказать сходимость последовательности Герона только для $a>1$. Доказал, что эта последовательность ограничена снизу и не убывает. Как доказать при $0<a<1$?

С Героном-то всё просто. $q$ и $\frac a q$ это приближения "сверху" и "снизу" (или наоборот) к $\sqrt a$
То есть их разность даёт оценку погрешности. А доказать, что она монотонно убывает - несложно.

-- 24 авг 2020, 22:41 --

Ну и ещё так можно.
Пусть q - приближение к $\sqrt a$ с относительной погрешностью d.
$q=\sqrt a (1+d)$
Тогда $\frac a q=\sqrt a(1+d)^{-1}=\sqrt a (1-d+d^2-d^3+d^4+\cdots)$
И при каждой вызове духа Герона из Аида погрешность магическим образом становится порядка $\frac {d^2} 2$

[vpb]

IvanX

IvanX в сообщении #1480468 писал(а):

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

А какие Вы учебники читали, можно узнать ?

Есть такая книжка. Сам не читал, т.к. оно вне моих интересов лежит, но рискну рекомендовать:
J.M.Muller, Elementary functions. Algorithms and implementation.
(Вроде, пользуется авторитетом. Точнее говоря, в заведомо хороших книжках об этой хорошо отзываются.)

[photon]

На практике одновременно достаточно быстрым и точным может быть такой подход: вычисляем обратный корень методом fast inverse square root, делаем к нему 2-3 уточняющие итерации. Если корень нужен в числителе, делим единицу на полученный обратный корень.
Примерно так:

Используется синтаксис C

float rsqrt(float d0)
{
    union
    {
        float f;
        int i;
    } d1;

    d1.f = d0;
    d1.i = 0x5F3759DF - (d1.i >> 1);
    d0 *= -0.5f;

    //1'st iteration
    float a = d0;
    a *= d1.f;
    a *= d1.f;
    a += 1.5f;
    d1.f *= a;

    //2'nd iteration
    a = d0;
    a *= d1.f;
    a *= d1.f;
    a += 1.5f;
    d1.f *= a;

    return d1.f;
}

[venco]

photon в сообщении #1480711 писал(а):

делим единицу на полученный обратный корень

Или умножаем исходное число на обратный корень - обычно умножение быстрее.

[photon]

venco в сообщении #1480748 писал(а):

Или умножаем исходное число на обратный корень - обычно умножение быстрее.

нет.

photon в сообщении #1480711 писал(а):

Если корень нужен в числителе

а у нас есть только обратный корень, то придется делить. Но в общем случае, конечно, если есть позможность заменить деление чисел с плавающей точкой умножением, то, с точки зрения скорости, это будет эффективнее.

[venco]

photon в сообщении #1480755 писал(а):

venco в сообщении #1480748 писал(а):

Или умножаем исходное число на обратный корень - обычно умножение быстрее.

нет.

photon в сообщении #1480711 писал(а):

Если корень нужен в числителе

а у нас есть только обратный корень, то придется делить. Но в общем случае, конечно, если есть позможность заменить деление чисел с плавающей точкой умножением, то, с точки зрения скорости, это будет эффективнее.

Вам не кажется, что вы сами себе противоречите?

[Утундрий]

venco
Складывается впечатление, что чтение постов занимает меньше Вашего времени, чем написание ответа.

[photon]

venco в сообщении #1480850 писал(а):

Вам не кажется, что вы сами себе противоречите?

Нет, не кажется. Я привел код для быстрого вычисления обратного корня $\dfrac{1}{\sqrt{x}}$. Корень - в знаменателе. Если нам нужно, чтобы корень был в числителе, то должны единицу поделить на полученный результат. Это первое утверждение, а второе, что в общем случае, если мы можем заменить деление умножением, то выиграем в скорости. Например, надо вычислить $x_1/a, x_2/a, x_3/a, \dots x_n/a$, то эффективнее будет вычислить $b = 1 / a$ и заменить деление умножением как $bx_1, bx_2, bx_3,\dots bx_n$.

[Sender]

По-моему, venco просто-напросто пытается сказать, что $\sqrt{a}=\frac{1}{\sqrt{a}}\cdot a$.

[photon]

Sender в сообщении #1480855 писал(а):

По-моему, venco просто-напросто пытается сказать, что $\sqrt{a}=\frac{1}{\sqrt{a}}\cdot a$.

А-а, ну если так, то да, просто не понял. Да, пожалуй, так будет лучше.

[venco]

Sender в сообщении #1480855 писал(а):

По-моему, venco просто-напросто пытается сказать, что $\sqrt{a}=\frac{1}{\sqrt{a}}\cdot a$.

Именно. Я же вроде сказал, что умножать надо на исходное число. Так действительно получается быстрее по крайней мере на моём i7-6700K.

[photon]

Да, я недопонял. Конечно, так будет быстрее.

[Утундрий]

Забавно, я был уверен, что venco спорол чушь и упорствует в этом. Все прояснилось только после

Sender в сообщении #1480855 писал(а):

По-моему, venco просто-напросто пытается сказать, что $\sqrt{a}=\frac{1}{\sqrt{a}}\cdot a$.

Не знаю, что помешало самому venco выразиться столь же определённо.

[venco]

venco в сообщении #1480748 писал(а):

photon в сообщении #1480711 писал(а):

делим единицу на полученный обратный корень

Или умножаем исходное число на обратный корень - обычно умножение быстрее.

Я думал, что здесь всё понятно было и без формул. А дальше, конечно, приключилась излишняя эскалация после короткого "нет".
В общем, я рад, что мы в конце пришли к согласию.