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

Алгоритм извлечения квадратного корня

Журнал «Самиздат»: [Регистрация] [Найти] [Рейтинги] [Обсуждения] [Новинки] [Обзоры] [Помощь]

---

  ИЗВЛЕЧЕНИЕ КВАДРАТНОГО КОРНЯ

  Квадратным корнем из любого, данного, положительного числа называется число, которое будучи возведённым во вторую степень даст данное число. Положительное значение корня называется арифметическим квадратным корнем. Квадратный корень извлекается только из любого, данного, положительного числа. Квадратный корень из нуля есть ноль! Действие извлечения квадратного корня обратно действию возведения в квадрат. В основе алгоритма (схемы) извлечения корня лежат следующие математические факты: десятичная запись любого числа, например ab.cd , где a, b, c, d есть десятичные цифры, можно представить как ab.cd = 10 * a + b + 0.1 * c + 0.01 * d ; квадрат любой цифры от 1 до 9 находится в промежутке чисел от 1 до 99, то есть требует для записи два разряда. Квадрат 1 = 1 * 1 = 1. Квадрат 9 = 9 * 9 = 81. Квадрат любой десятичной дроби от 0,1 до 0,9 находится в промежутке чисел от 0,01 до 0,99, то есть требует для записи два разряда. Квадрат 0,1 = 0,1 * 0,1 = 0,01. Квадрат 0,9 = 0,9 * 0,9 = 0,81. В алгоритме используется формула

   ( 10 * a + b ) ^ 2 = 100 * a ^ 2 + 20 * a * b + b ^ 2 = 100 * a ^ 2 + ( 20 * a + b ) * b.

  Алгоритм.

  1. Разбиваем цифры исходного числа на пары: те, что стоят слева от десятичной запятой, группируем по две справа налево, а те, что правее — по две слева направо.

  2. Затем первый раз подбором вычисляем квадрат старшей цифры корня, чтобы он не превосходил числового значения крайней левой пары цифр исходного числа, но был к нему наиболее близок, и вычитаем его из этого числового значения. Записываем в результат первую цифру корня.

  3. Далее мы приписываем две, следующие слева направо в исходном числе, десятичные цифры к остатку вычитания. Отсюда понятно разбиение на пары (видно из формулы).

  4. Выбираем 2 * a — удвоенное число, образованное цифрами известного на данный момент результата извлечения корня.

  5. Сдвигаем 2 * a на разряд влево (умножаем на 10) и прибавляем к нему подбором следующую цифру корня b так, чтобы число ( 20 * a + b ) * b не превосходило числового значения остатка с приписанной к нему парой цифр исходного числа, но было к нему наиболее близко.

  6. Для этого выбираем перебором очередную цифру из цифр от 0 до 9 и образуем число 20 * a + b .

  7. Умножаем 20 * a + b на эту же самую цифру b, получаем число ( 20 * a + b ) * b.

  8. Вычитаем число ( 20 * a + b ) * b из числа, образованного остатком и приписанной к нему справа парой цифр исходного числа.

  9. Сравниваем остаток с числом ( 20 * a + b ) * b .

  10. Остаток больше числа ( 20 * a + b ) * b. Переход к пункту 6.

  11. Приписываем цифру b справа к результату извлечения корня, то есть к числу за знаком корня.

  12. Все пары цифр исходного числа обработаны?

  13. Нет. Переход к пункту 3.

  14. Да. Конец.

  

  Пример извлечения корня с описанием выполняемых действий из числа 57240.5625.

  Квадратный корень из 5’72’40.56’25 = 239.25………………….

  —————————4………………………………

  …………………………………1’72…………………………….

  —————————1 29……………….43 * 3 = 129

  ………………………………….. 43’40……………………………

  —————————-42 21………………469 * 9 = 4221

  ……………………………………..1 19’56…………………………

  ———————————95 64……………4782 * 2 = 9564

  …………………………………………23 92’25……………………….

  ———————————23 92 25…………47845 * 5 = 239225

  …………………………………………00 00 00

  1. Разбиваем цифры числа 57240.5625 на пары: те, что стоят слева от десятичной запятой, группируем по две справа налево, а те, что правее — по две слева направо. Получаем 5’72’40.56’25.

  2. Определяем квадратный корень из числа, соответствующего первой группы цифр слева — в нашем случае это 5 (ясно, что точно корень может не извлекаться, берем число, квадрат которого максимально близок к нашему числу, образованному первой группой цифр, но не превосходит его). В нашем случае это будет число 2. Записываем 2 в ответ — это старшая цифра корня.

  3. Возводим число, которое стоит уже в ответе, а это 2, в квадрат, и вычитаем его из числа, соответствующего первой слева группы цифр — из числа 5. В остатке остается 1.

  4. Приписываем к остатку справа следующую группу из двух цифр — 72 и получаем число 172. Число 2, которое уже стоит в ответе, умножаем на 2 и получаем 4.

  5. Теперь следите внимательно. Нам нужно число 4 сдвинуть на разряд влево (умножить на 10) и справа приписать (прибавить) одну цифру b, и число 4b умножить на b, то есть на ту же самую приписанную цифру. Результат должен быть как можно ближе к 172, но опять-таки не больше этого числа. В нашем случае, в результате подбора, это будет цифра 3. Её записываем в ответ рядом с цифрой 2, справа. Это следующая цифра в десятичной записи нашего квадратного корня.

  6. Из 172 вычитаем произведение 43 * 3 = 129, получаем в остатке 43.

  7. Повторяем предыдущие операции. Приписываем к 42 справа следующую группу цифр 40. Получаем число 4240. Число 23 в ответе умножаем на 2 и сдвигаем влево. К полученному числу 46_ после подбора приписываем справа (прибавляем к 460) одну цифру, такую, чтобы при умножении на нее получилось число, меньшее 4240, но наиболее близкое к нему. Это цифра 9 — следующая цифра в ответе, в десятичной записи квадратного корня, а число 4221.

  8. Далее у нас в числе стоит десятичная точка, ставим такую же точку в ответе после цифры 9. Продолжаем процесс, снося по две цифры после точки. Так же, как и ранее получаем две цифры корня после десятичной точки. Это 2 и 5. Понятно, что в общем случае, если остаток не равен нулю, можно сносить и два нуля, чтобы достичь желаемой точности извлечения корня.

  

