Как компьютер вычисляет корень
Обновлено: 21.11.2024
Какой алгоритм используется компьютерами для вычисления квадратного корня числа?
Но ответы, представленные здесь, мне нравятся больше. К тому же у человека, задавшего аналогичный вопрос, вопрос был сформулирован по-своему.
У моего вопроса более простая формулировка. Аналогичного спрашивали, имея представление о внутренней механике такого алгоритма, и спрашивали, будто это что-то, что еще не решено-найдено.
Я не знаю, есть ли у модератора способ объединить два сообщения.
$\begingroup$ @Pseudonym Что ж, некоторые вычисления считаются само собой разумеющимися, например преобразование числа с плавающей запятой в форму 'm×2^e' и предварительно вычисленный 'sqr(2)' . даже предварительно вычисленный 'sqr(2)' имеет ограниченное количество десятичных знаков. Я искал алгоритм, который мог бы вычислить произвольное количество десятичных знаков. $\endgroup$
6 ответов 6
Посмотрите на статью
в котором описывается аппаратная реализация деления/квадратичного корня в некоторых процессорах ARM.
Примерно идея: для единицы деления вы можете найти начальные биты делителя и делимого в таблице, чтобы получить два бита результата. Для двойной точности с 53-битной мантиссой вы повторяете это 26 или 27 раз и получаете результат. Для одинарной точности с 24-битной мантиссой вам нужно повторить только 12 или 13 раз. Все остальные биты, вычисление показателя степени и т. д., могут выполняться параллельно.
Какое отношение квадратный корень имеет к делению? Просто: sqrt (x) = x / sqrt (x). Вы получаете квадратный корень, разделив x на его квадратный корень. Теперь, когда вы начинаете это деление, вы еще не знаете квадратный корень. Но как только у вас будет, скажем, восемь битов, и вы будете очень, очень осторожны, вы сможете производить два бита мантиссы за цикл. И получить первые, скажем, восемь битов несложно, так как в отличие от деления x/y здесь задействован только один операнд.
В документе это описывается гораздо более подробно и, что важно, объясняется, почему это лучше, например, по сравнению с использованием Ньютона-Рафсона или аналогичного метода. Примечание. Это лучше для типичных чисел с плавающей запятой с 24- или 53-битной мантиссой. Поскольку это то, что используется в 99,9999% случаев, это важно, но в разных ситуациях все по-разному.
Ну, это своего рода вопрос о численном методе, и он не связан с алгоритмом аппроксимации. В любом случае, я думаю, вы можете поискать метод деления пополам, метод Ньютона (или метод Ньютона-Рафазона), конечно, есть и другие способы, но это то, что я помню из курса численных методов.
Проверьте этот учебник:
Стивен С. Чапра и Раймонд П. Канале. Численные методы. 7-е издание. McGraw Hill Education.
$\begingroup$ Я поместил в теги "алгоритм аппроксимации" по двум причинам. 1) Я не знал, что еще может иметь значение. 2) вы никогда не сможете вывести фактический квадратный корень из 2. Разве это не определение приближения? Разве численные методы не часто являются приближениями? Добавлю числовой тег, потому что это хорошая идея. $\endgroup$
$\begingroup$ Да, я не проверял, есть ли тег численных методов, но я думаю, что его следует добавить. Да, полностью согласен с тем, что корень квадратный из 2 не имеет точного значения (и многих других чисел), но эти алгоритмы, насколько я знаю, мы не называем их алгоритмами аппроксимации. Последнее относится к задачам оптимизации, которые обладают некоторыми свойствами, отличными от «алгоритмов, находящих квадратный корень из числа». $\endgroup$
Если вы не являетесь разработчиком аппаратного обеспечения, вы, вероятно, используете метод итераций Ньютона. Учитывая уравнение f(x) = 0 и приближенное решение $x_0$ , итерация Ньютона вычисляет (надеюсь) лучшее приближение как $x_ = x_n - f(x_n) / f'(x_n)$ . Если мы заменим $x = a^$ на $x^2 = a$ на $x^2 - a = 0$ , то получим простую формулу $x_$ = $x_n - (^2 - a) / 2x_n$ = $(x_n + a/x_n)/2$ .
Это хорошо работает с хорошим начальным приближением, но каждый раунд итерации включает в себя деление, а деление очень медленное. Поэтому мы используем другую формулу: вместо решения $x = a^$ мы решаем $x = a^$ и умножаем результат на a, что дает требуемое значение $a^$.
Переставляем $x = a^$ как $x^2 = 1/a$ , тогда $1/x^2 = a$ и $1/x^2 - a = 0$ . Теперь $f'(x) = -2/x^3$ , поэтому итерация Ньютона дает $x_n - (1/^2 - a) / (-2/^3)$ или $x_n + (x_n - a^ 3) / 2)$ или $1.5x_n - (a/2)^3))$ . Это можно вычислить, используя только умножение, что намного быстрее, чем деление. На современном процессоре, который может вычислять умножение параллельно и имеет объединенную операцию умножения-сложения, вы вычисляете $r = 1,5x_n$ , $s = (a/2)x_n$ , $t = ^2$ , затем $x_ = г + с \cdot t$ .
Для поддержки этого процессоры x86, например, имеют очень быструю аппаратную инструкцию, вычисляющую приближение к $a^$ с относительной ошибкой менее 1/1024, реализованную с использованием таблицы.
Вы получите совершенно другой ответ, если запросите квадратные корни из n-битных чисел с плавающей запятой для БОЛЬШИХ n, скажем, n ≥ 1000 или n ≥ 1 000 000.
Для больших n мы обычно определяем время, необходимое для умножения двух n-битных чисел, как M(n). Это время зависит от того, насколько умен наш алгоритм; то, что мы узнали в школе, имеет M (n) = O (n ^ 2), алгоритм Карацубы имеет M (n) ≈ O (n ^ 1,58), а алгоритмы на основе БПФ работают за O (n log n). Деление с точностью n бит может быть выполнено за ненамного большее время, около 2 M(n).
Мы можем использовать метод Ньютона-Рафсона, повторяя $x_$ = $x_k - (^2 - a) / 2x_k$ . Однако мы вносим одно важное изменение: если нам нужен результат, скажем, с точностью в 1 000 000 бит, мы не выполняем весь расчет с такой точностью. Мы вычисляем одно приближение с достаточной точностью, чтобы последний шаг итерации дал требуемую точность. Например, мы можем вычислить предпоследнее значение с точностью 500 005 или 500 010 бит, а затем выполнить последнюю итерацию с полной точностью. Но вычисляя $^2$ , мы знаем, что первые 500 000 битов результата должны быть идентичны a, поэтому мы можем сэкономить много времени, не вычисляя эти 500 000 бит, когда мы уже знаем, что они из себя представляют. И нам не нужно вычислять $(^2 - a) / 2x_k$ с точностью до 1 000 000 бит, потому что результатом является лишь крошечная поправка к $x_k$, поэтому точности около 500 000 бит достаточно. (Очевидно, что вам нужно очень тщательно анализировать границы ошибок).
При расчете предпоследнего приближения вам также не требуется точность 500 010 бит на протяжении всего расчета; достаточно вычислить третье-последнее приближение, скажем, с точностью 250 015 бит и так далее. Таким образом, общее время равно O(M(n)) + O(M(n/2)) + O(M(n/4)) + . Стоимость последнего шага преобладает над остальными, пока M(n) ≥ O(n), поэтому квадратный корень с точностью n бит может быть вычислен за время c * M(n) для c, вероятно, от 6 до 10. < /p>
Если вы выполняете много таких вычислений, стоит проверить, не даст ли вычисление приближения к $a^$ более быстрых результатов.
Хотите улучшить этот вопрос? Обновите вопрос, чтобы он соответствовал теме Stack Overflow.
Закрыт 9 лет назад.
Как компьютер вычисляет квадратные корни? Я имею в виду, что там происходит! Как это обрабатывается!! Использует ли он какие-то математические методы, такие как метод Ньютона? А тригонометрические функции? И почти все эти математические функции. В случае, если у каждого языка свой путь, то давайте поговорим о c++.
4 ответа 4
Большинство современных невстроенных ЦП (например, x86 и более крупные ядра ARM) имеют аппаратные инструкции для прямого вычисления квадратных корней. Аппаратная реализация, поддерживающая эти инструкции, различается, но обычно представляет собой вариант алгоритма «цифра за цифрой» школьного учебника (хотя и не всегда по основанию два; также можно использовать основание четыре или шестнадцать). Обычно это одни из самых медленных основных арифметических операций на ЦП; такие тайминги, как 16-64 цикла, не редкость, и эти инструкции часто не конвейерны.
Для процессоров, в которых отсутствуют прямые аппаратные инструкции по извлечению квадратного корня (Itanium, PPC и другие), типичным подходом является создание начальной оценки (либо с помощью инструкции, которая производит оценку, либо с помощью таблицы поиска), а затем ее уточнение. с использованием итеративного метода (обычно Ньютона или Гольдшмидта). Если вам интересно, вы можете найти некоторые работы Питера Маркштейна или Роджера Голливера на эту тему.
Более сложные математические функции (например, тригонометрические операции) обычно вычисляются путем сведения аргумента к некоторой фундаментальной области и последующего аппроксимирования его полиномиальной или рациональной функцией. Более подробные сведения можно найти в источниках любой из нескольких математических библиотек, доступных в Интернете (fdlibm — хорошая отправная точка).
Набор инструкций x86 предоставляет ряд инструкций, которые поддерживают математические функции, такие как exp, log и sin, но они больше не используются широко, поскольку хорошие реализации программных библиотек обеспечивают более высокую производительность.
Самый простой метод — использовать метод Ньютона. По сути, это интеллектуальная версия метода «угадай и проверь», в которой вы используете исчисление, чтобы понять, что следует угадывать.
Чтобы использовать метод Ньютона, сначала вы должны сформулировать свой вопрос в форме "дана функция f, значение x которой удовлетворяет условию f(x) = 0". В этом случае, если мы пытаемся найти квадратный корень из c, мы хотим, чтобы f(x) = x 2 - c, потому что, если мы подставим sqrt из c, мы получим f(sqrt(c)) = sqrt (в) 2 - с = с - с = 0.
Чтобы применить метод Ньютона, нам нужна f', производная от f, которая согласно основному исчислению равна f'(x) = 2x.
Затем метод Ньютона предлагает нам выбрать начальное предположение, x_0, а затем сделать следующее предположение равным x_1 = x_0 - f(x_0)/f'(x_0).Если мы будем повторять это уравнение снова и снова, мы будем все ближе и ближе приближаться к правильному значению. Попробуем на примере!
x_1 = 1 - (1 - 7)/2 = 4
x_2 = 4 - (16 - 7)/8 = 2,875
x_3 = 2,875 - (2,875 2 – 7)/(2*2,875) = 2,65489130435
Теперь фактическое значение квадратного корня из 7 составляет около 2,64575131106, и вы можете видеть, что мы получили довольно близкое значение всего после трех итераций этого алгоритма. Существуют и другие методы, используемые компьютерами, некоторые из которых быстрее, но в основном все они используют этот принцип, используя производные, чтобы делать более точные предположения.
Существуют и другие алгоритмы, но они обычно используются только в тех случаях, когда скорость настолько важна, что можно пожертвовать точностью.
Стоит также отметить, что этот метод сходится очень быстро. Каждая итерация примерно удваивает количество точных цифр.
Другие ответы дают конкретные алгоритмы для вычисления квадратного корня, но с точки зрения вычислений они действительно не относятся к делу.
Решение квадратных корней относится к классу задач, которые легко проверяются. Для всех входных данных X любое найденное решение-кандидат (назовем его предположение) можно проверить следующим образом:
если (догадка * догадка == X), то успех
или, что более реалистично, мы определяем некоторую минимально допустимую ошибку, называемую epsilon, и проверяем:
если(абсолютное_значение(догадка*догадка - X) < эпсилон), то успех
Более того, каждое предположение говорит нам что-то об окончательном решении проблемы. Если предположение*предположение меньше X, то фактическое решение должно быть больше, чем предположение. Если предположение * предположение больше, чем X, то фактическое решение должно быть меньше, чем предположение. Это устанавливает верхнюю и нижнюю границы истинного решения.
Итак, сложив все это вместе, задача нахождения квадратного корня обладает следующими свойствами:
Любое предположение может быть эффективно проверено
Проверка каждого предположения устанавливает новую верхнюю или нижнюю границу истинного решения
Следствием этого является то, что любой разумный алгоритм поиска может эффективно находить квадратные корни. Метод Ньютона делает некоторые сильные предположения, которые позволяют ему очень быстро находить квадратный корень примерно за ~15 итераций. Но бинарный поиск может найти квадратные корни примерно за 40 итераций. Фактически, случайный поиск с верхними и нижними границами может найти квадратный корень примерно за 700-800 шагов итерации (начиная с нижней границы в нуле и верхней границы в наибольшем представимом положительном числе). Все эти цифры приведены для точности вплоть до представления значения с плавающей запятой одинарной точности, или эпсилон = 0,00000001.
Хотя никто не хочет использовать случайный поиск на практике, он всего на порядок медленнее, чем самые эффективные алгоритмы, и не будет заметен для людей на современном компьютерном оборудовании. Сравните это с известными сложными задачами, такими как взлом шифрования или решение задачи коммивояжера, где случайный поиск займет больше времени, чем возраст Вселенной, чтобы решить нетривиальные формулировки задачи.
Ученые из Университета Рочестера использовали ДНК, чтобы создать простой компьютер, вычисляющий корни идеальных квадратов до 900, сообщает New Scientist. Компьютер упорядочивает числа примерно до 1000 на нити с помощью двоично-кодированных маркеров, а растворы подсвечиваются с помощью флуоресценции.
В новой статье, опубликованной Small, объясняется, почему ДНК-компьютер уникален и мощен. Предыдущие компьютерные модели ДНК могли вычислять квадратные корни из 4-битных двоичных чисел. Это означает, что всего четыре цифры равны 0 и 1, а максимальное значение 15 соответствует диапазону из 16 значений, начинающихся с 0. Компьютер Гуо выполняет вычисления с 10 битами, что означает 1024 значения в диапазоне от 0 до 1023.
Вычисление квадратных корней из полных квадратов, то есть целых чисел, имеющих целые квадратные корни, является логически сложным, но все же может быть выполнено с помощью механических схем и логических вентилей. Команда Го говорит, что ее компьютер работает с квадратами до 900, хотя есть еще один хитрый идеальный квадрат с размером 961, а 1024 сам по себе является идеальным квадратом.
ДНК-вычисления во многом схожи с квантовыми вычислениями, поскольку оба предполагают позиционирование молекул и частиц как механическую форму вычислений. Команда Гуо также считает, что ДНК-вычисления присоединятся к квантовым вычислениям как метод, который в конечном итоге может превзойти вычисления на кремниевых чипах.
Сегодня взаимодействие обычного человека с компьютером кажется крайне далеким от механики и логики, которые на самом деле выполняет аппаратное обеспечение.Между нашими клавиатурами и электрическими импульсами, проводящими операции на уровне схемы, есть слои и слои программирования, которые становятся все более сложными и математическими и менее узнаваемыми как язык.
При написании кода на Java или даже HTML часто используются целые обычные слова, такие как "main" и "strong", и они преобразуются в двоичные строки для выполнения. Эти струны усложняются, но по-прежнему исполняются как микровсплески электричества. Именно в этой простой механике и работают ДНК-вычисления. Проходя по цепи, импульс сталкивается с воротами (переключателями), подобными тем, которые перенаправляют железнодорожные пути.
ДНК — это естественный формат для выполнения двоичных вычислений, поскольку естественно связанные пары оснований образуют подразумеваемый двоичный и логический путь. ДНК, которую команда Гуо использовала в своем компьютере, состоит из двух отдельных цепей, которые связаны в процессе, называемом гибридизацией, создавая совершенно новую цепочку, не связанную с клетками живых существ.
«Он может вычислять квадратный корень из 10-битного двоичного числа (в пределах десятичного целого числа 900), создавая последовательности ДНК и программируя реакции смещения нитей ДНК», — говорится в аннотации команды. Меняющиеся нити и последовательности запускают цветовые коды, которые показывают ответ. Это отсылка к самым ранним дням появления механических компьютеров с максимально возможной перспективой.
Этот контент создается и поддерживается третьей стороной и импортируется на эту страницу, чтобы помочь пользователям указать свои адреса электронной почты. Дополнительную информацию об этом и подобном контенте можно найти на сайте piano.io
Схема в пробирке, состоящая из логических вентилей на основе ДНК, может вычислять квадратный корень из чисел до 15, используя ДНК.
Ребекка Бойл | Опубликовано 3 июня 2011 г., 23:47
Схема в пробирке, состоящая из логических элементов на основе ДНК, может вычислять квадратный корень из чисел до 15, используя репликацию ДНК и связывание последовательности для проведения вычислений. Это мучительно медленно — расчет может занять до 10 часов — так что органические ноутбуки точно не в нашем ближайшем будущем. Но настоящий прорыв заключается в том, как эта система может управлять химическими системами.
Согласно новой статье, опубликованной сегодня, исследователи из Калифорнийского технологического института спроектировали самую сложную биохимическую цепь из когда-либо созданных с нуля. Схема использует ДНК вместо электронных транзисторов для создания сигналов включения-выключения и/или сигналов, которые позволяют компьютеру проводить свои расчеты.
В типичном компьютере транзисторы пропускают внутрь и наружу ток электронов. Вместо этого ДНК-компьютер использует фрагменты короткой одноцепочечной или частично двухцепочечной ДНК, помещенные в пробирку с соленой водой. Нити торчат, как щупальца, из двойной спирали ДНК, как объясняется в пресс-релизе Калифорнийского технологического института. Молекулы ДНК сталкиваются в воде и связываются друг с другом, производя и высвобождая молекулы-потомки. Они действуют как сигналы, как электроны в традиционном чипе, и перемещаются между «воротами» ДНК, соединяя цепь.
Пары вентилей могут создавать логику и/или на основе наблюдаемых выходных молекул, как объясняет Ars Technica. (Ознакомьтесь с постом Ars Technica для более подробного объяснения того, как это работает.)
Исследователи под руководством научного сотрудника с докторской степенью Лулу Цянь могут кодировать любую последовательность ДНК, которую они хотят, поэтому они полностью контролируют взаимодействие нитей ДНК.
Их самый большой компьютер представлял собой 74-молекулярную четырехбитную схему, которая могла вычислять квадратный корень из любого числа до 15, округляя ответ до ближайшего целого числа. Чтобы получить ответ, исследователи будут отслеживать концентрацию выходных молекул в пробирке, используя флуоресцентную метку.
Процесс занимает много времени, но скорость не имеет значения — с помощью этого метода ученые могут в конечном итоге разработать биохимические пути, способные принимать решения. Этот тип контроля над химическими реакциями может быть полезен для всего, от фармацевтики до промышленных процессов. Представьте себе компьютерные чипы на основе ДНК, встроенные в вашу кожу и выпускающие лекарства в нужное время, или ДНК-компьютер, который может изучать концентрацию определенных молекул в образце крови и быстро диагностировать заболевание.
По словам исследователей, схему можно масштабировать до более крупных ДНК-компьютеров. Их также можно настроить, изменив типы используемых ДНК или перенастроив схему.
«Мы хотим создавать все более совершенные биохимические цепи, которые могут выполнять более сложные задачи, заставляя молекулярные устройства воздействовать на окружающую среду», — сказал Цянь в пресс-релизе. Компьютер был описан в статье в сегодняшнем номере журнала Science.
Читайте также: