Алгоритм извлечения корня квадратного: Алгоритм вычисления корня n-ой степени из произвольного положительного числа

Содержание

Алгоритм извлечения квадратного корня столбиком — Алгебра — Математика — Каталог статей

Этот способ позволяет найти приближённое значение корня из любого действительного числа с любой наперёд заданной точностью.

Для ручного извлечения корня применяется запись, похожая на деление столбиком. Пусть извлекается корень из целого числа A. В отличие от деления снос производится группами по две цифры, причём группы следует отмечать, начиная с десятичной запятой (в обе стороны), дописывая необходимым количеством нулей.

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

Провести вычитание из старших разрядов A квадрата числа an.

Удвоить an.

Сдвинуть остаток от вычитания на 2 разряда влево, а величину 2an – на один разряд влево. Под сдвигом в данном алгоритме понимается умножение / деление на степени 10, что соответственно является сдвигом влево и вправо.

Приписать справа от остатка вычитания два следующих старших разряда числа A.

Сравнить полученное число с нулём.

Если полученное число не равно 0, то найти такое 2an − 1, которое, будучи умноженным на (2an10+an− 1), даст в результате число, меньшее полученного на четвёртом шаге, но наиболее близкое к нему по значению. Перейти к п. 3.

Если в п. 6 получено равенство, то перейти к п. 4, предварительно приписав справа от an нуль.

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

Описанная последовательность действий в математике получила название алгоритма извлечения квадратного корня.

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

2.         Чтобы найти первую цифру корня, извлекают квадратный корень из первой грани.

3.         Чтобы найти вторую цифру, из первой грани вычитают квадрат первой цифры корня, к остатку сносят вторую грань и число десятков получившегося числа делят на удвоенную первую цифру корня; полученное целое число снова подвергают испытанию.

4.         Испытание проводится так: за вертикальной чертой (слева от остатка) пишут удвоенное, ранее найденное число корня, и к нему с правой стороны приписывают испытуемую цифру; получившееся после этой приписки число умножают на испытуемую цифру. Если после умножения получится число, больше остатка, то испытуемая цифра не годится и надо испытать следующую меньшую цифру.

5.         Следующие цифры корня находят с помощью того же приёма.

6.         Если после снесения грани число десятков получившегося числа окажется меньше делителя, т.е. меньше удвоенной найденной части корня, то в корне ставят 0, сносят следующую грань и продолжают действие дальше.

Пример. Извлечём корень√8649  .

1-й шаг. Число 8649 разбиваем на грани справа налево; каждая из которых должна содержать две цифры. Получаем две грани: √86’49 .

2-й шаг. Извлекаем квадратный корень из первой грани 86, получаем  √86≈9 с недостатком. Цифра 9 – это первая цифра корня.

3-й шаг. Число 9 возводим в квадрат (92 = 81) и число 81 вычитаем из первой грани, получаем 86 – 81 = 5. Число 5 – первый остаток.

4-й шаг. К остатку 5 приписываем вторую грань 49, получаем число 549.

5-й шаг. Удваиваем первую цифру корня 9 и, записывая слева, получаем:

√86’49 = 9

¯ 81

18… ¯¯¯¯¯549¯¯¯¯¯

К числу 18 нужно приписать такую наибольшую цифру, чтобы произведение числа, которое мы получим, на эту цифру было бы либо равно числу

549, либо меньше, чем 549. Это цифра 3. Она находится путем подбора: количество десятков числа 549, то есть число 54 делится на 18, получаем 3, так как 183 ∙ 3 = 549. Цифра 3 – это вторая цифра корня.

6-й шаг. Находим остаток 549 – 549 = 0. Так как остаток равен нулю, то мы получили точное значение корня – 93. Процесс извлечения корня закончился. Число 93 – двузначное, так как подкоренное число 8649 содержит две грани. Корень из числа содержит столько цифр, сколько граней содержит это число.

Аналогично извлекают квадратный корень из десятичных дробей. Только подкоренное число разбивают на грани так, чтобы запятая была между гранями, т.е. от запятой влево и вправо. Если в крайней правой грани окажется одна цифра, то её дополняют дописыванием к числу нуля.

Как извлекать квадратный корень в столбик? Показываю простой алгоритм! | Математика не для всех

Подписывайтесь на канал в Яндекс. Дзен или на канал в телеграм «Математика не для всех», чтобы не пропустить интересующие Вас материалы. Также есть группы в VK, Одноклассниках и Facebook : всё для математического просвещения!

Еще в школе Вас научили складывать и вычитать, умножать и делить в столбик. Более «закаленные» математики помнят, что и многочлены в школьном курсе математики приходилось делить на бумаге. А что же с извлечением квадратного корня? Интуиция подсказывает, что и эта операция может быть выполнена на бумаге достаточно просто, и она нас не обманывает. Давайте посмотрим вместе, как это сделать. Поехали!

Извлекаем квадратный корень из 6-значного числа

Гостем сегодняшней программы является число 341187. Попробуйте, не заглядывая дальше, прикинуть, чему равен квадратный корень из него. Первую цифру, наверняка, Вы отгадаете, и это будет 5, а вот дальше становится сложнее. Однако, цифра 5 является «толчком» для следующих действий.

Первые шаги мы уже описали

Первые шаги мы уже описали

Обратите внимание, что я поставил апострофы, чтобы было удобно сносить цифры. Почему по две цифры? Потому что, любое число меньше 10 в квадрате состоит не более, чем из 2 цифр. (в сиутации с кубическим корнем всё сложнее). Итак, продолжим:

Объясняю: каждое число, которое будет получаться в результате, мы будем умножать на 2 и сносить вот таким образом:

Здесь подробнее:

  1. Вычитаем из 34 квадрат числа, не превосходящий его. Получаем 9.
  2. Сносим вторую пару чисел, получаем 911.
  3. Умножаем 5 на 2, получаем 10 и записываем его слева от 911.
  4. Ставим точки, обозначающие следующую цифру результата.

Теперь у нас следующая задача: найти число вида 10n, которое при умножении на n, будет меньше 911. Очевидно, что это число — 8, ведь 108*8=864 < 911, а 108*9=972>911.

Запятая между разрядами не нужна)

Запятая между разрядами не нужна)

Теперь вычитаем и получаем 47, приписываем оставшиеся две цифры справа, умножаем 58 на 2 и приписываем слева с точкой:

Аналогично находим, что за точкой скрывается число 4. Теперь поправочка: если бы корень извлекался нацело, то на этом этапе получился бы 0. В нашей ситуации, всё не так: результат будет дробным. Впрочем, никто не мешает приписать справа два нуля и продолжить извлечение корня:

Проверьте на калькуляторе: всё правильно! Понравилось? Тогда попробуйте решить эту математическую задачу менее, чем за одну минут. На это способны лишь 2% людей! Проверьте себя!

Путеводитель по каналу «Математика не для всех» — здесь собрано больше 100 статей на самые разнообразные темы: как для новичков, так и для более начитанных математиков!
Второй проект канал «Русский язык не для всех»
Источник: https://res.cloudinary.com/teepublic/image/private/s—JOzHZHK2—/t_Preview/b_rgb:262c3a,c_lpad,f_jpg,h_630,q_90,w_1200/v1538993948/production/designs/190280_2.jpg

Источник: https://res.cloudinary.com/teepublic/image/private/s—JOzHZHK2—/t_Preview/b_rgb:262c3a,c_lpad,f_jpg,h_630,q_90,w_1200/v1538993948/production/designs/190280_2.jpg

Спасибо! Надеюсь, было очень интересно и познавательно! Буду рад, если Вы поддержите меня ПОДПИСКОЙ, ЛАЙКОМ или даже критическим комментарием. ССЫЛКА НА ДЗЕН-КАНАЛ и TELEGRAM.

**************************************************************************

Алгоритм извлечения квадратных корней для экзаменов, ЦТ и ЕГЭ.

Извлечение квадратных корней из чисел без использования калькулятора часто вызывает у абитуриентов определенные сложности. На ЦТ и ЕГЭ по математике запрещено пользоваться калькуляторами, а вот корни квадратные рассчитывать приходится крайне регулярно. В представленном ниже файле приведен специфический экзаменационный алгоритм по извлечению квадратных корней. Данный алгоритм содержит в себе информацию о том, как именно нужно поступать с квадратными корнями именно на ЦТ или ЕГЭ, а также о том, как заранее правильно подготовится к выполнению такой процедуры на экзамене.

 

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

 

Как успешно подготовиться к ЦТ по физике и математике?

Для того чтобы успешно подготовиться к ЦТ по физике и математике, среди прочего, необходимо выполнить три важнейших условия:

  1. Изучить все темы и выполнить все тесты и задания приведенные в учебных материалах на этом сайте.
    Для этого нужно всего ничего, а именно: посвящать подготовке к ЦТ по физике и математике, изучению теории и решению задач по три-четыре часа каждый день. Дело в том, что ЦТ это экзамен, где мало просто знать физику или математику, нужно еще уметь быстро и без сбоев решать большое количество задач по разным темам и различной сложности. Последнему научиться можно только решив тысячи задач.
  2. Выучить все формулы и законы в физике, и формулы и методы в математике. На самом деле, выполнить это тоже очень просто, необходимых формул по физике всего около 200 штук, а по математике даже чуть меньше. В каждом из этих предметов есть около десятка стандартных методов решения задач базового уровня сложности, которые тоже вполне можно выучить, и таким образом, совершенно на автомате и без затруднений решить в нужный момент большую часть ЦТ. После этого Вам останется подумать только над самыми сложными задачами.
  3. Посетить все три этапа репетиционного тестирования по физике и математике. Каждый РТ можно посещать по два раза, чтобы прорешать оба варианта. Опять же на ЦТ, кроме умения быстро и качественно решать задачи, и знания формул и методов необходимо также уметь правильно спланировать время, распределить силы, а главное правильно заполнить бланк ответов, не перепутав ни номера ответов и задач, ни собственную фамилию. Также в ходе РТ важно привыкнуть к стилю постановки вопросов в задачах, который на ЦТ может показаться неподготовленному человеку очень непривычным.