---

---

Связаться с программистом сайта.

Сайт — «Художники» .. || .. Доска об’явлений «Книги»

Большинство современных не встроенных процессоров (например, x86 и ядра ARM) имеют аппаратные инструкции для непосредственного вычисления квадратных корней. Реализация аппаратных средств, поддерживающая эти инструкции, различна, но, как правило, это вариант в алгоритме с цифрой по цифре в школьной книге (хотя не всегда в базовом дворе, также могут использоваться базовые четыре или шестнадцать). Они обычно относятся к самым медленным элементарным арифметическим операциям на процессоре; тайминги, такие как 16-64 цикла, не являются редкостью, и эти инструкции часто не конвейерны.

В процессорах, которые не имеют прямых аппаратных команд с квадратным корнем (Itanium, PPC, others), типичный подход заключается в создании начальной оценки (либо с инструкцией, которая производит оценку, либо с помощью таблицы поиска), а затем уточняет эту оценку используя итерационный метод (обычно Ньютон или Голдшмидт). Вы могли бы отследить некоторые статьи Питера Маркштейна или Роджера Голливера по этому вопросу, если вы заинтересованы.

Более сложные математические функции (например, тригг-операции) обычно вычисляются путем уменьшения аргумента в некоторый фундаментальный домен и затем аппроксимации его полиномиальной или рациональной функцией.

Вы можете посмотреть источники любой из нескольких математических библиотек, которые доступны онлайн для более подробной информации (fdlibm — хорошая отправная точка).

Набор инструкций x86 предоставляет ряд инструкций, которые поддерживают математические функции, такие как exp, log и sin, но они чаще не используются, потому что хорошие реализации библиотеки программного обеспечения обеспечивают лучшую производительность.



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

Ключевые слова: квадратный корень, извлечение квадратного корня.

На уроках математики я познакомился с понятием квадратного корня, и операцией извлечения квадратного корн. Мне стало интересно извлечение квадратного корня возможно только по таблице квадратов, с помощью калькулятора или есть способ извлечения вручную. Я нашел несколько способов: формула Древнего Вавилона, через решение уравнений, способ отбрасывания полного квадрата, метод Ньютона, геометрический метод, графический метод (, ), метод подбора угадыванием, метод вычетов нечётного числа.

Рассмотрим следующие способы:

1. Извлечение корня путем разложения подкоренного числа на простые множители. Например.

Разложим на простые множители, используя признаки делимости 27225=5*5*3*3*11*11. Таким образом

1. Канадский метод.

   Методы извлечения квадратного корня

   Этот быстрый метод был открыт молодыми учёными одного из ведущих университетов Канады в 20 веке. Его точность — не более двух — трёх знаков после запятой.

где х-число, из которого надо извлечь корень, с-число ближайшего квадрата), например:

=5,92

1. Столбиком. Этот способ позволяет найти приближённое значение корня из любого действительного числа с любой наперёд заданной точностью. К недостаткам способа можно отнести увеличивающуюся сложность вычисления с увеличением количества найденных цифр. Для ручного извлечения корня применяется запись, похожая на деление столбиком

Алгоритм извлечения квадратного корня

1.От запятой отдельно дробную и отдельно целую части делим на грани по две цифры в каждой грани (целую часть — справа налево; дробную — слева направо). Возможно, что в целой части может оказаться одна цифра, а в дробной — нули.

2.Извлечение начинается слева направо, и подбираем число, квадрат которого не превосходит числа, стоящего в первой грани. Это число возводим в квадрат и записывает под числом, стоящим в первой грани.

3.Находим разность между числом, стоящим в первой грани, и квадратом подобранного первого числа.

4.К получившейся разности сносим следующую грань, полученное число будет делимым. Образовываем делитель. Первую подобранную цифру ответа удваиваем (умножаем на 2), получаем число десятков делителя, а число единиц должно быть таким, чтобы его произведение на весь делитель не превосходило делимого.

Подобранную цифру записываем в ответ.

5.К получившейся разности сносим следующую грань и выполняем действия по алгоритму. Если данная грань окажется гранью дробной части, то в ответе ставим запятую. (Рис. 1.)

Рис. 1	Рис. 2

Данным способом можно извлекать числа с разной точностью, например с точностью до тысячных. (Рис.2)

Рассматривая различные способы извлечения квадратного корня, можно сделать вывод: в каждом конкретном случае нужно определиться с выбором наиболее эффективного для того, чтобы меньше затратить времени для решения

Литература:

1. Киселев А. Элементы алгебры и анализа. Часть первая.-М.-1928 г