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

25 Апрель 2012, 0:03

Арифмометр Феликс

Об извлечении квадратного корня в столбик я уже писала здесь. Сейчас хочу вам предложить модификацию этого метода, которая мне кажется гораздо более простой и красивой. Предложил ее Сергей Валентинович Савич, который и написал мне об этом. Метод был изобретен для арифмометра — механической вычислительной машины, на которой в свое время считали, причем очень активно. Вот что пишет сам Сергей Валентинович: “Схема вычисления квадратных корней была придумана мной в конце 70-х г., и мне хотелось даже опубликовать её описание. Но время арифмометров закончилось, и этот алгоритм остался только в моей памяти. Теперь немного истории. В 1975–76 гг. я учился в Ленинградском топографическом техникуме, и у нас было очень много высокоточных измерений и расчётов. Калькуляторов и ПК тогда ещё не было, всё считали на арифмометрах, а значения функций приходилось брать из толстых 7 — 10-значных таблиц. Тогда у меня и появилась мысль “научить’’ арифмометр вычислять корни. Проштудировал кучу литературы, но ничего подходящего не нашёл. Методы последовательных приближений (дихотомии, Ньютона) отложил как неэкономичные для реализации на арифмометре. Когда я узнал о свойстве арифметической прогрессии нечётных чисел, то решил попробовать на его основе разработать алгоритм извлечения квадратного корня. Наибольшую трудность представляло то, что я никак не мог сообразить, что делать с остатком от вычитания квадрата первой цифры из аргумента. Интуитивно было понятно, что решение где-то рядом. В общем, вертел этот остаток и так, и сяк, и в конечном итоге набрёл на правильное решение.” Как уже говорилось, идея очень красивая. В основе метода лежит следующее свойство суммы $n$ первых нечетных чисел:

$1+3+5+\ldots+(2n-1)=n^2 .$

Доказать это легко, если вспомнить формулу суммы $n$ первых членов арифметической прогрессии. Еще понадобится следующая идея, которая основывается на этом свойстве. Если требуется приписать к какому-то числу $a$ справа еще одну цифру $b$ , а потом умножить полученное число на эту же цифру, то сделать это можно сложением $b$ последовательных нечетных чисел:

$(10a+b)\cdot b=(10a+1)+(10a+3)+(10a+5)+\ldots+(10a+(2b-1)) .$

Действительно, давайте раскроем скобки во всех $b$ слагаемых справа и их перегруппируем:

$(10a+1)+(10a+3)+(10a+5)+\ldots+(10a+(2b-1))=$

$=10ab+(1+3+5+\ldots+(2b-1))=10ab+b^2=(10a+b)b .$

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

1. Сначала мы точно так же, как было описано, делим число, из которого будем извлекать квадратный корень, на группы цифр, по две цифры в каждой группе. Целую часть числа (то, что стоит слева от десятичной запятой) разбиваем на группы по две цифры справа налево, а дробную часть (начиная от первой цифры справа от десятичной запятой) — слева направо. Пример давайте рассмотрим тот же, что уже был просчитан. Можно будет сравнить, насколько проще получается алгоритм. Возьмем число $56789,321$ . Итак, разбиваем цифры этого числа на пары $5^{\prime}67^{\prime}89.32^{\prime}1$ .

2. Из первой группы цифр слева вычитаем последовательно нечетные числа $1,3,5,7,\ldots,(2n-1)$ до тех пор, пока не получится отрицательное число. Запомним последнюю положительную разность, которая получилась — $A$ , и то число, которое при этом вычитали — $2n-1$ . Если последняя разность равна $0$ , то корень извлечен точно. В нашем примере можно вычесть два нечетных числа: $5-1=4,4-3=1 .$ Это означает, что первая цифра корня — $2$ , остаток $A = 1$ , вычитали при его получении число $2n - 1 = 3$ . Здесь $n$ — порядковый номер последнего нечётного числа. Далее, к последнему вычитаемому прибавим $1$ . В нашем случае к $3$ прибавляем $1$ , получаем число $y = 4$ .

