Как компьютер вычисляет квадратные корни?
Как компьютер вычисляет квадратные корни?
Я имею в виду, что там происходит! Как это обрабатывает это !!
Использует ли он некоторые математические методы, такие как метод Ньютона?
Как насчет тригонометрических функций? И почти все эти математические функции.
В случае, если у каждого языка свой путь, давайте поговорим о c ++.
Решение
Большинство современных не встроенных процессоров (например, x86 и более крупные ядра ARM) имеют аппаратные инструкции для прямого вычисления квадратных корней. Аппаратная реализация, поддерживающая эти инструкции, различается, но, как правило, представляет собой вариант алгоритма «цифра за цифрой» в учебнике (хотя не всегда в базе два; также могут использоваться базы четыре или шестнадцать). Как правило, это одни из самых медленных базовых арифметических операций на процессоре; такие временные интервалы, как 16-64 цикла, нередки, и эти инструкции часто не передаются по конвейеру.
В процессорах, в которых отсутствуют прямые аппаратные квадратно-корневые инструкции (Itanium, PPC и т. Д.), Типичным подходом является генерация начальной оценки (либо с помощью инструкции, которая производит оценку, либо с помощью таблицы поиска), а затем уточнение этой оценки с использованием итеративного метод (обычно Ньютон или Гольдшмидт). Вы можете отследить некоторые работы Питера Маркштейна или Роджера Голливера на эту тему, если вам интересно.
Более сложные математические функции (например, операции триггера) обычно вычисляются путем сведения аргумента в некоторую фундаментальную область и последующего приближения его полиномиальной или рациональной функцией. Вы можете посмотреть на источники любой из нескольких математических библиотек, которые доступны онлайн для более подробной информации (fdlibm — хорошая отправная точка).
Набор команд x86 предоставляет ряд инструкций, которые поддерживают математические функции, такие как exp, log и sin, но они больше не используются, потому что хорошие реализации программных библиотек дают лучшую производительность.
Другие решения
Хорошая статья об этом http://www.codeproject.com/Articles/69941/Best-Square-Root-Method-Algorithm-Function-Precisi показывая сравнение различных методов, которые используются.
Еще одна возможность, которая не была упомянута, это CORDIC метод. CORDIC не широко используется / не известен в программном обеспечении, но довольно распространен в аппаратных средствах и довольно хорошо справляется с получением достойной производительности без использования большого количества шлюзов.
Я думаю, что метод итеративной сходимости Ньютона используется при расчете квадратного корня
Как уже отмечали другие, это очень широкий вопрос — что хорошо работает для программного обеспечения, может быть плохим выбором для аппаратной реализации; а затем возникают проблемы правильного округления для IEEE-754, аппаратных таблиц поиска и т. д. Существует много библиотек C с открытым исходным кодом, с libm реализации, а также. Хороший обзор классических и современных методов можно найти Вот.