Успешное, старательное и ответственное выполнение этих трех пунктов, а также ответственная проработка итоговых тренировочных тестов, позволит Вам показать на ЦТ отличный результат, максимальный из того, на что Вы способны.

 

Нашли ошибку?

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

2) ): от идеи до реализации

В статье собрана и проанализирована информация о методах вычисления корня квадратного, приведены ссылки на материалы. Сделана попытка синтезировать на основе двух методов алгоритм нахождения модуля вектора: оценка модуля вектора алгоритмом “альфа максимум плюс бета минимум” и последующее уточнение значения с помощью метода Ньютона.


Ссылки по вычислению квадратного корня:
вычисление квадратного корня на tms320f2812
Очень нужна помощь в оптимизации алгоритма извлечения квадратного корня
Корень квадратный, Как взять быстро?
Квадратный корень в целых числах, Benchmark for ARM
Magical Square Root Implementation In Quake III

Часть 1.

Полезная добытая информация из статей.

IQMath — это библиотека TI только для работы с fixed-point процессорами. А мой процессор, TMS320F28335 — floating-point. И эта библиотека для него не подходит.

Для floating-point процессоров есть RTS Library, в которой все оптимизировано: sprc664 –это про fastRTS, sprc624 – это про “не ANSI, но быстро” (про fpu библиотеку)
В частности в SPRC664 сказано:


Примерный список методов извлечения корня приведем ниже ( ссылка ):

1.  Арифметический

2.  Грубая оценка

3.  Столбиком

4.  Вавилонский способ  

5.  Метод Герона

6.  Метод Ньютона

7.  Десятично


Арифметический способ

Для квадратов чисел верны следующие равенства:

1 = 12
1 + 3 = 22
1 + 3 + 5 = 32
и так далее.

То  есть,  узнать  целую  часть  квадратного  корня  числа  можно,  вычитая  из него все нечётные числа по порядку, пока остаток не станет меньше следующего вычитаемого  числа  или  равен  нулю,  и  посчитав  количество  выполненных действий. Например, так:

9 − 1 = 8
8 − 3 = 5
5 − 5 = 0

Выполнено 3 действия, квадратный корень числа 9 равен 3.

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

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

RISC-команд» (в книге целый раздел, посвященный извлечению корня!)

Часть 2.

Идея.

Можно запрограммировать метод Ньютона (он же очень похож на вавилонский), но в качестве первого приближения использовать алгоритм αMax + βMin ( “ альфа максимум плюс бета минимум” )

Что значит вычислить корень из х?

Если под корнем стоит некое число а, то мы должны найти такое число g, чтобы:

Или по-другому :

Напомним, что g — это искомое значение корня, а а — это подкоренное число (или число, передаваемое в виде аргумента в функцию, например, sqrt( a ) для нахождения значения квадратного корня из а).

Уравнение (3) переписывается иначе:

Уравнение (4) полезно как выражение, задающее условие продолжения работы цикла в программе С++ в неком итерационном подходе вычисления g (этот итерационной подход — вычисление квадратного корня методом Ньютона). Пока мы не найдем точное значение g, значения gi и a/gi не будут совпадать, поэтому точное значение корня квадратного g будет находиться между двумя этими числами. Тогда логично, что следующее наилучшее приближение для  gi+1 будет среднее арифметическое gi и a/gi. Из этих соображений и вырос, видимо, метод Ньютона:

Вопрос: что выбирать в качестве первого приближения g0 для алгоритма Ньютона? Много методов в книгах описано. Но мне хочется попробовать своеобразный способ, мало описанный в литературе. И главное, что этот способ идеально подходит нам, т.к. ожидается, что сделает наиболее близкое приближение к истинному квадратному корню из числа, тогда потребуется минимум итераций метода Ньютона, чтобы достичь истинное значение, т.к. двигаться мы будем не от целого начального приближения (например, для х=5 начальное приближение g0 может быть 4), а от вещественного первого приближения, например, 2.1 . Алгоритм называется “альфа максимум плюс бета минимум”. Он нам подходит еще и потому, что оперирует в понятиях векторного числа, у которого есть синфазная и квадратурная составляющие, т.е. де-факто I и Q составляющие. Фактически, это метод вычисления модуля комплексного числа. Достаточно точный метод.


Часть 3.

От идеи к алгоритму.

Часть 4

Реализация.


  1. #ifndef SQRTIQ_HPP
  2. #define SQRTIQ_HPP
  3. #ifdef ITERATIONS
  4. //for debug
  5. int iterationCnt;
  6. #endif
  7. template< class T >
  8. T sqrtIQ( T i, T q ) {
  9. #ifdef ITERATIONS
  10. //for debug
  11. iterationCnt = 1;
  12. #endif
  13. //first estimation for Newton’s algorithm. This estimation is found
  14. //by means of «alpha max plus beta min» algorithm
  15. T firstEstimation;
  16. //current value of estimation
  17. T nextEstimation;
  18. T radicand;
  19. T quotient;
  20. //coefficients for «alpha max plus beta min»:
  21. //alpha = 1. 0, beta = 0.5 therefore they don’t need to be present in memory
  22. //begin — «alpha max plus beta min» algorithm
  23. if( i > q ) {
  24. firstEstimation = i +  q/2;
  25. }
  26. else {
  27. firstEstimation = q +  i/2;
  28. }
  29. //end — «alpha max plus beta min» algorithm
  30. //begin — Newton’s algorithm
  31. i *= i;
  32. q *= q;
  33. radicand = i + q;
  34. quotient = radicand/firstEstimation;
  35. nextEstimation = ( firstEstimation + quotient )/2;
  36. while( firstEstimation — nextEstimation != 0 ) {
  37. firstEstimation = nextEstimation;
  38. nextEstimation = ( firstEstimation + quotient )/2;
  39. //for next iteration check in while()
  40. quotient = radicand/firstEstimation;
  41. #ifdef ITERATIONS
  42. //for debug
  43. ++iterationCnt;
  44. #endif
  45. } //while
  46. return firstEstimation;
  47. //end — Newton’s algorithm
  48. }
  49. #endif // SQRTIQ_HPP

Х.

Рамиль Альварес. Троичный алгоритм извлечения квадратного корня

Методические рекомендации:

Решение задач на тему «Представление чисел в компьютере». Типы задач. 1. Целые числа. Представление чисел в формате с фиксированной запятой. 2. Дробные числа. Представление чисел в формате с плавающей

Подробнее

n q 1 a 1 a a q n A = n n q n m s 2

Лекция 5 Основы представления информации в цифровых автоматах Позиционные системы счисления Системой счисления называется совокупность приемов и правил для записи чисел цифровыми знаками. Любая предназначенная

Подробнее

Введение в программирование

Введение в программирование Цели семинара:. Научиться стоить алгоритмы, содержащие ветвление и зацикливание.. Потренироваться писать программы с операторами if, switch while, do while и for. 3. Научиться

Подробнее

= 4

Коррекционная карточка 6 класс: Действия с рациональными числами (с помощью координатной прямой) 1. Построить координатную прямую, указав начало координат и единичный отрезок. Отметить на координатной

Подробнее

Понятие системы счисления

Понятие системы счисления Для записи информации о количестве объектов используются числа. Числа записываются с использованием особых знаковых систем, которые называются системами счисления (с/с). Алфавит

Подробнее

ПОЗИЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ

ПОЗИЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ Известно множество способов представления чисел. В любом случае число изображается символом или группой символов (словом) некоторого алфавита. Будем называть такие символы

Подробнее

2015 года (профильный уровень).

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

Подробнее

a x j a j Пример: 28=1*2 4 +1*2 3 +1*2 2 +0*2 1 +0*2 0

Лекция 2 Цифровые методы представления информации. Цифровые коды. Двоичная и шестнадцатиричная системы счисления. Перевод чисел из одной системы счисления в другую. Двоичная арифметика. Формы представления

Подробнее

ПРАВИЛА ПРИБЛИЖЁННЫХ ВЫЧИСЛЕНИЙ

ПРАВИЛА ПРИБЛИЖЁННЫХ ВЫЧИСЛЕНИЙ Терминология Цифры знаки для записи чисел. В десятичной системе счисления, которой мы, в основном, пользуемся, это 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Всего десять цифр. 0 (ноль)

Подробнее

Бабкина Наталья Анатольевна

Бабкина Наталья Анатольевна «Машинные» системы счисления. Представление целых чисел в компьютере. Цели- задачи: Знать: Основные понятия: переполнение, дискретность, машинные системы счисления. Особенности

Подробнее

Распишем подобным образом дробное число:.

Лекция Системы счисления Подумайте, сколькими разными способами можно записать число «десять» Один способ уже представлен в предыдущем предложении Можно назвать еще достаточно много способов написания

Подробнее

Представление чисел в ЭВМ

А. А. Вылиток Представление чисел в ЭВМ 1. Информация и данные Информация (от лат. information разъяснение, изложение) содержание (смысл) сообщения или сигнала, сведения, рассматриваемые в процессе их