3. Теперь к остатку $A$ справа припишем следующую группу $C$ из двух цифр подкоренного числа, получим число $100A + C$ . В нашем примере, приписывая следующие две цифры, получим число $167$ . Из числа $100A + C$ снова начинаем вычитать последовательно нечётные числа, предварительно сдвинув вычитаемое на один разряд вправо. Эти нечётные числа формируются следующим образом: первое число, которое будем вычитать, будет число $y$ , к которому справа припишем цифру $1$ , т.е. $10y + 1$ , затем $10y + 3; 10y + 5;\ldots, 10y + (2n - 1)$ . Делаем вычитания до тех пор, пока остаток не станет меньше вычитаемого. И снова запомним остаток (это будет $A$ ), последнее вычитаемое $10y + (2n - 1)$ и количество вычитаний $n$ . Если же получили разность $0$ , и оставшиеся цифры в подкоренном числе — нули, то корень извлечён точно. В нашем примере делаем следующие действия: $167- 41 = 126; 126 - 43 = 83; 83 - 45 = 38; 38 < 47$ , поэтому вычитания прекращаем. Было выполнено три вычитания, значит, следующая цифра корня — $3$ .

4. Если нам нужно посчитать следующие цифры корня, то возьмём снова ту последнюю положительную разность, которую мы запомнили в п. 3, как $A$ и последнее вычитаемое $10y + (2n - 1)$ , увеличенное на $1$ — как $y$ . Для разбираемого нами примера получим $A = 38, y = 45 + 1 = 46$ . И повторяем алгоритм, начиная с шага 3. В том случае, если первое вычитаемое $10y + 1$ больше, чем $100A + C$ , то следующая цифра корня — $0$ , так как ни одного вычитания сделать нельзя. В этом случае принимаем $100A + C$ за $A$ , $10y$ за $y$ , и выполняем действия, начиная с шага 3. Если же корень вычислен точно (последняя разность равна $0$ и оставшиеся цифры справа в подкоренном числе — нули) или корень вычислен с требуемой точностью, то завершаем процесс. Далее я не буду описывать все шаги, просто приведу то, что получается, если все вычисления записать в столбик. Пояснения — в фигурных скобках.

$\sqrt{56789,321} = 238,305$ {точность — 6 значащих цифр, 21 вычитание} Как видно из приведённого описания, этот способ легко может быть формализован и записан в виде программного кода для ЭВМ, причём время выполнения этой программы сопоставимо с временем выполнения операции деления. Сергей Валентинович предложил также некоторые изменения, упрощающие процесс вычислений и позволяющие повысить точность. Так, можно заметить, что после каждого цикла вычитаний цифры последнего вычитаемого, увеличенного на $1$ (т.е. $y$ , по нашему соглашению), представляют собой цифры удвоенного значения корня. Поэтому можно не подсчитывать число вычитаний, а просто разделить $y$ , полученное из последнего вычитаемого, на $2$ . Положение запятой можно определить, руководствуясь следующим правилом: количество цифр целой части результата равно количеству пар цифр в целой части аргумента, каждой паре цифр аргумента соответствует одна цифра результата.

Примеры:

аргумент 61 71 , 67 36 (1)

результат 7 8 , 5 6

аргумент 0 , 00 78 93 10 (2)

результат 0 , 0 8 8 8 4 3 1 2

Кроме этого, вдобавок можно получить ещё примерно столько же значащих цифр, сколько уже было получено, простым делением последнего остатка с приписанными неиспользованными парами цифр на последнее вычитаемое, увеличенное на $1$ . Для описанного нами примера имеем: $47975 / 476610 = 0,10065881...;$ Здесь шесть цифр $100659$ являются, с учётом округления последней, верными. Отсюда получаем конечный результат с точностью 12 дес. знаков (!): $\sqrt{56789,321} = 238,305100659.$ Конечно, вычислять вручную с такой точностью значения корней вряд ли целесообразно, но данное правило позволяет для нахождения корней с точностью 5-6 знаков ограничиться вычислением с помощью вычитания нечётных чисел только 3-х цифр.

Ни Сергей Валентинович, ни я нигде не встречали описание данного метода. Если кто-либо из вас где-то об этом читал, напишите, пожалуйста. Заранее большое спасибо.

Подробный пример извлечения квадратного корня на арифмометре можно увидеть в статье Савича С.В. здесь (www.twirpx.com/file/1096076/).

Теги: алгебра, средняя и старшая школа
Рубрика: Статьи по математике | Отзывы (RSS) | Трекбек

Комментариев: 40

1 Извлечение квадратного корня в столбик | Математика, которая мне нравится:

[...] P.S. Красивую модификацию описанного метода извлечения квадратного корня, которую предложил С.В. Савич, можно найти здесь: http://hijos.ru/2012/04/25/krasivaya-modifikaciya-metoda-izvlecheniya-kvadratnogo-kornya/ [...]
25 Апрель 2012, 12:41
2 Марина:

