Главное меню

Каким образом калькулятор находит корень заданного числа?

Автор Taggeli, Март 15, 2024, 02:52

« назад - далее »

Taggeli

Как это решить Каким образом калькулятор находит корень заданного числа?.

Iam

Казалось бы, в извлечении корня нет никакой сложности -- используется метод последовательных приближений, например, метод половинного деления для решения уравнения x^2=a, придуманный для извлечения корня еще в Вавилоне. Однако 12-разрядное число -- это 40 двоичных бит, то есть уравнение с заданной точностью решается за 40 итераций, на каждой из которых необходимо возводить в квадрат, то есть совершать весьма медленную операцию умножения. При отсутствии быстродействующего аппаратного умножителя (наличие которого трудно ожидать в калькуляторе) каждое умножение (в той же 12-разрядной сетке, которая 40 бит) выливается в ~ 40 сложений и 40 сдвигов, к которым добавляются проверки условий и условные переходы. В результате только одних математических операций (сложений и сдвигов) за одно извлечение корня придется выполнить 3200 штук, плюс еще столько же вспомогательных.
Это сегодня процессор, выполняющий 50 миллионов операций в секунду и выполняющий 32-разрядное умножение (как и сложение) за один такт, стоит меньше доллара. Но раньше было не так, и чтобы калькулятор помещался на столе и стоил не как спортивный автомобиль или даже квартира в центре Нью-Йорка, разработчики были вынуждены сильно упрощать вычислительные блоки. Никаких параллельных АЛУ, все операции -- последовательные, бит за битом. Операция сложения 12-разрядных чисел разворачивается в 48 операций двоичного сложения (48 -- потому что использовалась двоично-десятичная кодировка, опять же, ради упрощения схемы), каждая -- в лучшем случае за один такт. Тактовая частота -- килогерцы, сложение за десятки миллисекунд, умножение -- за полсекунды. Извлечение корня по такому алгоритму заняло бы десятки секунд.
Метод Ньютона, взятый "в лоб", ускоряет сходимость, да требует деления. А оно страшно долгое и выигрыша не получается.
Поэтому в калькуляторах применили алгоритмы, которые еще в доэлектронную эру использовали для извлечения корня на бумаге, а позже на арифмометре. Только с учетом того, что деление -- операция долгая, как я говорил, а вот сдвиг -- то же деление, только на 2,4 и т.д.
                                                                              

Kantua

Для начала всякое число представляется в виде произведения целой степени четверки на какой-то множитель от 1 до 4. Скажем, 20 = 8*2,5, 0.05 = 0,025*2 (0,025 -это тоже целая степень четверки), и т. п. После чего извлекается корень из этого коэффициента, любым подходящим способом - через разложение в степенной ряд, интерполяционным (когда заранее известны значения функции в опорных точках, а значения в промежуточных вычисляются простой линейной интерполяцией, типа той, что применялась в таблицах Брадиса), столбиком... Полученный результат умножается на двойку в той же степени, в которой была четверка (понятно зачем и почему). Это и есть ответ.

Yon

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