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

[IvanX]

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

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

Здесь кое-что можно найти
http://libarch.nmu.org.ua/handle/Genofo ... tribute=ru
http://www.toroid.ru/ivanovVV.html
Но вообще при выборе метода надо учитывать архитектуру конкретной ЭВМ.

[=SSN=]

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

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

CORDIC

[IvanX]

В приведенных книгах много методов, без примеров, не понятно, что именно выбрать
Попробую уточнить вопрос. Хочу написать программку на C++, которая вычисляет квадратный корень данного числа $x$ с заданной точностью $\varepsilon$. Какой именно алгоритм использовать?

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

Если просто действительные числа - алгоритм Герона. Для каких-то других числовых систем, а также для очень больших целых - надо что-то иное, но что? Надо уточнить, что считаем.

[IvanX]

Евгений Машеров в сообщении #1480516 писал(а):

Если просто действительные числа - алгоритм Герона.

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

Евгений Машеров в сообщении #1480516 писал(а):

Надо уточнить, что считаем.

Для чисел double. Пусть я хочу написать свою функцию sqrt для C++. И желательно осмысленно, оптимально, с минимальным числом итераций по заданной погрешности.

[nds]

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

Как на компьютере вычисляются корни

Например, так это делается на ассемблере: http://ww1.microchip.com/downloads/en/AppNotes/00544d.pdf

[Sender]

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

Как по заданной погрешности $\varepsilon$ узнать кол-во итераций? Есть какая-то формула для оценки погрешности?

Этими вопросами занимается вычислительная математика. Берите учебник и изучайте. В частности, итерационная формула Герона для нахождения квадратного корня - это не что иное, как применение метода Ньютона к уравнению $x^2-a=0$, а сходимость метода Ньютона давно исследована и описана.

[wrest]

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

Как на компьютере вычисляются корни,

Вот так: http://cs.uccs.edu/~cs591/bufferOverflo ... 4/e_sqrt.c

[Andrey A]

Евгений Машеров в сообщении #1480516 писал(а):

... а также для очень больших целых - надо что-то иное

Важно еще в какой форме должен быть выражен результат. В простых дробях квадратный радикал из натурального $m$ может вычисляться так: $\dfrac{p_{n+1}}{q_{n+1}}=\dfrac{2p_n^2-1}{2p_nq_n}$, где $\dfrac{p_1}{q_1}$ — первое (или некоторое) решение ур. Пелля. Быстрее вряд ли что найдется. Пример: $\sqrt{2}=\dfrac{3}{2},\dfrac{17}{12},\dfrac{577}{408},\dfrac{665857}{470832},...$ уже $12$ дес. знаков.

[iifat]

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

Какой именно алгоритм использовать?

Как вы думаете, писали бы толстенные книжки по вычислительным методам, если б существовал Самый Наилучший Алгоритм?

Andrey A в сообщении #1480529 писал(а):

В простых дробях

Чем ещё хорош подобный метод — очень просто вычисляется погрешность. Поскольку имеет место быть сходящийся ряд побольше-поменьше. А напоследок можно не постесняться да разделить, дабы получить десятичную дробь.

[Andrey A]

iifat в сообщении #1480544 писал(а):

... не постесняться да разделить

Можно. Если разовые затраты, к которым нужно отнести и решение Пелля, не сопоставимы с общими — прямой смысл. С рациональным $m$ это работает не хуже, тот же период, а вот для радикалов степени $>2$ периода нет. Но если нужна именно простая дробь, есть другие способы помучиться.

[worm2]

Забавную вещь обнаружил: если число, не меньшее 1, записанное в стандартном формате IEEE-754 одинарной или двойной точности, побитово сдвинуть вправо, то получится неплохое начальное приближение для квадратного корня из этого числа.
Интересно, это так задумано, или случайно получилось?
UPD: К сожалению, не работает, см. коммент ниже.

[Утундрий]

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

Интересно, это так задумано, или случайно получилось?

Случайно ли получилось, что $x/2$ - хорошее начальное приближение для $\sqrt x $? Наверное, это больше зависит не от стандарта, а от алгоритма.

[worm2]

Там не $x/2$ получается, а $\sqrt{1+x} \approx 1+x/2$ при $x < 1$, т.е. прямо по Тэйлору.

P.S. А нет, дьявол, не получается! Экспонента-то в этом формате сдвинута на 127 (для Single, для Double — на 1023), так что так просто не сработает. А так красиво было! экспонента тоже на два бы делилась, а нечётная давала бы подходящую прибавку в мантиссу

-- Пн авг 24, 2020 21:17:40 --

Видимо, похожий хак применяется в алгоритме "Fast inverse square root".