Решила попробовать этот метод и сразу наткнулась на вопрос. Предположим, что необходимо извлечь корень из числа первая цифра которого чётная. Тогда после первых преобразований выражение 2n-1 будет равно нечетному числу => Тогда первая цифра корня, то есть B=.,5? На этом я и закончила рассмотрение данного метода. А хотелось бы докопаться до истины=)

[Ответить]
Елизавета Александровна Калинина Reply:
Сентябрь 7th, 2012 at 12:35
Марина, не очень понимаю, в чем проблема. Давайте рассмотрим пример. Возьмем, например, число
$235,97$

. Разбиваем это число на группы цифр:
$2^{\prime}35,97$

. Теперь из первой группы цифр вычитаем последовательные нечетные числа до тех пор, пока разность остается положительной. Ясно, что можем вычесть только число
$1$

. Тем самым, первая цифра корня — это
$1$

, а разность, которая получилась, тоже равна
$1$

. Теперь к разности приписываем следующую группу цифр, получаем:
$135$

и продолжаем процесс дальше, как написано в п. 5.

[Ответить]
7 Сентябрь 2012, 11:32
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/

[Ответить]
9 Сентябрь 2012, 17:03
4 Корнеев В. Ф.:

А почему адрес http://hijos.ru/2012/04/25/krasivaya-modifikaciya-metoda-izvlecheniya-kvadratnogo-kornya/, указанный в первом комментарии, приводит опять сюда, а не на стр. С.В. Савича?

[Ответить]
Елизавета Александровна Калинина Reply:
Сентябрь 9th, 2012 at 17:40
Не поняла, это автоматическая ссылка из статьи об извлечении квадратного корня в столбик именно на эту статью. К сожалению, странички у С.В. Савича, насколько знаю, нет. Он прислал мне этот метод по электронной почте.

[Ответить]
9 Сентябрь 2012, 17:15
5 Вячеслав:

Елизавета Александровна, метод описанный Вами я знал давно. Вероятно он был в старых школьных учебниках и возможно есть в современных. А обоснование я ранее не встречал. Второй метод С.В.Савича для меня нов, но он мне показался более сложным и трудоёмким. Оба метода забываются, если ими не пользоваться регулярно. Недавно мне понадобилось извлекать корни, но под рукой не было ни калькулятора, ни таблиц, ни логарифмической линейки и я никак не мог вспомнить метод извлечения. Тогда мне пришло на ум извлекать корни методом, который я назвал методом последовательных приближений(МПП). Математики его называют каким-то научным термином. Этот метод очень прост, не требует ничего запоминать. Достаточно лишь знать простые арифметические действия.

[Ответить]
Елизавета Александровна Калинина Reply:
Февраль 18th, 2013 at 17:00
Вы правы, хорошо работает также метод Ньютона. Здесь интересно то, что этот метод был придуман для арифмометра, вычисления все очень простые. Кроме того, в методе последовательных приближений, в методе Ньютона мы не знаем, сколько верных цифр коня вычислено, сколько шагов потребуется, скажем, для нахождения 10 цифр корня. А здесь за один шаг находится одна цифра.

[Ответить]
18 Февраль 2013, 16:07
6 Вячеслав:

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

[Ответить]
18 Февраль 2013, 16:14
7 Вячеслав:

Елизавета Александровна, посмотрел я в интернете метод последовательных приближений и метод Ньютона и удивился, как математики умеют морочить головы не математикам, вводя непонятные термины: “итерация”, “сходимость процесса итерации”, “последовательность операторов”, “рекуррентно”. При таком описании метода, он недоступен для понимания не только школьникам начальных классов, но и студентам технических ВУЗов вроде меня. Я представляю этот метод очень просто и доступно для всех. Вот пример извлечения кубического корня из 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
Вячеслав, то, что Вы предлагаете, это просто подбор. Это не метод последовательных приближений и не метод Ньютона. А так, для каждого метода хочется выяснить условия применимости и скорость сходимости. Отсюда сложности.

[Ответить]
19 Февраль 2013, 14:31
8 Вячеслав:

Елизавета Александровна, для глубокого изучения математики можно излагать теорию с использованием специальных терминов. Для начального обучения это недопустимо. Для моего метода более соответствует определение МПП, чем просто подбор, и для приведенного примера и других подобных задач нет необходимости выяснять условия применяемости и скорость сходимости. Отсюда необоснованные сложности.

[Ответить]
Елизавета Александровна Калинина Reply:
Февраль 19th, 2013 at 21:08
Вячеслав, да, Вы правы, так в школе и рассказывают именно о методе подбора без всяких изысков. Так что для начального уровня ничего такого и нет.

