Распечатать запись Распечатать запись

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

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

Об извлечении квадратного корня в столбик я уже писала здесь. Сейчас хочу вам предложить модификацию этого метода, которая мне кажется гораздо более простой и красивой. Предложил ее Сергей Валентинович Савич, который и написал мне об этом. Метод был изобретен для арифмометра — механической вычислительной машины, на которой в свое время считали, причем очень активно. Вот что пишет сам Сергей Валентинович: “Схема вычисления квадратных корней была придумана мной в конце 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/).

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

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

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

  2. 2 Марина:

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

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Марина, не очень понимаю, в чем проблема. Давайте рассмотрим пример. Возьмем, например, число 235,97. Разбиваем это число на группы цифр: 2^{\prime}35,97. Теперь из первой группы цифр вычитаем последовательные нечетные числа до тех пор, пока разность остается положительной. Ясно, что можем вычесть только число 1. Тем самым, первая цифра корня — это 1, а разность, которая получилась, тоже равна 1. Теперь к разности приписываем следующую группу цифр, получаем: 135 и продолжаем процесс дальше, как написано в п. 5.

    [Ответить]

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

    (10a+b)b=(10a+1)+(10a+3)+(10a+5)+…+(10a+(2b-1)). Гениально!
    А вот остальное, начиная с п.4, как-то очень сложно.

    [Ответить]

    Елизавета Александровна Калинина Reply:

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

    Вдруг подумала. А Вы исходный метод извлечения квадратного корня в столбик знаете? На всякий случай, он вот тут есть: http://hijos.ru/2010/12/22/izvlechenie-kvadratnogo-kornya-v-stolbik/

    [Ответить]

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

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

    [Ответить]

    Елизавета Александровна Калинина Reply:

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

    [Ответить]

  5. 5 Вячеслав:

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

    [Ответить]

    Елизавета Александровна Калинина Reply:

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

    [Ответить]

  6. 6 Вячеслав:

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

    [Ответить]

  7. 7 Вячеслав:

    Елизавета Александровна, посмотрел я в интернете метод последовательных приближений и метод Ньютона и удивился, как математики умеют морочить головы не математикам, вводя непонятные термины: “итерация”, “сходимость процесса итерации”, “последовательность операторов”, “рекуррентно”. При таком описании метода, он недоступен для понимания не только школьникам начальных классов, но и студентам технических ВУЗов вроде меня. Я представляю этот метод очень просто и доступно для всех. Вот пример извлечения кубического корня из 5: Предположим, что искомый корень равен 2, возведем 2 в куб = 8, т.е больше 5, значит искомый корень меньше 2, примем корень равным 1,5 и возведем 1,5 в куб = 3,725 меньше 5, примем корень равным 1,75 в кубе = 5,36;. Такие арифметические действия можно продолжать, пока не получим достаточную точность. В нашем случае мы остановились на результате 1,75. На калькуляторе (корень кубический из 5)= примерно 1,71. Складывается впечатление, что математики намеренно излагают теорию недоступным языком.

    [Ответить]

    Елизавета Александровна Калинина Reply:

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

    [Ответить]

  8. 8 Вячеслав:

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

    [Ответить]

    Елизавета Александровна Калинина Reply:

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

    [Ответить]

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

    А что делать, в случае извлечения корня из числа 119. С первой единицы вычтем единицу, тут все понятно, потом приписываем 19 и тут надо вычесть из этого числа 21. Но 19<21. Ноль вычитаний, значит, в ответе 10 целых, но что дальше делать, чтоб узнать, сколько десятых? Я приписываю к 19 два нуля и вычитаю из 1900 число 221, но ответ не сходится) При вычитании 211 тоже не сходится) Не хватает одного вычитания в обоих случаях)))

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Сначала нужно вычитать 201, так как уже есть число 20, и справа нужно к нему приписать 1. Получится 9 вычитаний, и останется 19.

    [Ответить]

    Елена Reply:

    Помогите разобраться с числом 17665209

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Делим цифры на группы: 17^{\prime}66^{\prime}52^{\prime}09. Вычитаем: 17-1-3-5-7=1, четыре вычитания, первая цифра корня 4. Далее к оставшейся 1 приписываем следующую группу цифр: 166 и снова вычитаем: 166-81-83=2, два вычитания, вторая цифра корня 2. К оставшемуся числу 2 приписываем следующую группу цифр: 252 и т.д.

    [Ответить]

  10. 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… .

    [Ответить]

  11. 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;
    }
    }

    [Ответить]

  12. 12 Димитрий:

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

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Спасибо. Это полезная информация.

    [Ответить]

  13. 13 Михаил П.:

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

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Спасибо!

    [Ответить]

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

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

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

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

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

    [Ответить]

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

Добавить изображение