Подробнее

Системы счисления (СС)

Системы счисления (СС) I. Двоичная система счисления. Как устроено число в десятичной СС: 579 0 =5 0 7 0 9 0 0 ( a 0, a 0). В любой другой позиционной системе счисления числа устроены точно таким же образом.

Подробнее

Тема 1. Элементы теории погрешностей

— 1 — Тема 1 Элементы теории погрешностей 11 Источники и классификация погрешностей Численное решение любой задачи, как правило, осуществляется приближенно, те с некоторой точностью Это может быть обусловлено

Подробнее

Арифметические основы компьютеров

Арифметические основы компьютеров (По материалам http://book.kbsu.ru/) 1. Что такое система счисления? Система счисления это совокупность приемов и правил, по которым числа записываются и читаются. Существуют

Подробнее

Системы счисления Пример 1.

Системы счисления В наше время человек всё время сталкивается с числами. Все мы с детства знакомы с общепринятой записью чисел при помощи арабских цифр. Однако этот способ записи использовался далеко не

Подробнее

Обобщения. Примеры решения задач

Алгоритмы быстрого возведения в степень (дихотомический алгоритм возведения в степень, бинарный алгоритм возведения в степень) алгоритмы, предназначенные для возведения числа x в натуральную степень n

Подробнее

Тема: Системы счисления

Коротко о главном Тема: Системы счисления Системы счисления — это способ представления чисел и соответствующие ему правила действия над числами. Разнообразные системы счисления, который существовали раньше

Подробнее

Представление чисел в компьютере

Представление чисел в компьютере ГОУ СОШ с углубленным изучением математики, информатики, физики 444 Числа Целые Вещественные Без знака Со знаком Прямой код Положительные Отрицательные Прямой код = Дополнительный

Подробнее

Компьютерная арифметика

1 Компьютерная арифметика 26. Особенности представления чисел в компьютере 27. Хранение в памяти целых чисел 28. Операции с целыми числами 29. Хранение в памяти вещественных чисел 30. Операции с вещественными

Подробнее

ОГЛАВЛЕНИЕ. Предисловие… 5

ОГЛАВЛЕНИЕ Предисловие……………………………………… 5 Глава первая Арифметика и алгебра………………………………. 6 1.1. Числа и действия с ними………………………..

Подробнее

Задания С6 ЕГЭ олимпиадного характера

Задания С6 ЕГЭ олимпиадного характера 1. Все члены конечной последовательности являются натуральными числами. Каждый член этой последовательности, начиная со второго, либо в 11 раз больше, либо в 11 раз

Подробнее

Введение в системы счисления

Введение в системы счисления А. А. Вылиток Система счисления это способ записи чисел с помощью заданного набора специальных знаков (цифр). Существуют позиционные и непозиционные системы счисления. В непозиционных

Подробнее

Представление целых чисел в компьютере

Представление целых чисел в компьютере Вся информация, которую обрабатывает компьютер представлена в двоичном коде с помощью двух цифр: 0 и 1 Привет! 1001011 Целые числа представлены в двоичной системе

Подробнее

B2 (базовый уровень, время 2 мин)

B2 (базовый уровень, время 2 мин) Тема: Оператор присваивания в языке программирования 1. Что нужно знать: переменная это величина, которая имеет имя, тип и значение; переменная может изменяться во время

Подробнее

6-2 (базовый уровень, время 4 мин)

К. Поляков, 009-06 6- (базовый уровень, время 4 мин) Тема: Поиск алгоритма минимальной длины для исполнителя. Что нужно знать: исполнитель это человек, группа людей, животное, машина или другой объект,

Подробнее

Маслов С. П. Троичная схемотехника

Маслов С. П. Троичная схемотехника Схемотехника определяется как научно-техническое направление, охватывающего проблемы проектирования и исследования схем электронных устройств радиотехники и связи, вычислительной

Подробнее

6-1 (базовый уровень, время 4 мин)

6-1 (базовый уровень, время 4 мин) Тема: Выполнение и анализ простых алгоритмов. Что нужно знать: сумма двух цифр в десятичной системе счисления находится в диапазоне от 0 до 18 (9+9) в некоторых задачах

Подробнее

Вопросы для повторения I

4 Вопросы для повторения I. Натуральные числа. Натуральный ряд.. Числа и цифры. Десятичная система счисления. 3. Разряды и классы. Представление числа в виде суммы разрядных слагаемых. 4. Сравнение натуральных

Подробнее

Тема «различные способы извлечения квадратного и кубического корня из многозначных чисел»

Всероссийский конкурс исследовательских работ учащихся

“ПЕРВЫЕ ШАГИ В НАУКУ”

Направление: математика

Тема: «Различные способы извлечения квадратного и кубического корня

из многозначных чисел»

Выполнила: ученица 8«А» класса

МАОУ Новоильинский агротехнический лицей

Заиграевского района Республики Бурятия

Жерлова Анжелика

Научный руководитель: учитель математики

МАОУ Новоильинский агротехнический лицей

Зубарева Надежда Игоревна

г. Обнинск, 2011/2012 учебный год

Оглавление

1. Введение 3 стр

2. Различные способы извлечения квадратного и кубического корня из многозначных чисел:

а) Алгоритмы вычисления квадратного и кубического корня из многозначных чисел

5 стр

б) Алгоритмы быстрого извлечения квадратного и кубического корня. 10 стр

в) Приближенные методы вычисления квадратных корней (метод Ньютона и т.д) 12 стр

3. Заключение 14 стр

4. Список литературы 15 стр

Введение.

В этом году я и мои одноклассники изучали тему квадратные корни.

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

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

Я заинтересовалась и решила изучить этот вопрос глубже, чем он освещен в школьной программе, а также приготовить выступление для своих одноклассников. Цель работы: Исследовать различные способы вычисления арифметических корней.

Были намечены следующие задачи:

  1. Проанализировать математическую литературу по данной теме, использовать также интернет-ресурсы.

  2. Составить алгоритмы по вычислению квадратного и кубического корня в случаях его вычисления «нацело».

  3. Определить особенности вычисления арифметического корня, когда он не вычисляется «нацело»;составить алгоритмы вычисления квадратного и кубического корня, когда он не вычисляется «нацело».

  4. Привести примеры быстрого извлечения квадратного и кубического корней.

  5. Рассмотреть приближенные методы извлечения квадратного корня (метод Ньютона, способ которым пользовались в древнем Вавилоне)

  6. Оформить свое исследование в виде доклада.

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

Различные способы извлечения квадратного и кубического корня из многозначных чисел

Извлечение квадратного корня из целого числа «нацело»

Пример: найдём √212521

Шаги алгоритма

Пример

Комментарии

1

Разбить число на группы по 2 цифры в каждой справа налево

21’ 25’ 21

Общее число образовавшихся групп определяет количество цифр в ответе

2

Для первой группы цифр подобрать цифру, квадрат которой будет наибольшим, но не превосходящим числа первой группы

1 группа – 21

42=16

16<21

цифра — 4

Найденная цифра записывается в ответе на первом месте

3

Из первой группы цифр вычесть найденный на шаге 2 квадрат первой цифры ответа

_21’ 25’ 21

16

5

4

К остатку, найденному на шаге 3, приписать справа (снести) вторую группу цифр

_21’ 25’ 21

16__

525

5

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

4*2=8

цифра – 6

86*6=516

516<525

Найденная цифра записывается в ответе на втором месте

6

Из числа, полученного на шаге 4 вычесть число, полученное на шаге 5. Снести к остатку третью группу

_21’ 25’ 21

16

_525

516

921

7

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

46*2=92

цифра 1

921*1=921

Найденная цифра записывается в ответе на третьем месте

8

Записать ответ

√212521=461

√5963364=&, т. е. &2=59633

Шаги алгоритма

Пример

Комментарии

1

Разбить число на группы по 2 цифры в каждой справа налево

5`96`33`64

Общее число образовавшихся групп определяет количество цифр в ответе

2

Для первой группы цифр подобрать цифру, квадрат которой будет наибольшим, но не превосходящим числа первой группы

1 группа – 5

22=4

4<5

цифра — 2

Найденная цифра записывается в ответе на первом месте

3

Из первой группы цифр вычесть найденный на шаге 2 квадрат первой цифры ответа

_5`96`33`64

4

1

4

К остатку, найденному на шаге 3, приписать справа (снести) вторую группу цифр

_5`96`33`64

4

196

5

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

2*2=4

цифра – 4

44*4=176

176<196

Найденная цифра записывается в ответе на втором месте

6

Из числа, полученного на шаге 4 вычесть число, полученное на шаге 5. Снести к остатку третью группу

_5`96`33`64

4

196

176

2033

7

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

24*2=48

цифра 4

484*4= 1936

1936<2033

Найденная цифра записывается в ответе на третьем месте

8

Из числа, полученного на шаге 6 вычесть число, полученное на шаге 7. Снести к остатку последнюю группу