[Ответить]
19 Февраль 2013, 18:24
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
Делим цифры на группы:
$17^{\prime}66^{\prime}52^{\prime}09$

. Вычитаем:
$17-1-3-5-7=1$

, четыре вычитания, первая цифра корня
$4$

. Далее к оставшейся
$1$

приписываем следующую группу цифр:
$166$

и снова вычитаем:
$166-81-83=2$

, два вычитания, вторая цифра корня
$2$

. К оставшемуся числу
$2$

приписываем следующую группу цифр:
$252$

и т.д.

[Ответить]
13 Февраль 2014, 14:32
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:26
11 Андрей:

Действительно данный метод легко реализуется программно, при этом он достаточно эффективен при вычислении больших чисел. На 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:25
12 Димитрий:

Здравствуйте! Обычный метод извлечения корня столбиком я встречал в старых учебниках и справочниках ( кажется у Выгодского).
Так называемый метод Савича был приведён в руководству арифмометра “Быстрица”. Если не ошибаюсь

[Ответить]
Елизавета Александровна Калинина Reply:
Апрель 7th, 2016 at 22:16
Спасибо. Это полезная информация.

[Ответить]
3 Апрель 2016, 19:54
13 Михаил П.:

Данный метод и еще один (более совершенный) алгоритм извлечения квадратного корня на основе свойства арифм.прогрессии нечетных чисел подробно описан в учебном пособии для машиностроительных ВУЗов
Рязанкин В. Н., Евстигнеев Г. П.. Тресвятский Н. Н., Вычислительные машины, ч. 1, М., 1957. Книга – не редкая, практически любой сайт, посвященный выч.счетным машинам имеет ссылку на эту книгу. В предисловии книги указано, что 3-я глава книги, описывающая методы извл.квадр.корня написана конкретно Рязанкиным В.Н.

[Ответить]
Елизавета Александровна Калинина Reply:
Апрель 12th, 2016 at 21:30
Спасибо!

[Ответить]
11 Апрель 2016, 17:44
14 Сергей Валентинович:

Уважаемая Елизавета Александровна!

Увидел комментарий Димитрия и решил внести ясность в обсуждение “так называемого метода Савича”. В одном из первых своих писем Вам я писал, что этот алгоритм, возможно используется в виде каких-то модификаций в калькуляторах и математических сопроцессорах. Разбираясь в способах вычисления элементарных функций, я перечитал и изучил большое
количество самой разнообразной и весьма серъёзной литературы по этим вопросам (Некоторые из этих книг перечислены в списке литературы), и, конечно же, не стал бы публиковать от своего имени этот метод, если бы он был там описан. Справедливости ради надо отметить, что описанный мной алгоритм, в общем, тривиален, и было бы весьма странным и непонятным, если бы его не изобрели раньше, учитывая историю развития науки. В частности, читая недавно старинные книги по истории математики, я встречал упоминание о школе пифагорейцев, где уже тогда, в древние времена, обращалось внимание на свойство суммы нечётных чисел. Так что открытие мной этого метода имеет сугубо личный характер и может служить лишь иллюстрацией множественности путей поэнания свойств окружающего мира. Скажу только, что для меня лично поиски решения этой проблемы имеют ещё и яркую эмоциональную окраску, что даёт стимул к дальнейшим исследованиям.
Что касается арифмометра “Быстрица”, то я не поленился, нашёл оригинальное описание и инструкцию “www.alple.net/arif-ru/books.htm#bystritsa-2″. В этом описании нет ни слова об извлечении корня.
По поводу замечания Михаила П. могу добавить, что совсем недавно “раскопал” (интернет даёт такую возможность) интереснейшее издание – пятитомник Энциклопедия элементарной математики, 1951 г., и там тоже приводится описание похожей методики извлечения квадратного корня, правда, чуть упрощённой – для целых чисел, причём автор этой главы – всем известный и уважаемый учёный, педагог Владимир Модестович Брадис. Чтение таких книг – настоящее наслаждение. Как жаль, что эта энциклопедия не встретилась мне раньше.
“Более совершенный” метод, описанный Рязанкиным В.Н., на самом деле использует разность прогрессии 10, что в 5 раз больше 2, и поэтому больше подходит для расчётов в десятичной системе. Других преимуществ у него нет. Метод, описанный мной, оптимизирован для вычислений в двоичной системе и может быть реализован аппаратурно в процессорах.
В заключение хочу сказать, что целью публикации метода вычисления квадратного корня было познакомить интересующихся математикой с малоизвестным, незаслуженно забытым, и в то же время изящным и очень быстрым алгоритмом. Считаю эту задачу выполненной.
С уважением, С.В.Савич

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

