Оригинальный метод извлечения квадратного корня
Интересующимся извлечением корней “в столбик” рекомендую новую статью С.В. Савича здесь.
Об извлечении квадратного корня в столбик я уже писала здесь. Сейчас хочу вам предложить модификацию этого метода, которая мне кажется гораздо более простой и красивой. Предложил ее Сергей Валентинович Савич, который и написал мне об этом. Метод был изобретен для арифмометра — механической вычислительной машины, на которой в свое время считали, причем очень активно. Вот что пишет сам Сергей Валентинович: “Схема вычисления квадратных корней была придумана мной в конце 70-х г., и мне хотелось даже опубликовать её описание. Но время арифмометров закончилось, и этот алгоритм остался только в моей памяти. Теперь немного истории. В 1975–76 гг. я учился в Ленинградском топографическом техникуме, и у нас было очень много высокоточных измерений и расчётов. Калькуляторов и ПК тогда ещё не было, всё считали на арифмометрах, а значения функций приходилось брать из толстых 7 — 10-значных таблиц. Тогда у меня и появилась мысль “научить’’ арифмометр вычислять корни. Проштудировал кучу литературы, но ничего подходящего не нашёл. Методы последовательных приближений (дихотомии, Ньютона) отложил как неэкономичные для реализации на арифмометре. Когда я узнал о свойстве арифметической прогрессии нечётных чисел, то решил попробовать на его основе разработать алгоритм извлечения квадратного корня. Наибольшую трудность представляло то, что я никак не мог сообразить, что делать с остатком от вычитания квадрата первой цифры из аргумента. Интуитивно было понятно, что решение где-то рядом. В общем, вертел этот остаток и так, и сяк, и в конечном итоге набрёл на правильное решение.” Как уже говорилось, идея очень красивая. В основе метода лежит следующее свойство суммы первых нечетных чисел:
Доказать это легко, если вспомнить формулу суммы первых членов арифметической прогрессии. Еще понадобится следующая идея, которая основывается на этом свойстве. Если требуется приписать к какому-то числу
справа еще одну цифру
, а потом умножить полученное число на эту же цифру, то сделать это можно сложением
последовательных нечетных чисел:
Действительно, давайте раскроем скобки во всех слагаемых справа и их перегруппируем:
А теперь можно изменять метод, о котором уже было рассказано. Я опишу каждый шаг, а затем на примере покажу, как он выполняется.
1. Сначала мы точно так же, как было описано, делим число, из которого будем извлекать квадратный корень, на группы цифр, по две цифры в каждой группе. Целую часть числа (то, что стоит слева от десятичной запятой) разбиваем на группы по две цифры справа налево, а дробную часть (начиная от первой цифры справа от десятичной запятой) — слева направо. Пример давайте рассмотрим тот же, что уже был просчитан. Можно будет сравнить, насколько проще получается алгоритм. Возьмем число . Итак, разбиваем цифры этого числа на пары
.
2. Из первой группы цифр слева вычитаем последовательно нечетные числа до тех пор, пока не получится отрицательное число. Запомним последнюю положительную разность, которая получилась —
, и то число, которое при этом вычитали —
. Если последняя разность равна
, то корень извлечен точно. В нашем примере можно вычесть два нечетных числа:
Это означает, что первая цифра корня —
, остаток
, вычитали при его получении число
. Здесь
— порядковый номер последнего нечётного числа. Далее, к последнему вычитаемому прибавим
. В нашем случае к
прибавляем
, получаем число
.
3. Теперь к остатку справа припишем следующую группу
из двух цифр подкоренного числа, получим число
. В нашем примере, приписывая следующие две цифры, получим число
. Из числа
снова начинаем вычитать последовательно нечётные числа, предварительно сдвинув вычитаемое на один разряд вправо. Эти нечётные числа формируются следующим образом: первое число, которое будем вычитать, будет число
, к которому справа припишем цифру
, т.е.
, затем
. Делаем вычитания до тех пор, пока остаток не станет меньше вычитаемого. И снова запомним остаток (это будет
), последнее вычитаемое
и количество вычитаний
. Если же получили разность
, и оставшиеся цифры в подкоренном числе — нули, то корень извлечён точно. В нашем примере делаем следующие действия:
, поэтому вычитания прекращаем. Было выполнено три вычитания, значит, следующая цифра корня —
.
4. Если нам нужно посчитать следующие цифры корня, то возьмём снова ту последнюю положительную разность, которую мы запомнили в п. 3, как и последнее вычитаемое
, увеличенное на
— как
. Для разбираемого нами примера получим
. И повторяем алгоритм, начиная с шага 3. В том случае, если первое вычитаемое
больше, чем
, то следующая цифра корня —
, так как ни одного вычитания сделать нельзя. В этом случае принимаем
за
,
за
, и выполняем действия, начиная с шага 3. Если же корень вычислен точно (последняя разность равна
и оставшиеся цифры справа в подкоренном числе — нули) или корень вычислен с требуемой точностью, то завершаем процесс. Далее я не буду описывать все шаги, просто приведу то, что получается, если все вычисления записать в столбик. Пояснения — в фигурных скобках.
{точность — 6 значащих цифр, 21 вычитание} Как видно из приведённого описания, этот способ легко может быть формализован и записан в виде программного кода для ЭВМ, причём время выполнения этой программы сопоставимо с временем выполнения операции деления. Сергей Валентинович предложил также некоторые изменения, упрощающие процесс вычислений и позволяющие повысить точность. Так, можно заметить, что после каждого цикла вычитаний цифры последнего вычитаемого, увеличенного на
(т.е.
, по нашему соглашению), представляют собой цифры удвоенного значения корня. Поэтому можно не подсчитывать число вычитаний, а просто разделить
, полученное из последнего вычитаемого, на
. Положение запятой можно определить, руководствуясь следующим правилом: количество цифр целой части результата равно количеству пар цифр в целой части аргумента, каждой паре цифр аргумента соответствует одна цифра результата.
Примеры:
аргумент 61 71 , 67 36 (1)
результат 7 8 , 5 6
аргумент 0 , 00 78 93 10 (2)
результат 0 , 0 8 8 8 4 3 1 2
Кроме этого, вдобавок можно получить ещё примерно столько же значащих цифр, сколько уже было получено, простым делением последнего остатка с приписанными неиспользованными парами цифр на последнее вычитаемое, увеличенное на . Для описанного нами примера имеем:
Здесь шесть цифр
являются, с учётом округления последней, верными. Отсюда получаем конечный результат с точностью 12 дес. знаков (!):
Конечно, вычислять вручную с такой точностью значения корней вряд ли целесообразно, но данное правило позволяет для нахождения корней с точностью 5-6 знаков ограничиться вычислением с помощью вычитания нечётных чисел только 3-х цифр.
Ни Сергей Валентинович, ни я нигде не встречали описание данного метода. Если кто-либо из вас где-то об этом читал, напишите, пожалуйста. Заранее большое спасибо.
Подробный пример извлечения квадратного корня на арифмометре можно увидеть в статье Савича С.В. здесь (www.twirpx.com/file/1096076/).
1 Извлечение квадратного корня в столбик | Математика, которая мне нравится:
[...] P.S. Красивую модификацию описанного метода извлечения квадратного корня, которую предложил С.В. Савич, можно найти здесь: http://hijos.ru/2012/04/25/krasivaya-modifikaciya-metoda-izvlecheniya-kvadratnogo-kornya/ [...]
25 Апрель 2012, 12:412 Марина:
Решила попробовать этот метод и сразу наткнулась на вопрос. Предположим, что необходимо извлечь корень из числа первая цифра которого чётная. Тогда после первых преобразований выражение 2n-1 будет равно нечетному числу => Тогда первая цифра корня, то есть B=.,5? На этом я и закончила рассмотрение данного метода. А хотелось бы докопаться до истины=)
[Ответить]
Елизавета Александровна Калинина Reply:
Сентябрь 7th, 2012 at 12:35
Марина, не очень понимаю, в чем проблема. Давайте рассмотрим пример. Возьмем, например, число
. Разбиваем это число на группы цифр:
. Теперь из первой группы цифр вычитаем последовательные нечетные числа до тех пор, пока разность остается положительной. Ясно, что можем вычесть только число
. Тем самым, первая цифра корня — это
, а разность, которая получилась, тоже равна
. Теперь к разности приписываем следующую группу цифр, получаем:
и продолжаем процесс дальше, как написано в п. 5.
[Ответить]
3 Корнеев В. Ф.:
(10a+b)b=(10a+1)+(10a+3)+(10a+5)+…+(10a+(2b-1)). Гениально!
А вот остальное, начиная с п.4, как-то очень сложно.
[Ответить]
Елизавета Александровна Калинина Reply:
Сентябрь 9th, 2012 at 17:43
Может, у меня плохо написано… Однако есть пример. В действительности все гораздо проще, чем в том методе, который обычно рассказывают. И красивее.
Вдруг подумала. А Вы исходный метод извлечения квадратного корня в столбик знаете? На всякий случай, он вот тут есть: http://hijos.ru/2010/12/22/izvlechenie-kvadratnogo-kornya-v-stolbik/
[Ответить]
4 Корнеев В. Ф.:
А почему адрес http://hijos.ru/2012/04/25/krasivaya-modifikaciya-metoda-izvlecheniya-kvadratnogo-kornya/, указанный в первом комментарии, приводит опять сюда, а не на стр. С.В. Савича?
[Ответить]
Елизавета Александровна Калинина Reply:
Сентябрь 9th, 2012 at 17:40
Не поняла, это автоматическая ссылка из статьи об извлечении квадратного корня в столбик именно на эту статью. К сожалению, странички у С.В. Савича, насколько знаю, нет. Он прислал мне этот метод по электронной почте.
[Ответить]
5 Вячеслав:
Елизавета Александровна, метод описанный Вами я знал давно. Вероятно он был в старых школьных учебниках и возможно есть в современных. А обоснование я ранее не встречал. Второй метод С.В.Савича для меня нов, но он мне показался более сложным и трудоёмким. Оба метода забываются, если ими не пользоваться регулярно. Недавно мне понадобилось извлекать корни, но под рукой не было ни калькулятора, ни таблиц, ни логарифмической линейки и я никак не мог вспомнить метод извлечения. Тогда мне пришло на ум извлекать корни методом, который я назвал методом последовательных приближений(МПП). Математики его называют каким-то научным термином. Этот метод очень прост, не требует ничего запоминать. Достаточно лишь знать простые арифметические действия.
[Ответить]
Елизавета Александровна Калинина Reply:
Февраль 18th, 2013 at 17:00
Вы правы, хорошо работает также метод Ньютона. Здесь интересно то, что этот метод был придуман для арифмометра, вычисления все очень простые. Кроме того, в методе последовательных приближений, в методе Ньютона мы не знаем, сколько верных цифр коня вычислено, сколько шагов потребуется, скажем, для нахождения 10 цифр корня. А здесь за один шаг находится одна цифра.
[Ответить]
6 Вячеслав:
Забыл написать, что методом последовательных приближений можно также просто извлекать корни любых степеней.
[Ответить]
18 Февраль 2013, 16:147 Вячеслав:
Елизавета Александровна, посмотрел я в интернете метод последовательных приближений и метод Ньютона и удивился, как математики умеют морочить головы не математикам, вводя непонятные термины: “итерация”, “сходимость процесса итерации”, “последовательность операторов”, “рекуррентно”. При таком описании метода, он недоступен для понимания не только школьникам начальных классов, но и студентам технических ВУЗов вроде меня. Я представляю этот метод очень просто и доступно для всех. Вот пример извлечения кубического корня из 5: Предположим, что искомый корень равен 2, возведем 2 в куб = 8, т.е больше 5, значит искомый корень меньше 2, примем корень равным 1,5 и возведем 1,5 в куб = 3,725 меньше 5, примем корень равным 1,75 в кубе = 5,36;. Такие арифметические действия можно продолжать, пока не получим достаточную точность. В нашем случае мы остановились на результате 1,75. На калькуляторе (корень кубический из 5)= примерно 1,71. Складывается впечатление, что математики намеренно излагают теорию недоступным языком.
[Ответить]
Елизавета Александровна Калинина Reply:
Февраль 19th, 2013 at 16:24
Вячеслав, то, что Вы предлагаете, это просто подбор. Это не метод последовательных приближений и не метод Ньютона. А так, для каждого метода хочется выяснить условия применимости и скорость сходимости. Отсюда сложности.
[Ответить]
8 Вячеслав:
Елизавета Александровна, для глубокого изучения математики можно излагать теорию с использованием специальных терминов. Для начального обучения это недопустимо. Для моего метода более соответствует определение МПП, чем просто подбор, и для приведенного примера и других подобных задач нет необходимости выяснять условия применяемости и скорость сходимости. Отсюда необоснованные сложности.
[Ответить]
Елизавета Александровна Калинина Reply:
Февраль 19th, 2013 at 21:08
Вячеслав, да, Вы правы, так в школе и рассказывают именно о методе подбора без всяких изысков. Так что для начального уровня ничего такого и нет.
[Ответить]
9 Вопиющий в пустыне:
А что делать, в случае извлечения корня из числа 119. С первой единицы вычтем единицу, тут все понятно, потом приписываем 19 и тут надо вычесть из этого числа 21. Но 19<21. Ноль вычитаний, значит, в ответе 10 целых, но что дальше делать, чтоб узнать, сколько десятых? Я приписываю к 19 два нуля и вычитаю из 1900 число 221, но ответ не сходится) При вычитании 211 тоже не сходится) Не хватает одного вычитания в обоих случаях)))
[Ответить]
Елизавета Александровна Калинина Reply:
Февраль 13th, 2014 at 15:41
Сначала нужно вычитать 201, так как уже есть число 20, и справа нужно к нему приписать 1. Получится 9 вычитаний, и останется 19.
[Ответить]
Елена Reply:
Февраль 17th, 2014 at 11:51
Помогите разобраться с числом 17665209
[Ответить]
Елизавета Александровна Калинина Reply:
Февраль 17th, 2014 at 13:13
Делим цифры на группы:
. Вычитаем:
, четыре вычитания, первая цифра корня
. Далее к оставшейся
приписываем следующую группу цифр:
и снова вычитаем:
, два вычитания, вторая цифра корня
. К оставшемуся числу
приписываем следующую группу цифр:
и т.д.
[Ответить]
10 Вячеслав:
Извлечь корень квадратный из 119 методом последовательных приближений или, как предлагает называть этот метод Елизавета Александровна, методом подбора очень просто. Принимаем первоначально приближенное значение 10, 10 в квадрате 100, что меньше 119. Следующее приближение 11, 11 в квадрате 121, что больше 119. Следующее приближение 10.9, что в квадрате 118,81 и снова меньше 119. Следующее приближение 10,91, что в квадрате 119,081 и т.д. Можно остановиться на значении 10,91 с избытком на 0,81. Более точное значение 10,9087… .
[Ответить]
14 Февраль 2014, 14:2611 Андрей:
Действительно данный метод легко реализуется программно, при этом он достаточно эффективен при вычислении больших чисел. На C++ программная реализация выглядит примерно так:
void Sqrt(DecimalNumber &result, const DecimalNumber &val) {
if (val > 1;
NDigit nCurPair = 0; // Digit index in ‘val’ integer
SymbolicArith nPair, nSub, nCount;
for (NDigit numIter = 0; numIter = nSub) {
nPair -= nSub;
nCount++;
nSub++; nSub++; // 1 + 2 = 3, 3 + 2 = 5, etc. // same with nSub += 2;
}
result.AppendDigit(nCount); // Add output digit
nSub–;
nSub.AppendDigit(0); // Same with nSub *= 10;
}
}
[Ответить]
31 Июль 2015, 1:2512 Димитрий:
Здравствуйте! Обычный метод извлечения корня столбиком я встречал в старых учебниках и справочниках ( кажется у Выгодского).
Так называемый метод Савича был приведён в руководству арифмометра “Быстрица”. Если не ошибаюсь
[Ответить]
Елизавета Александровна Калинина Reply:
Апрель 7th, 2016 at 22:16
Спасибо. Это полезная информация.
[Ответить]
13 Михаил П.:
Данный метод и еще один (более совершенный) алгоритм извлечения квадратного корня на основе свойства арифм.прогрессии нечетных чисел подробно описан в учебном пособии для машиностроительных ВУЗов
Рязанкин В. Н., Евстигнеев Г. П.. Тресвятский Н. Н., Вычислительные машины, ч. 1, М., 1957. Книга – не редкая, практически любой сайт, посвященный выч.счетным машинам имеет ссылку на эту книгу. В предисловии книги указано, что 3-я глава книги, описывающая методы извл.квадр.корня написана конкретно Рязанкиным В.Н.
[Ответить]
Елизавета Александровна Калинина Reply:
Апрель 12th, 2016 at 21:30
Спасибо!
[Ответить]
14 Сергей Валентинович:
Уважаемая Елизавета Александровна!
Увидел комментарий Димитрия и решил внести ясность в обсуждение “так называемого метода Савича”. В одном из первых своих писем Вам я писал, что этот алгоритм, возможно используется в виде каких-то модификаций в калькуляторах и математических сопроцессорах. Разбираясь в способах вычисления элементарных функций, я перечитал и изучил большое
количество самой разнообразной и весьма серъёзной литературы по этим вопросам (Некоторые из этих книг перечислены в списке литературы), и, конечно же, не стал бы публиковать от своего имени этот метод, если бы он был там описан. Справедливости ради надо отметить, что описанный мной алгоритм, в общем, тривиален, и было бы весьма странным и непонятным, если бы его не изобрели раньше, учитывая историю развития науки. В частности, читая недавно старинные книги по истории математики, я встречал упоминание о школе пифагорейцев, где уже тогда, в древние времена, обращалось внимание на свойство суммы нечётных чисел. Так что открытие мной этого метода имеет сугубо личный характер и может служить лишь иллюстрацией множественности путей поэнания свойств окружающего мира. Скажу только, что для меня лично поиски решения этой проблемы имеют ещё и яркую эмоциональную окраску, что даёт стимул к дальнейшим исследованиям.
Что касается арифмометра “Быстрица”, то я не поленился, нашёл оригинальное описание и инструкцию “www.alple.net/arif-ru/books.htm#bystritsa-2″. В этом описании нет ни слова об извлечении корня.
По поводу замечания Михаила П. могу добавить, что совсем недавно “раскопал” (интернет даёт такую возможность) интереснейшее издание – пятитомник Энциклопедия элементарной математики, 1951 г., и там тоже приводится описание похожей методики извлечения квадратного корня, правда, чуть упрощённой – для целых чисел, причём автор этой главы – всем известный и уважаемый учёный, педагог Владимир Модестович Брадис. Чтение таких книг – настоящее наслаждение. Как жаль, что эта энциклопедия не встретилась мне раньше.
“Более совершенный” метод, описанный Рязанкиным В.Н., на самом деле использует разность прогрессии 10, что в 5 раз больше 2, и поэтому больше подходит для расчётов в десятичной системе. Других преимуществ у него нет. Метод, описанный мной, оптимизирован для вычислений в двоичной системе и может быть реализован аппаратурно в процессорах.
В заключение хочу сказать, что целью публикации метода вычисления квадратного корня было познакомить интересующихся математикой с малоизвестным, незаслуженно забытым, и в то же время изящным и очень быстрым алгоритмом. Считаю эту задачу выполненной.
С уважением, С.В.Савич
Список литературы
Вычисление элементарных функций на ЭВМ. Благовещенский Ю.В., Теслер Г.С. Изд. Технiка, Киев 1977.
Принципы построения электронных клавишных вычислительных машин. Мараховский В.Б., Каневский Е.А.
Аппаратурная реализация элементарных функций в ЦВМ. Байков В.Д., Смолов В.Б.
О вычислениях при помощи арифмометра. Кочанов Н.С., Изд. Знание, Москва, 1967
Вычисление функций на ЭВМ. Попов Б.А., Теслер Г.С., Изд. Наукова думка, Киев 1984
[Ответить]
14 Апрель 2016, 11:2015 Сергей Валентинович:
Предлагаю сравнить эффективность вычисл. корня в десятичн. и двоичн. системе
Пример: квадратный корень из 9801
В десятичной системе
(компактная запись)
98`01.
98-1
97-3
94-5
89-7
82-9
73-11
62-13
49-15
34-17 ; 9 вычитаний
1701-181
1520-183
1337-185
1152-187
965-189
776-191
585-193
392-195
197-197 ; 9 вычитаний
000 ; стоп
Ответ: 99
или (197+1)/2 = 99
(18 вычитаний)
В двоичной системе
9801(10) = 10011001001001(2)
10`01`10`01`00`10`01.
-01 ; 1 вычитание
101
-101 ; 1 вычитание
0010 ; <1101 0 вычитаний
01001 ; <11001 0 вычитаний
100100 ; <110001 0 вычитаний
10010010
-1100001 ; 1 вычитание
11000101
-11000101 ; 1 вычитание
0000000 ; стоп
Ответ: 1100011
или (11000101+1)/10=1100011(2)=99(10)
(4 вычитания)
Кто-нибудь знает более быстрый алгоритм!?
[Ответить]
10 Февраль 2017, 14:0416 Михаил:
Почему эффективность метода оценивается исключительно по операции вычмтания (не самой медленной компьютерной операции)?
Но и здесь Вы делаете ошибку, останавливаясь на 9 шаге:
2. Из первой группы цифр слева вычитаем последовательно нечетные числа 1,3,5,7,\ldots,(2n-1) до тех пор, пока не получится отрицательное число.
[Ответить]
Сергей Валентинович Reply:
Апрель 27th, 2017 at 11:50
Здесь, видимо, вкралась опечатка. В оригинале текста п.2 изложен в следующей редакции:
{2. Из первой группы цифр слева вычитаем последовательно нечётные числа 1; 3; 5; 7;…(2n-1), одновременно подсчитывая число вычитаний n, до тех пор, пока остаток не станет меньше следующего вычитаемого. Запомним остаток, который получился – это A, и последнее вычитаемое – 2n-1. Если последняя разность равна 0, и справа от этой группы все цифры нули, то корень извлечён точно.} далее по тексту.
[Ответить]
Михаил Reply:
Май 2nd, 2017 at 12:18
Давайте вместе считать. Может, я чего-то недопонимаю, или считать не умею.
49-15 = 34
1) 98-1 = 97
Проверка: > 0 . Вычитаем дальше.
2) 97-3 = 94
Проверка: > 0 . Вычитаем дальше.
3) 94-5 = 89
Проверка: > 0 . Вычитаем дальше.
4) 89-7 = 82
Проверка: > 0 . Вычитаем дальше.
5) 82-9 = 73
Проверка: > 0 . Вычитаем дальше.
6) 73-11 = 62
Проверка: > 0 . Вычитаем дальше.
7) 62-13 = 49
Проверка: > 0 . Вычитаем дальше.
Проверка: > 0 . Вычитаем дальше.
9) 34-17 = 17
Проверка: > 0 . Вычитаем дальше.
10) 17 – 17 = 0
Проверка: = 0 . Вычитаем дальше.
11) 0 – 19 = -11
Проверка: < 0 . Останов. ("…пока остаток не станет меньше следующего вычитаемого")
Согласно алгоритму метода – мы должны сделать не 9, а 11 вычитаний.
Но, не это главное. Это просто для объективности.
Неприятно то, что после каждой операции вычитания (и двух операций сложения) приходится исп. функцию сравнения. А она, насколько я знаю, не реализуется аппаратно, а только программно. Поэтому, сравнение в этом методе – самое медленное действие.
[Ответить]
Михаил Reply:
Май 2nd, 2017 at 12:33
11) 0 – 19 = -19
[Ответить]
Сергей Валентинович Reply:
Май 2nd, 2017 at 15:25
1) По всей видимости, Михаил действительно чего-то не понимает (да и с умением считать трудности):
34-17=17 (9-е вычитание)
17 меньше 19 (следующее вычитаемое), значит, вычитать нельзя. Берём следующую группу и так далее…
А у Вас почему-то 17-17=0 ??? Я уж не говорю про п.11;
2) Операция сравнения над скалярными величинами (притом целыми), каковыми и являются все числа в приведённых примерах, осуществляются как-раз аппаратно, в регистрах процессора (так называемая сверхбыстрая оперативная память) за 1 или 2 такта (при тактовой-то частоте 3 000 000 000 Гц!);
3) Ваши рассуждения, Михаил, смахивают на попытку увести разговор в сторону. Вы знаете более быстрый алгоритм? Флаг Вам в руки. Опишите его. Интересующиеся математикой будут Вам благодарны.
[Ответить]
Михаил Reply:
Май 2nd, 2017 at 15:30
Все. Понял. Тогда – да 9 вычитаний. К тому же в 10 действии я ошибся.
[Ответить]
Михаил Reply:
Май 2nd, 2017 at 22:30
https://habrahabr.ru/post/128468/
[Ответить]
17 Михаил:
Так все-таки, почему 9 вычитаний, если (34-17 = 17 > 0 ) ?
Чтобы ответить на вопрос Сергея Валентиновича
“Кто-нибудь знает более быстрый алгоритм!?” мне кажется надо сначала правильно посчитать кол-во действий в приведенном примере.
[Ответить]
Сергей Валентинович Reply:
Апрель 27th, 2017 at 11:53
Смотрите предыдущий ответ (правильная редакция п.2)
[Ответить]
18 Михаил П.:
Вот еще пара книжек с описанием данного метода:
1. “Электронные клавишные вычислительные машины” Толстьев В.П.1974
2. Александр Григорьевич Бобров
Клавишные вычислительные машины: Конструкция и техн. обслуж. [Учебник для техникумов ж.-д. трансп.]/ А. Г. Бобров, В. Н. Думов, В. И. Кастерин
456 c. ил.:1 отд. л. схем 22 см.
М. Статистика 1978
[Ответить]
6 Апрель 2017, 11:1119 Luxy:
Кто-нибудь пробовал метод в системах счисления с основанием отличным от десяти, н-р, 2**32?
[Ответить]
28 Июнь 2017, 17:4720 Luxy:
Метод хорош для десятичных куркулятуров. В системе счисления с основанием 2 вычесть можно лишь единицу, соответственно метод превращается в набор битовых манипуляций, описанный на Википедии:
https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Binary_numeral_system_.28base_2.29
В системах счисления с основанием равным машинному слову, н-р, 2**32, придётся в худшем случае производить 2**32 – 1 вычитания на массивах цифр. Мне не кажется, что такое решение эффективно.
[Ответить]
28 Июнь 2017, 19:2221 Сергей Валентинович:
Последовательности нечётных чисел позволяют, оказывается, рассмотреть вопрос о вычислении корней более высоких степеней. Предлагаю любителям математики подумать над разработкой соответствующих алгоритмов, аналогичных вышеописанному методу вычисления квадратного корня.
Примеры последовательностей:
Квадраты
1=1^2
1+3=4=2^2 (2 слагаемых)
1+3+5=9=3^2 (3 слагаемых)
1+3+5+7=16=4^2 (4 слагаемых)
… и т.д.
Кубы
1=1^3
3+5=8=2^3 (2 слагаемых)
7+9+11=27=3^3 (3 слагаемых)
13+15+17+19=64=4^3 (4 слагаемых)
… и т.д.
Четвёртые степени
1=1^4
7+9=16=2^4 (2 слагаемых)
25+27+29=81=3^4 (3 слагаемых)
61+63+65+67=256=4^4 (4 слагаемых)
… и т.д.
Пятые степени
1=1^5
15+17=32=2^5 (2 слагаемых)
79+81+83=243=3^5 (3 слагаемых)
253+255+257+259=1024=4^5 (4 слагаемых)
… и т.д.
Первый член в каждой строке вычисляется по формуле (k^(n-1))-k+1,
где k – номер строки;
n – показатель степени.
[Ответить]
6 Июль 2017, 19:5122 Luxy:
Зачем я это сделал? Делать мне было нечего, а подходящая инфраструктура для дробления чисел была. http://pasted.co/a9e6ce21 Здесь можно видеть, что сложность предлагаемого алгоритма квадратичная (т.е. ~ O (n ** 2)), а сложность метода Ньютона, определяемая сложностью возведения в степень и сложностью деления, которые в данном случае определяется сложностью умножения Анатолия Карацубы, субквадратичная (т.е. ~ O (n ** lb (3))).
Вопрос о том, как зависит сложность предлагаемого алгоритма от принятого основания системы счисления, оставлю энтузиастам.
[Ответить]
16 Июль 2017, 5:1423 Сергей Валентинович:
28 декабря 2017 года
Уважаемая Елизавета Александровна!
Поздравляю Вас и всех читателей Вашего сайта с наступающим Новым годом!
В комментарии к статье об извлечении квадратного корня мной было предложено читателям Вашего сайта попробовать решить задачу вычисления корней произвольной степени, используя интересные свойства последовательностей нечётных чисел. В свою очередь, мне удалось разработать методику вычисления таких корней, аналогичную описанной на этой странице. Если заинтересуетесь, могу выслать Вам статью с описанием. С уважением, С.Савич
[Ответить]
28 Декабрь 2017, 11:1124 Дмитрий:
[Ответить]
Сергей Валентинович Reply:
Март 1st, 2018 at 13:41
Уважаемый Дмитрий!
Благодарю Вас за предоставленное описание алгоритма извлечения квадратного корня, используемого в советских калькуляторах серии “Искра”. Этот материал подтверждает мои предположения, высказанные в 14-м комментарии к этой статье. Боюсь, однако, что для многих читателей этого сайта, – я имею ввиду школьников и студентов, не знакомых с языком мнемокода процессора и логикой работы калькуляторов “Искра”, это описание будет малопонятным. В данной статье, а также в статье “О вычислении арифметических корней”, где говорится об обобщении алгоритма вычисления корней, я старался описать эти вопросы языком, понятным даже школьнику 5-6-го класса.
С уважением, С.В.Савич
[Ответить]