_5`96`33`64

4

196

176

2033

-1936

9764

9

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

244*2=488

цифра 2

4882*2= 9764

9764= 9764

Остаток =0.

Найденная цифра записывается в ответе на четвертом месте

8

Записать ответ

√5963364=2442

Извлечение квадратного корня из целого числа (корень не извлекается «нацело»)

Пример: найдём √123456

Шаги алгоритма

Пример

Комментарии

1

Установить точность извлечения 1/10m

m = 3

Определить количество знаков в ответе после запятой

2

Разбить число на группы по 2 цифры в каждой справа налево

12’ 34’ 56

3

Создать группы в дробной части числа, приписав, справа нули

12’ 34’ 56’, 00’ 00’ 00

Количество приписываемых нулей сокращается с заявленной точностью. В нашем примере – 6 нулей

(3 группы, так как m=3)

4

Использовать алгоритм 1, начиная со 2 шага

√123456000000=351,363

_9_

_334

325

_956

701

_25500

21069

443100

421596

­_2150400

2108169

42231

Извлечение квадратного корня из десятичной дроби

Пример: найдём √104,2441

Шаги алгоритма

Пример

Комментарии

1

Разбить число на группы по 2 цифры в каждой

1’ 04’, 24’ 41

Цифры, входящие в целую часть числа разбить справа налево, а цифры, входящие в дробную часть – слева направо

2

Установить точность

m = 4

1’ 04’, 24’ 41’ 00’ 00

Если число группы в дробной части больше m, отбросить лишнее; если меньше m — составить недостающие группы из нулей

3

Использовать алгоритм 1, начиная со 2 шага

√104,25520000=10,2105

1

_00425

404

_2152

2041

_1110000

1001025

108975

Я решила попробовать доказать этот способ.

Основой этого способа, является состав числа

an an-1 ….a2 a1 a0= an10n+ an-110n-1 +…+a2102+ a1101+ a0

Доказательство приведено мной для случаев:

1. Извлечение квадратного корня из трехзначного числа;

2. Извлечение квадратного корня из четырехзначного числа.

abc=100a+10b+c mn = 10m+n

2m*10+n √abc =mn

n m2

(a-m2)100+10b+c

20mn+n2

100a-100m2+10b+c-20mn-n2

т. к корень извлекается, то остаток равен 0

100a-100m2+10b+c-20mn-n2=0

Для удобства разбиваем на части т.е.

100a+10b+c=100m2+20mn+n2

abc=(10m+n)2

числоabc это квадрат числа mn

Докажем возможность извлечения квадратного корня из четырехзначного числа

abcd =1000a+100b+10c+d

2m*10+n √ab cd =mn

n m2

(10a+b-m2)100+10c+d

20mn+n2

1000a+100b-100m2+10c+d-20mn-n2=0

1000a+100b+10c+d=100m2+20mn+n2

abcd=(10m+n)2 это квадрат числа mn

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

Пример: найдём

Шаги алгоритма

Пример

Комментарии

1

Установить точность извлечения

, m=2

2

Обратить обыкновенную дробь в десятичную

=2,4285

Число десятичных знаков поле запятой определяется заявленной точностью, удвоив её

3

Извлечь приближенный корень из десятиной дроби, полученной на шаге 2(использовать алгоритм 1)

-√2,4285

≈1,55

_1

_142

125

_1785

1525

260

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

Например: найдём √3

с точностью до

√3 = 3,00000000 ≈ 1,7320

1

_200

189

_1100

1029

_7100

6924

17600

Точность вычисления можно увеличить, использую следующее утверждение: если после вычисления n значащих цифр (общее количество цифр до и после запятой) корня остаток от вычисления разделить на удвоенное найденное значение корня, то частное даёт n-1 следующих цифр корня.

В качестве примера увеличим точность извлечения квадратного корня из числа 3. Для этого остаток 176 разделим на удвоенное значение раннее найденного значения корня (1,732*2=3,464). Получим следующие 2 цифры: 50, то есть √3 = 1,732050

Извлечение кубического корня из целого числа «нацело»

Пример: найдём 3√74088

Шаги алгоритма

Пример

Комментарии

1

Разбить число на группы по 3 цифры справа налево

74’088

В первой группе могут оказаться три цифры, две или одна

2

Извлечь кубический корень из числа первой группы

43=64

64<74

число 4

Найденная цифра записывается в ответ на первом месте

3

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

_74’088

64

10088

4

В числе, найденном на шаге 3 отделить 2 цифры справа

_74’088

64

100’88

5

Оставшееся на шаге 4 число разделить на утроенный квадрат найденного числа корня

100/(42*3)=2

6

Найти второй остаток

_74’088

64

_100’88

96

488

Найденный остаток сверяется с , где a=4, b=2. Если они равны, то найденное число верно

7

Записать ответ

3√74088=42

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

Многие из нас знают метод извлечения квадратного корня разложением числа на простые множители. В нашей работе представлен ещё один способ, с помощью которого можно узнать целую часть квадратного корня числа. Способ настолько прост, что пользоваться им может ребенок, обладающий простыми навыками вычисления.

Заметим, что для квадратов чисел верны следующие равенства:

1=12

1+3=22

1+3+5=32

1+3+5+7=42 и т.д.

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

Пример: найдём √529

Решение: 1)_529

1

2)_528

3

3)_525

5

4)_520

7

5)_513

9

6)_504

11

7)_493

13

8)_480

15

9)_465

17

10)_448

19

11)_429

21

12)_408

27

13)_385

25

14)_360

27

15)_333

29

16)_304

31

17)_273

33

18)_240

35

19)_205

37

20)_168

39

21)_129

41

22)_88

43

23)_45

45

0

Ответ: √529 = 23

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

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

13 = 1

23 = 8

З3 = 27

43 = 64

53 = 125

63 = 216

73 = 343

83 = 512

93 = 729

103=1000

Обратим внимание на то, что цифры 1,4,5,6,9 в своём кубе оканчиваются на эту же цифру. В остальных же случая последняя цифра куба равна разности между 10 и числом возводимым в куб.

Извлекать кубический корень научимся на практических примерах

Пример: найдём 3√46656

Шаги алгоритма

Пример

Комментарии

1

Отделить тысячи

46

2

Найти число, куб которого наиболее близкий, но меньше числа, полученного на шаге 1

27

Воспользоваться таблицей 1

3

Извлечь кубический корень из числа, полученного на шаге 2

3√27=3

Найденная цифра записывается в ответе на первом месте

4

Рассмотреть оставшиеся цифры

656

5

Найти число куб которого заканчивается такой же цифрой как число полученное на шаге 4

216

Воспользоваться таблицей 1

6

Найти кубический корень из числа, полученного на шаге 5

3√216=6√

Воспользоваться таблицей 1. Найденная цифра записывается в ответе на втором месте

7

Записать ответ

3√46656=36

Пример: найдём 3√274625

Шаги алгоритма

Пример

Комментарии

1

Отметить последнюю цифру числа. Определить последнюю цифру ответа

5

Воспользоваться таблицей 1. Найденную цифру записать на последнем месте

2

Зачеркнуть последние 3 цифры числа. Рассмотреть оставшееся число

274

Зачеркиваются три цифры числа независимо от количества его цифр

3

Найти число, куб которого наиболее близок, но не превосходит числа, полученного на шаге 2

216

Воспользоваться таблицей 1

4

Найти кубический корень числа, полученного на шаге 2

3√216=6

Воспользоваться таблицей 1. Найденная цифра записывается в ответе на первом месте

5

Записать ответ

3√274625=56

Заметим, что рассмотренные способы почти одинаковы. Предпочтение можно отдать любому из них.

Приближенные методы извлечения квадратного корня (без использования калькулятора) [2].

1.Древние вавилоняне пользовались следующим способом нахождения приближенного значения квадратного корня их числа х. Число х они представляли в виде суммы а2+b, где а2ближайший к числу х точный квадрат натурального числа а (а2<х), и пользовались формулой . (1)

Извлечем с помощью формулы (1) корень квадратный, например из числа 28:

Результат извлечения корня из 28 с помощью МК 5,2915026.

Как видим способ вавилонян дает хорошее приближение к точному значению корня.

2. Исаак Ньютон разработал метод извлечения квадратного корня, который восходил еще к Герону Александрийскому (около 100 л. н.э.). Метод этот (известный как метод Ньютона) заключается в следующем.

Пусть а1 — первое приближение числа (в качестве а1 можно брать значения квадратного корня из натурального числа — точного квадрата, не превосходящего х) .

Следующее, более точное приближение а2 числа найдется по формуле .

Третье, еще более точное приближение и т.д.

(n+1)-е приближение найдется по формуле .

Нахождение приближенного значения числа методом Ньютона дает следующие результаты: а1=5; а2= 5,3; а3=5,2915.

— итерационная формула Ньютона для нахождения квадратного корня из числа х (n=2,3,4,…, аn — n-е приближение .

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

Заключение

Описанные в работе методы извлечения корней встречаются во многих источниках. Тем не менее, разобраться в них оказалось для меня непростой задачей, что вызвало немалый интерес. Представленные алгоритмы позволят всем, кто заинтересуется данной темой, быстрее овладеть навыками вычисления квадратного и кубического корней, их можно использовать при проверке своего решения и не зависеть от наличия в кармане калькулятора. Тем более что на экзамене в 9 и 11 классах применение калькулятора не допускается.

Литература

1.В.А. Гусев, А.Т. Мордкович «Математика: справочные материалы»; Книга для учащихся – 2-е издание. –М: Просвещение,1990

2.И.Н. Сергеев, С.Н. Олехник, С.Б.Гашков «Примени математику». – М.: Наука, 1990

3. Керимов З., «Как найти целый корень?» Научно-популярный физико-математический журнал «Квант» №2, 1980

4. Петраков И.С. «математические кружки в 8-10 классах»; Книга для учителя.

–М.:Просвещение,1987

5. Тихонов А.Н., Костомаров Д.П. «Рассказы о прикладной математики».- М.: Наука. Главная редакция физико- математической литературы, 1979

6. Фурсенко В.Б. «Об алгоритме извлечения квадратного корня». «Математика и физика в школе». 1936. № 5.

Алгоритм извлечения квадратного корня. Посмотрите на красивую алгебру… | Автор Ujjwal Singh

Символ квадратного корня ( Credits : By historicair 17:50, 4 июня 2007 г. (UTC) — Изображение: Nuvola apps edu Mathmatic-p.svg, LGPL, https://commons.wikimedia.org /w/index.php?curid=2201984)

Люди были очарованы квадратными корнями с незапамятных времен, ранняя мотивация подпитывалась утилитарными вопросами, такими как «данная площадь, построить квадрат, равный площади». Для этого нам нужно знать длину стороны квадрата, которая, конечно, равна квадратному корню из площади.

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

Содержание

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

  1. Резюме: Процедуры вычисления квадратных корней.
  2. Алгоритм извлечения квадратного корня.
  3. Почему алгоритм работает? — Обоснование алгоритма.
  4. Алгоритм извлечения квадратного корня в двоичной системе счисления.
  5. Заключительные замечания.

Итак, имея полный квадрат, как мы можем определить его квадратный корень? Как вы, возможно, помните, для этой цели в средней школе повсеместно преподаются две элементарные процедуры —

  • Факторизация простых чисел: это наивный способ извлечения квадратных корней. Здесь мы выполняем простую факторизацию данного числа, а затем группируем факторы в пары по два.Затем мы умножаем числа из каждой группы, чтобы получить квадратный корень. Суть процедуры понятна. Например,
Вычисление квадратного корня из 900 с использованием простой факторизации.
  • Посимвольный расчет: обратите внимание, что описанный выше метод оказывается чрезвычайно утомительным при работе с большими числами. Кроме того, в случаях, когда наименьший простой множитель данного числа достаточно велик, мы можем даже не начать процедуру (например, 12643277 = 3089 * 4093). Вот тут-то и приходит на помощь метод посимвольного вычисления (далее именуемый алгоритмом квадратного корня или просто алгоритмом). И именно об этом эта статья — как работает алгоритм, его особенности и, самое главное, почему он работает (вероятно, самая упускаемая из виду часть)! Итак, давайте погрузимся прямо в это.

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

Во-первых, ниже приводится краткое описание некоторых символов. Пусть a и b — два натуральных числа.Тогда —

  • . Через ab мы представляем обычное умножение, т. е. ab = a * b .
  • С помощью a|b мы представляем число, образованное размещением b справа от .
    Например, если a = 789 и b = 23, то a|b = 78923.

Как обычно, алгоритм лучше всего понять на примере пошагового руководства. Итак, ниже вычисление корня 50 965 321 с последующими подробными шагами:

Квадратный корень из 50 965 321 с использованием алгоритма квадратного корня.

Шаги

  1. Сопряжение : Начиная справа, сгруппируйте цифры заданного числа парами по два. В приведенном выше примере группы выделены подчеркиванием — (21), (53), (96) и (50). Примечание. Если номер содержит нечетное количество цифр, то в самой левой группе будет только одна цифра.
  2. Начальная догадка : Начните с самой левой группы. Найдите максимальную цифру, квадрат которой меньше или равен крайней левой группе.
    В нашем примере число, представленное группой, = 50.
    Итак, максимальная цифра, квадрат которой ≤ 50, равна 7.
  3. Запишите вверху число, полученное на предыдущем шаге. Это сформирует первую цифру квадратного корня. Давайте назовем текущее число, присутствующее вверху, как « текущий частичный квадратный корень », обозначенный как p .
    В нашем случае текущий частичный квадратный корень, p = 7.
    Вычтите квадрат этого числа из самой левой группы и запишите остаток.
    В нашем случае остаток = 50–49 = 1.
  4. Теперь запишите цифры следующей группы рядом с остатком.
    Позвоните на новый номер r .
    В нашем примере мы уменьшаем 96, чтобы получить 196. Это r = 196.
  5. Удар и испытание :
    Теперь найдите наибольшую цифру d такую, что ((2p) |d) * d r .
    В нашем примере 2п = 2* 7= 14 (на рисунке показано красным цветом).
    Начинаем с d = 1, 141*1 = 141. Далее
    С d = 2, 142*2 = 284 > 196.
    Следовательно, для нашего случая d = 1.
  6. d , полученное на предыдущем шаге, является следующей цифрой квадратного корня. Итак, поместите его вверху, справа от текущего частичного квадратного корня.
    То есть p_new = p_old | д .
    Далее узнаем новый остаток как —
    остаток = r— (((2p)|d) * d)
    В нашем случае новое значение остатка = 196–141 = 55.
  7. Повторить шаги от 4 до 6, пока не исчерпаем заданное число. Если бы число было полным квадратом, то у нас был бы 0 в качестве последнего остатка, а квадратный корень был бы равен числу, стоящему вверху!

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

Квадратный корень из 2 989 441 с использованием алгоритма квадратного корня.

Вот мы и подошли к сути этой статьи! Почему работает алгоритм квадратного корня, в чем причина этого?

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

Представьте, что у вас есть натуральное число, и . Кроме того, у вас есть цифра b . То есть b является одним из 0–9.

Тогда у нас есть —

Это именно то, чем алгоритм пользуется. Основной принцип —

Если мы знаем все, кроме одной последней цифры квадратного корня числа, то мы можем получить оставшуюся цифру, вычитая в 100 раз квадрат числа, образованного другими цифрами, из квадрата заданного числа, а затем поиск цифры d такой, что ((2a)|d)d равно этой разнице.

Алгоритм начинается с начального предположения (этап 2 выше), а затем итеративно применяет описанный выше принцип для получения квадратного корня.

Дополнительное примечание : Этот принцип также объясняет, почему мы группируем цифры по две —

  • Во-первых, интуитивно понятно, что квадрат числа содержит примерно в два раза больше цифр, чем само число. Это потому, что если a — n-значное число, то —
  • Итак, справедливо ожидать, что две цифры из квадрата будут соответствовать одной цифре квадратного корня.
  • Теперь обратите внимание, что мы вычитаем 100-кратный квадрат частичного квадратного корня из (текущий остаток | следующая группа). Вот почему следующая группа должна состоять из двух цифр (с одной цифрой мы можем столкнуться с отрицательными числами).
  • Почему мы начинаем группировку справа, а не слева?
    Это потому, что если мы начнем группировать слева число, содержащее нечетное количество цифр, то справа у нас будет одна цифра. Таким образом, в последней итерации у нас будет только одна цифра, которую нужно записать рядом с остатком, чего не должно происходить.В таких случаях, хотя на первом шаге у нас будет одна цифра, это нормально, так как это начальный шаг предположения. Важно то, что каждая группа, поступающая в последующих итерациях, должна иметь две цифры .

Давайте рассмотрим другой пример —

Квадратный корень из 383 161 с использованием алгоритма квадратного корня.

шагов —

  1. Первоначальное предположение: поскольку 6 — это самая большая цифра, квадрат которой ≤ 38 (крайняя левая группа), первая цифра нашего квадратного корня равна 6.
  2. Далее, мы используем описанный выше принцип, чтобы получить следующую цифру квадратного корня. Наше число (чей квадратный корень нужно найти) на этой итерации равно 3831. Итак, из 3831 мы вычитаем 100-кратный квадрат текущего частичного квадратного корня. То есть 3831 — 100,6² = 231.
  3. Теперь мы ищем самую большую цифру, d , такую, что (12|d)d ≤ 231 (потому что 2 * текущий частичный квадратный корень = 2 * 6 = 12) . Получаем d = 1.
  4. Далее сносим следующую группу справа от остатка, чтобы получилось 11061.Обратите внимание, что 11061 = 383161 — 100,61² (61 — текущий частичный квадратный корень).
  5. Теперь мы ищем самую большую цифру, d , такую, что (122|d)d ≤ 11061 (поскольку 2 * текущий частичный квадратный корень = 2 * 61 = 122). Получаем d = 9.
  6. Поскольку последний остаток равен 0, мы нашли точный квадратный корень для данного числа!

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

  • 6 — наибольшее число, квадрат которого ≤ 38.
  • 61 — наибольшее число, квадрат которого ≤ 3831.
  • 619 — наибольшее число, квадрат которого ≤ 383161.

понимание алгоритма, попробовав его в двоичной базе!

Суть алгоритма остается прежней. То есть мы находим квадратный корень цифра за цифрой, опираясь на полученное до сих пор значение. Обратите внимание, что в двоичной системе счисления всего две цифры (также известные как биты) — 0 и 1.Давайте посмотрим, какие настройки нужны нашему алгоритму в бинарном мире.

Допустим, у вас есть двоичное число, a . Также у вас есть бит, b . То есть b равно 0 или 1.

Тогда —

Итак, основной принцип здесь —

Если мы знаем все, кроме последнего бита квадратного корня из числа, то мы можем получить к оставшемуся биту путем вычитания 4-кратного квадрата числа, образованного другими битами, из квадрата заданного числа, а затем поиска бита d, такого, что (a|0d)d равно этой разнице.

Давайте разберемся с этим на примере, квадратный корень из 10101001 (169)—

Квадратный корень из 169 в основании 2, используя алгоритм квадратного корня.

Шаги (поскольку большинство приведенных ниже шагов аналогичны шагам, описанным выше для вычислений с основанием 10, поэтому здесь мы использовали краткие формулировки, пожалуйста, обратитесь к примерам с основанием 10, если вы столкнулись с какими-либо пробелами в понимании) —

  1. Сопряжение: как прежде мы соединяем числа в группы по два справа налево.
  2. Первоначальное предположение: Крайняя левая группа равна 10 (т. е. 2). Итак, мы находим наибольший бит, d , такой, что ≤ 10. Получаем d = 1. Это первый бит нашего квадратного корня.
  3. Вычитаем 1 из 10 и сносим следующую группу справа от остатка. По сути, здесь мы делаем ((a|b)² — a²|00) .
  4. Теперь попробуем найти наибольший бит d такой, что (1|0d)d ≤ 110 . Получаем d = 1.Это следующий бит квадратного корня.
  5. Повторяем шаги 3 и 4, пока не будет исчерпано заданное число. Если бы число было полным квадратом, в конце мы получили бы нулевой остаток, а число наверху представляло бы квадратный корень. В нашем случае, поскольку мы начали с идеального квадрата (169 = 13²), мы получили 1101 в качестве окончательного ответа. 1101 — это двоичный эквивалент 13!

Pros
Обратите внимание, как упрощает выполнение алгоритма в бинарном мире!

Минусы
Однако за простоту приходится платить. Количество шагов для выполнения увеличивается, так как заданное число занимает больше цифр в двоичной системе по сравнению с десятичной системой. В приведенном выше примере нам потребовалось бы две итерации, чтобы получить квадратный корень из 169 по основанию 10. Однако в двоичной системе нам потребовалось бы четыре итерации, чтобы получить это.

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

  • 1 (1) — наибольшее число, квадрат которого меньше или равен 10 (2).
  • 11 (3) — наибольшее число, квадрат которого меньше или равен 1010 (10).
  • 110 (6) — наибольшее число, квадрат которого меньше или равен 101010 (42).
  • 1101 (13) — наибольшее число, квадрат которого меньше или равен 10101001 (169).

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

К счастью, недавно я пришел к доказательству алгоритма, просматривая что-то похожее в великом произведении Арьябхаты, Арьябхатия. Да, в итоге мне потребовалось 15 лет, чтобы окончательно убедить себя, почему алгоритм работает, но ожидание того стоило!

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

Цитируя Лапласа (1749–1827),

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

Чтобы почувствовать, насколько десятичная система разрядов облегчает наши вычисления — забудьте о квадратных корнях, попробуйте умножить 14 (XIV) на 42 (XLII) римскими цифрами и убедитесь сами!

Вывод алгоритма квадратного корня

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

Алгоритм:

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

Шаг 1: Сгруппируйте число в «двойках» из десятичной дроби. место. (Если у вас есть номер с нечетным количеством цифр, крайняя левая группа будет состоять только из 1 цифры. )

Шаг 2: Начните с первой группы из двух (группа на осталось). Эта группа может состоять только из одного номера, если ваш номер имеет нечетное количество цифр. Найдите наибольший квадрат меньше или равный этой группе цифр, и ее квадратный корень будет вашим первое приближение всего квадратного корня.

Шаг 3: Вычтите текущее приближение в квадрате и получите вниз на следующую группу чисел за ним. Это твой следующий номер работать с.

Шаг 4: Удвойте текущее приближение корня.

Шаг 5: Найдите цифру «единицы» удвоенного числа это приведет к числу, которое делится на число, которое вы в настоящее время работают с минимально возможным остатком. Это следующее число в вашем приближении к квадратному корню.

Шаг 6: Умножьте цифру «единицы» на удвоенную число плюс цифра «единицы».Вычесть это число из номер, с которым вы сейчас работаете, и сбить следующий группа цифр за ним. Это ваша следующая группа чисел работать с.

Шаг 7. Повторяйте шаги с 4 по 6, пока не получите приблизительное значение. с приемлемым количеством значащих цифр.


Диаграмма алгоритма:

Происхождение:

Квадратный корень из числа N равен числу M, так что M 2 = Н.Алгоритм квадратного корня устроен так, что мы берем квадрат корень числа в виде (X + R) 2 . Квадратный корень из это число, очевидно, (X + R). X представляет текущее приближение для квадратного корня, а R представляет остаток от числа осталось от аппроксимации. Наше приближение всегда будет быть правильным квадратным корнем из числа усеченного (не округляется) до количества цифр в нашем приближении. Если мы расширим наше число (X + R) 2 будет равно X 2 + 2RX + R 2 .Это дает нам основу для нашего вывода алгоритма квадратного корня.

Шаг 1. Квадратный корень из числа от 1 до 100 представляет собой число от 1 до 10. Кроме того, квадратный корень числа между 100 и 10000 — число между 10 и 100. И так далее. Поэтому, если число разбито на группы по две цифры в каждой от десятичной точки влево, количество цифр в целая часть квадратного корня этого числа будет равна количество групп фигур.

Шаг 2: Только первая группа из двух (или одной) цифр определяет первая цифра квадратного корня. Если первые два (или один) цифры представляют собой полный квадрат, то ничего не остается и процесс можно повторить для следующих двух цифр номера. Обычно это не так, а это значит, что часть первые две (или одна) неучтенные цифры и наше приближение не идеально. Это ведет к шагу 3.

Шаг 3: Возьмите расширенное значение нашего номера: X 2 + 2RX + Р 2 .Мы вычитаем текущее приближение, X 2 , что приводит к в 2RX+R 2 часть исходного номера, которая не учитывается ибо в нашем приближении. Это дает нам следующую ценность для работы с участием.

Шаг 4: Переписывание 2RX + R 2 дает нам R(2X + R). Мы видим, что наше текущее приближение, X, должно быть удвоено, что дает 2X, которые являются первыми цифрами числа, с которым мы будем работать.

Шаг 5: Чтобы найти следующее приближение, нам нужно Значение R.Это число должно делиться на следующую группу с наименьший остаток, как показано R(2X + R). (R, очевидно, делит этот номер.)

Шаг 6: Поскольку вы нашли приближение на основе этого числа, вы должны вычесть R (2X + R), чтобы учесть любой остаток из вашей предыдущей группы чисел.

Шаг 7: Процедуру можно повторять столько раз, сколько необходимо до тех пор, пока не будет найден остаток, что означает, что у вас есть фактический квадратный корень, или до тех пор, пока не будет приемлемое количество знаков после запятой. оцененный.


Схема происхождения:


Вернуться на главную страницу

Алгоритмы оценки квадратного корня | 101 Компьютеры

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

15 2 = 15 х 15 = 225

Обратная операция, заключающаяся в вычислении квадратного корня числа, не так проста без использования функции квадратного корня калькулятора. В этом сообщении блога мы рассмотрим, как точно вычислить квадратный корень числа с помощью Python, а затем реализуем и сравним два метода, которые использовались несколько столетий назад для оценки значения квадратного корня любого заданного числа:

.
  • Вавилонский метод,
  • Метод Бахшали.
Возведение в степень

Языки программирования высокого уровня, такие как Python, имеют арифметический оператор для возведения числа в степень степени.2 при использовании псевдокода.

В Python оператор возведения в степень равен ** . например:

# 5 в степени 2 равно 25 квадрат = 5 ** 2 # 5 в степени 3 равно 125 куб = 5 ** 3

# 5 в степени 2 равно 25

квадрат = 5 ** 2

# 5 в степени 3 равно 125

куб = 5 ** 3

Квадратный корень = В степени половины

Мы можем легко вычислить квадратный корень числа в компьютерной программе, используя оператор возведения в степень, зная, что:

√x = x ½ = x 0. 5

Итак, в Питоне:

# Квадратный корень из 25 равен… кврт = 25 ** 0,5

# Квадратный корень из 25 равен…

sqrt = 25 ** 0,5

Вавилонский метод

Процедуры вычисления/оценки квадратных корней были известны, по крайней мере, со времен древнего Вавилона в 17 веке до нашей эры. Метод Герона (также известный как вавилонский метод) из Египта первого века был первым достижимым алгоритмом для вычисления квадратного корня.

Этот подход основан на оценке предела следующей сходящейся последовательности:

Для реализации вавилонского метода вычисления квадратного корня мы будем использовать следующий алгоритм:

Код Python

Используйте приведенную выше блок-схему для завершения кода ниже:

Метод Бахшали

Этот метод приближения к квадратному корню был описан в древней индийской математической рукописи, называемой рукописью Бахшали. Он использует подход, аналогичный вавилонскому методу, с использованием другого сходящегося ряда, как описано ниже:

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

Алгоритм

Mental Square Roots — World Mental Calculation

Существует несколько способов мысленного вычисления квадратных корней (для чисел, которые еще не являются квадратами).В этом посте объясняется один эффективный метод мысленного вычисления квадратного корня из 6-значных чисел с точностью до нескольких знаков после запятой, как в соревнованиях Кубка мира по умственным вычислениям и Мемориады. Этот метод также распространяется на квадратные корни других чисел.

Подготовка:

Для этого метода полезно знать квадраты чисел от 31² = 961 до 99² = 9801.

Метод:

В этом примере мы найдем квадратный корень из 661062.

Шаг 1:

Используйте свои знания о квадратных числах, чтобы найти первые две цифры ответа.

Для 661062 мы видим, что 81² = 6561 < 6610 < 82² = 6724, поэтому первые две цифры равны 81. Все деления на шаге 3 и далее будут использовать эти первые две цифры.

Шаг 2:

Вычтите этот квадрат (810² = 656100) из вопроса и разделите остаток на 20.

661062 – 656100 = 4962

4962 / 2 = 248,1

Шаг 3:

Разделите на 81, чтобы получить следующую цифру ответа, и умножьте остаток на 10.

248,1 / 81 = 3 остатка 5,1

Ответ на данный момент равен 813, а остаток равен 5,1 x 10 = 51

Шаг 4:

Удалите перекрестные произведения ответа. Перекрестные произведения проще всего объяснить на отдельном примере:

Представьте, что ответ пока равен 987,6543

Не обращайте внимания на первые две цифры (98) и умножьте первую и последнюю цифры: 7 x 3 = 21

Затем умножьте вторую и предпоследнюю цифры: 6 x 4 = 24

Продолжайте складывать эти продукты, пока не дойдете до середины. Если число цифр нечетное (например, как в этом новом примере), то, когда вы дойдете до средней цифры, возведите ее в квадрат и разделите пополам. В этом примере у нас есть нечетное количество цифр в (7, 6, 5, 4, 3), поэтому, когда мы достигнем этого среднего числа 5: 5²/2 = 12,5

Всего имеем 21 + 24 + 12,5 = 57,5 ​​

Итак, вернемся к нашему исходному примеру 661062 с ответом 813…

.

Не обращайте внимания на первые две цифры (81), и у нас останется только одна цифра (3), поэтому мы вычтем 3²/2 = 4,5 из остатка (51)

51 – 4.5 = 46,5

Внимание! Иногда остаток слишком мал, так что при вычитании перекрестных произведений результат будет отрицательным. В этом случае вернитесь к шагу 3 и уменьшите новую цифру в ответе на единицу. В этом примере у нас нет проблем (46,5 > 0), но в противном случае нам пришлось бы вернуться к шагу 3 и шагу 4 и сделать:

248,1 / 81 = 2 остатка 86,1

861 – 2²/2 = 859

Шаг 5:

Повторяйте шаги 3 и 4, пока не добьетесь достаточной точности:

46. 5 / 81 = 0, остаток 46,5 (поэтому новый ответ 813,0…)

46,5 х 10 = 465

465 – (3 х 0) = 465

465 / 81 = 5 остаток 60 (поэтому новый ответ 813,05…)

60 х 10 = 600

600 – (3 х 5) – 0²/2 = 585

585 / 81 = 7 остаток 18 (поэтому новый ответ 813,057…)

18 х 10 = 180

180 – (3 х 7) – (0 х 5) = 159

(и т. д.)

Шаг 6:

Чтобы вычислить последнюю цифру, необходимо также оценить следующую цифру, чтобы знать, нужно ли округлять в большую или меньшую сторону.В нашем примере:

159 / 81 < 5 поэтому округлим в меньшую сторону и ответ (до трех знаков после запятой) будет 813,057 (не 813,058)

 

Сводка:

Этот алгоритм кажется сложным, но его не так уж сложно изучить. Для практики используйте обучающее программное обеспечение Memoriad или Pegasus, представленное на этом веб-сайте.

Существует также похожий метод вычисления кубических корней в уме.

Если у вас есть какие-либо вопросы или вы хотели бы получить консультацию специалиста от меня, вы можете связаться со мной здесь.2}{2г_0}$$.

Подстановка $\epsilon$ в $y = y_0 + \epsilon$ дает:

$$y = \frac{1}{2}\left (\frac{a}{y_0}+y_0\right).$ $

Этот результат можно представить в виде рекурсии:

$$y_i= \frac{1}{2}\left (\frac{a}{y_{i-1}}+y_{i-1}\ right).$$

Для достижения квадратичной сходимости по квадратному корню требуется начальная оценка корня $y_0$. Оценка, слишком далекая от истинного корня, приведет к тому, что сходимость будет линейной, а не квадратичной. Другими словами, если начальная оценка корня, $y_0$, намного меньше или больше, чем корень, то каждая итерация приближается к корню линейно в соответствии с:

$$y_i = \frac{y_{i-1 }}{2}.$$

Квадратичная сходимость возвращается к рекурсии, когда аппроксимация корня $y_i$ оказывается вблизи действительного корня. Поэтому требуется хорошая начальная оценка корня.

Еще одна особенность алгоритма извлечения квадратного корня Ньютона-Рафсона заключается в том, что каждая итерация требует выполнения деления. С точки зрения компьютерной арифметики деление, как правило, намного медленнее, чем умножение, за исключением случаев, когда эти операции могут быть реализованы как операции сдвига вправо и влево соответственно.

Существует несколько подходов к выбору $y_0$. Для чисел с плавающей запятой один из подходов состоит в том, чтобы разбить формат с плавающей запятой, т.е. в экспоненту и мантиссу компоненты. Оценка квадратного корня получается просто манипулирование экспонентой и сборка компонентов обратно опять таки. Этот подход работает для представлений с плавающей запятой, потому что мантисса представляет собой ограниченный диапазон чисел: от $0,5$ до $1,0$. Экспонента с плавающей запятой позволяет использовать гораздо больший набор чисел.{15}.$$

Поскольку мантисса обычно представляет собой число от 0,5$ до 1,0$, квадратный корень из мантиссы лежит между $\sqrt{2}/2$ и $1. 0$. Если квадратный корень мантиссы принимается равной $1,0$, оценка квадратного корня определяется как величина показателя степени, деленная на $2$. То дополнительные итерации, которые могут возникнуть в результате использования этого значения для $y_0$, обычно невелики. Итак, этот подход, хотя и не оптимальный, но представляет собой хороший, надежный подход, который легко реализовать и который не оказывает существенного влияния на производительность.

Другой подход к определению оценки квадратного корня заключается в использовании таблиц с целью уточнения начальной оценки и минимизации количества итераций, необходимых для сходимости к корню. Это подход, используемый для многих реализаций квадратного корня во многих процессорах с плавающей запятой. Исторически сложилось так, что не полностью указанная таблица была источником печально известной ошибки FDIV в процессоре Intel Pentium.

Во введении представлен алгоритм извлечения квадратного корня, основанный на алгоритме Ньютона и Рафсона. Кроме того, в нем обсуждается подход к оценке начального значения квадратного корня для значений с плавающей запятой, чтобы можно было достичь квадратичной, а не линейной сходимости к корню. Для целевого приложения вместо чисел с плавающей запятой используются 32-битные числа с фиксированной точкой. ( Примечание: Основная причина использования 32-битного представления с фиксированной точкой заключается в том, что алгоритм реализован для поддержки контроллера движения, встроенного в программируемую логику ПЛИС, а не в ПЛИС с использованием встроенного микропроцессора с программным ядром. )

Алгоритм извлечения квадратного корня Гольдшмидта поддерживает операции извлечения квадратного корня из некоторых современных процессоров с плавающей запятой. Его можно использовать для вычисления квадратных корней и обратных квадратных корней для процессоров с фиксированной точкой. В этом разделе алгоритм будет описан применительно к представлениям с фиксированной точкой. ( Примечание: реализация алгоритма для представлений с плавающей запятой может быть легко определена из последующего обсуждения. )

Начальная оценка квадратного корня фиксированной точки, $y_0$

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

$$\mathtt{msb}(S)=m=\lfloor{\log_2{S}}\rfloor-b_{fraction}$$

, где $S$ — 32-битное дополнение до 2, фиксированное -точечное значение с 16-битной дробной частью, т. {16}\right)$$

Установка количества итераций, необходимых для постоянной сходимости на обеих границах, позволяет реализовать алгоритм с использованием фиксированное количество итераций и устраняет требование проверки сходимости для завершения алгоритма.Однако форма функции квадратного корня означает, что она очень маловероятно, что ошибка в оценке будет одинаковой на обоих концах диапазона, представленного каждым $\mathtt{msb}(S)$. Мультипликативная корректировка, применяемая к каждому сегменту, может сделать количество итераций, необходимых для сходимости, одинаковым для каждой крайности сегмента и одинаковым для всех сегментов в диапазоне значений, для которых алгоритму потребуется вычислить квадрат корень и обратный квадратный корень.{16}N_{adj}\right)$$

Значение $N_{adj}$, которое делает количество итераций одинаковым для каждой границы сегмента, можно найти с помощью функции «Что, если» в Microsoft Excel . Таким образом, в дополнение к функции  $\mathtt{msb}()$, все, что требуется – это небольшая предварительно рассчитанная таблица для 27 сегментов для $m = \left[-12,\ldots,15\right)$. для оценки начального значения квадратного корня для алгоритма квадратного корня Гольдшмидта. (Примечание: для этих значений $m$ значение для $N_{adj}$ равно $1.Было найдено, что 23898296208219$ делает количество итераций, необходимых для сходимости, равным $5$. В представлении с фиксированной точкой FP32B16 для значений меньше 4096, т.е. $m=-12$, может быть возвращено некоторое подходящее значение для квадратного корня и обратного квадратного корня.)

Плавающая точка Goldschmidt $\sqrt{S} Алгоритм $ и $1/\sqrt{S}$ Описание

Существует два алгоритма вычисления Гольдшмидта $\sqrt{S}$ и $1/\sqrt{S}$. Эти алгоритмы будут определены в следующих двух подразделах.2_{i-1}$$

$$Y_i = \frac{3 — b_i}{2}$$

$$x_i = x_{i-1}Y_i$$

$$y_i = y_{i -1}Y_i$$

Алгоритм сошелся к корню и может быть остановлен, когда $b_i \le 1 — \epsilon$, где $\epsilon$ — заданная граница ошибки, или после заданного числа итераций . $\sqrt{S}$ и $1/\sqrt{S}$ задаются следующим образом:

$$\sqrt{S} = x_i$$

и

$$\frac{1}{\sqrt{ S}} = y_i$$

Плавающая точка Гольдшмидта $\sqrt{S}$ и $1/\sqrt{S}$ Алгоритм №2

Алгоритм №2 использует три переменные: $r$, $x$ и $ч$. Начальные значения этих переменных инициализируются следующим образом:

$$x_0 = S\left(\frac{1}{\sqrt{S}}\right)_{est}$$

$$h_0 = \frac{1}{2}\left(\frac{1}{\sqrt{S}}\right)_{est}$$

$$r_0 = \frac{1 — 2 x_0 h_0}{2} $$

Алгоритм выполняется путем вычисления следующих уравнений рекурсии:

$$x_i = x_{i-1}\left(1+r_{i-1}\right)$$

$$h_i = h_ {i-1}\left(1+r_{i-1}\right)$$

$$r_i = \frac{1 — 2 x_i h_i}{2}$$

Алгоритм сошелся к корню и может быть остановлен, когда $r_i \le \epsilon$, где $\epsilon$ — заданная граница ошибки, или после заданного количества итераций.$\sqrt{S}$ и $1/\sqrt{S}$ задаются следующим образом:

$\sqrt{S} = x_i$$

и

$$1/\sqrt{S} = 2h_i$ $

Выбор алгоритма для реализации в фиксированной точке

Тестирование этих двух алгоритмов с помощью Excel показало, что алгоритм №1 оказался более последовательным в отношении условия завершения. Несмотря на то, что целью было фиксированное количество итераций, то есть 6 или инициализация плюс еще пять циклов, алгоритм № 1, по-видимому, обеспечивал более надежный способ завершения. 2}$$

$$Y_i = \frac{3B-b_i}{2}$$

$$x_i = \frac{x_{i-1}Y_i}{B}$$

$$y_i = \frac{y_{i-1}Y_i}{B}$$

Алгоритм сходится, когда $b_i \le B (1-\epsilon)$, или когда было выполнено заранее определенное количество итераций.Результаты:

$$\sqrt{S_{FP}} = x_i$$

$$\frac{1}{\sqrt{S_{FP}}} = y_i$$

( Примечание: при реализации арифметики с фиксированной запятой обычно желаемым результатом является верхняя половина произведения двойной длины.При умножении чисел с фиксированной запятой с различным количеством дробных битов после вычисления любых произведений с фиксированной запятой требуется шаг нормализации. Этот шаг нормализации обычно включает в себя сдвиг произведения двойной длины вправо/влево по мере необходимости, чтобы обеспечить сохранение и запись в регистр результата правильного количества дробных битов.В описании алгоритма в этой статье поддерживается представление как FP32B16, т. е. 32-битное число с фиксированной запятой со знаком с 16 дробными битами. Таким образом, после каждого произведения результат двойной длины должен быть сдвинут вправо на количество дробных битов в представлении.

В арифметическом блоке с фиксированной запятой, реализованном для целевого приложения, сдвиги влево/вправо произведения двойной длины обеспечиваются бочкообразным сдвигом за один цикл на выходе умножителя.Это означает, что арифметическая операция сдвига вправо, показанная в приведенных выше уравнениях, бесплатна. Точно так же такие операции, как масштабирование по степени двойки, также бесплатны.

Наконец, для целевого приложения арифметические операции с фиксированной запятой были выполнены с использованием 32-битных значений со знаком. Произведение двойной длины с фиксированной запятой было сгенерировано с использованием 4-разрядного множителя Бута, а не множителя, построенного из встроенных 18-разрядных множителей-накопителей, доступных в FPGA целевого приложения.Разработанный по индивидуальному заказу множитель Бута не обеспечивает производительность за один или даже за 4 цикла. На самом деле, для вычисления произведения требуется 11 циклов (10 для множителя и 1 для сдвига барреля), поскольку в целевом приложении и АЛУ, и множитель фактически реализованы как 40-битные функции, чтобы обеспечить защитные биты на оба конца для поддержки связанных операций и улучшенного округления/усечения промежуточных результатов. В совокупности множитель Бута немного медленнее и использует меньше ресурсов, чем множитель, построенный с использованием встроенных аппаратных множителей целевой FPGA для аналогичного числового формата. )

Создание таблицы $Y_{est}[m]$

Как и алгоритмы с плавающей запятой, алгоритм с фиксированной точкой зависит от «хорошей» оценки $1/\sqrt{S_{FP}}$, чтобы ограничить количество итераций, необходимых для сходимости. Оценка квадратного корня ранее описанное является хорошей отправной точкой, и его просто необходимо инвертируется, чтобы обеспечить необходимую оценку для фиксированной точки Алгоритм Гольдшмидта. Таблица, содержащая предварительно вычисленные оценки обратных квадратных корней с фиксированной точкой, необходимые для алгоритма Гольдшмидта с фиксированной точкой, может быть создана следующим образом:

$$Y_{est}[m] = \frac{B}{\sqrt {2^m}N_{прил}}, \{m: -12\ldots+15\}$$

, где $N_{прил} = 1. 238982962$. С обратным квадратным корнем, предоставленным оценкой, предоставленной $Y_{est}[m]$, алгоритм сходится за пять итераций. ( Примечание: интересно, если оценка, предоставленная для алгоритма с фиксированной запятой, используется для алгоритма с плавающей запятой, сходимость алгоритма с плавающей запятой также составляет 5 итераций. )

Алгоритм фиксированной точки Гольдшмидта $\sqrt{S_{FP}}$ и $1/\sqrt{S_{FP}}$ обеспечивает эффективный способ найти квадратный корень и обратный квадратный корень из количество.Решения, предлагаемые алгоритмом, необходимы для реализовать решения закона косинусов, которые необходимы для преобразования управляющая переменная от угловой скорости вокруг шарнира до линейной скорость выдвижения приводов в целевом приложении. Это также обеспечивает преимущество, которое может быть легко расширен для поддержки деления, если эта математическая операция становится необходимым.

Вам также может понравиться. .. (рекламируемый контент)

Обучение детей программированию – рекурсивный алгоритм вычисления квадратного корня

Обучение детей программированию : Видео по Структуры данных и алгоритмы

9

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

Предположим, где находится самое большое квадратное число, меньшее или равное n.
Тогда мы можем переписать его как:




Рекурсивно заменив

Таким образом, мы можем реализовать следующее, сходя действительный корень до тех пор, пока ошибка (EPS) не станет достаточно малой:

 1
2
3
4
5
6
7
8
9
10
 
 по определению rSqrt(n, a, EPS = 1e-8):
б = п - а * а
х = а + б / а
т = х
# пока ошибка все еще большая
в то время как abs(x*x - n) > EPS:
х = а + b / (а + т)
# сойтись ответ
т = х
возврат x 
 по определению rSqrt(n, a, EPS = 1e-8):
    б = п - а * а
    х = а + б / а
    т = х
    # пока ошибка все еще большая
    в то время как abs(x*x - n) > EPS:
        х = а + b / (а + т)
        # сойтись ответ
        т = х
    возврат х 

Протестируйте решение, сравнив его с Math. функция кврт:

 1
2
 
 print(rSqrt(150, 12)) # 12.247448713888222
print(sqrt(150))      # 12.24744871391589 
 print(rSqrt(150, 12)) # 12.247448713888222
print(sqrt(150)) # 12.24744871391589 

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

– EOF (блог Ultimate Computing & Technology) —

GD Star Rating
a Рейтинговая система WordPress

685 слов
Последнее сообщение : Как отсортировать список по весу Хэмминга в C++?
Следующая запись : Обучение детей программированию — Алгоритм обнаружения уродливых чисел

Модификация быстрого алгоритма обратного квадратного корня [v1]

Препринт Статья Версия 1 Сохранено в портике. Эта версия не рецензируется.

, , *

Версия 1 : Получено: 1 августа 2019 г. / Утверждено: 5 августа 2019 г. / В сети: 5 августа 2019 г. (05:09:06 CEST)

Также существует рецензируемая статья этого препринта.

Валчик, С.Дж.; Мороз, Л.В.; Cieśliński, JL Модификация быстрого алгоритма обратного квадратного корня. Расчет 2019 , 7 , 41. Вальчик, CJ; Мороз, Л.В.; Cieśliński, JL Модификация быстрого алгоритма обратного квадратного корня. Расчет 2019, 7, 41. Копировать

Ссылка на журнал: Computation 2019, 7, 41
DOI: 10.3390/computation7030041

Цитировать как:

Вальчик, CJ; Мороз, Л.В.; Чеслинский, Ю.Л.Модификация быстрого алгоритма обратного квадратного корня. Расчет 2019 , 7 , 41. Вальчик, CJ; Мороз, Л.В.; Cieśliński, JL Модификация быстрого алгоритма обратного квадратного корня. Расчет 2019, 7, 41. Копировать

ОТМЕНИТЬ КОПИРОВАТЬ ДЕТАЛИ ЦИТАТА

Абстрактный

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

Ключевые слова

арифметика с плавающей запятой; обратный квадратный корень; магическая константа; Метод Ньютона-Рафсона

Тема

МАТЕМАТИКА И ИНФОРМАТИКА, Общая и теоретическая информатика

Это статья с открытым доступом, распространяемая в соответствии с лицензией Creative Commons Attribution License, которая разрешает неограниченное использование, распространение и воспроизведение на любом носителе при условии надлежащего цитирования оригинальной работы.

Комментарии (0)

Мы приветствуем комментарии и отзывы широкого круга читателей. См. критерии для комментариев и наше заявление о разнообразии.

Добавить комментарий

Ваш адрес email не будет опубликован.

2015-2019 © Игровая комната «Волшебный лес», Челябинск
тел.:+7 351 724-05-51, +7 351 777-22-55 игровая комната челябинск, праздник детям челябинск