Вычисление элементарных функций на ЭВМ. Благовещенский Ю.В., Теслер Г.С. Изд. Технiка, Киев 1977.
Принципы построения электронных клавишных вычислительных машин. Мараховский В.Б., Каневский Е.А.
Аппаратурная реализация элементарных функций в ЦВМ. Байков В.Д., Смолов В.Б.
О вычислениях при помощи арифмометра. Кочанов Н.С., Изд. Знание, Москва, 1967
Вычисление функций на ЭВМ. Попов Б.А., Теслер Г.С., Изд. Наукова думка, Киев 1984

[Ответить]
14 Апрель 2016, 11:20
15 Сергей Валентинович:

Предлагаю сравнить эффективность вычисл. корня в десятичн. и двоичн. системе
Пример: квадратный корень из 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:04
16 Михаил:

Почему эффективность метода оценивается исключительно по операции вычмтания (не самой медленной компьютерной операции)?
Но и здесь Вы делаете ошибку, останавливаясь на 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
Давайте вместе считать. Может, я чего-то недопонимаю, или считать не умею.
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 . Вычитаем дальше.
49-15 = 34
Проверка: > 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/

[Ответить]
3 Апрель 2017, 15:29
17 Михаил:

Так все-таки, почему 9 вычитаний, если (34-17 = 17 > 0 ) ?
Чтобы ответить на вопрос Сергея Валентиновича
“Кто-нибудь знает более быстрый алгоритм!?” мне кажется надо сначала правильно посчитать кол-во действий в приведенном примере.

[Ответить]
Сергей Валентинович Reply:
Апрель 27th, 2017 at 11:53
Смотрите предыдущий ответ (правильная редакция п.2)

[Ответить]
5 Апрель 2017, 0:18
18 Михаил П.:

Вот еще пара книжек с описанием данного метода:
1. “Электронные клавишные вычислительные машины” Толстьев В.П.1974
2. Александр Григорьевич Бобров
Клавишные вычислительные машины: Конструкция и техн. обслуж. [Учебник для техникумов ж.-д. трансп.]/ А. Г. Бобров, В. Н. Думов, В. И. Кастерин
456 c. ил.:1 отд. л. схем 22 см.
М. Статистика 1978

[Ответить]
6 Апрель 2017, 11:11
19 Luxy:

Кто-нибудь пробовал метод в системах счисления с основанием отличным от десяти, н-р, 2**32?

[Ответить]
28 Июнь 2017, 17:47
20 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:22
21 Сергей Валентинович:

Последовательности нечётных чисел позволяют, оказывается, рассмотреть вопрос о вычислении корней более высоких степеней. Предлагаю любителям математики подумать над разработкой соответствующих алгоритмов, аналогичных вышеописанному методу вычисления квадратного корня.
Примеры последовательностей:
Квадраты
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:51
22 Luxy:

Зачем я это сделал? Делать мне было нечего, а подходящая инфраструктура для дробления чисел была. http://pasted.co/a9e6ce21 Здесь можно видеть, что сложность предлагаемого алгоритма квадратичная (т.е. ~ O (n ** 2)), а сложность метода Ньютона, определяемая сложностью возведения в степень и сложностью деления, которые в данном случае определяется сложностью умножения Анатолия Карацубы, субквадратичная (т.е. ~ O (n ** lb (3))).
Вопрос о том, как зависит сложность предлагаемого алгоритма от принятого основания системы счисления, оставлю энтузиастам.

[Ответить]
16 Июль 2017, 5:14

Математика, которая мне нравится

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

Комментариев: 40

1 Извлечение квадратного корня в столбик | Математика, которая мне нравится:

2 Марина:

3 Корнеев В. Ф.:

4 Корнеев В. Ф.:

5 Вячеслав:

6 Вячеслав:

7 Вячеслав:

8 Вячеслав:

9 Вопиющий в пустыне:

10 Вячеслав:

11 Андрей:

12 Димитрий:

13 Михаил П.:

14 Сергей Валентинович:

15 Сергей Валентинович:

16 Михаил:

17 Михаил:

18 Михаил П.:

19 Luxy:

20 Luxy:

21 Сергей Валентинович:

22 Luxy:

Оставьте свой отзыв

Навигация по сайту

Разделы

Новые комментарии

Хороший книжный магазин

Подписка на обновления сайта

Твиттер