Количество нечётных чисел в числе

[provincialka]

Simplar в сообщении #813555 писал(а):

почему, допустим, Тейлором медленнее?

Как именно? Нет, там медленнее. Да и трудно искать очередное приближение.
А через логарифмы совсем просто. Пусть $m^2\le n <(m+1)^2$. Прологарифмируйте эти неравенства и выведите формулу для $m$.

[Simplar]

Решительно не могу понять, как из неравенства вывести формулу. Это же неравенство.

[tatkuz1990]

Решение, думаю, такое:

если $n$ является квадратом числа, то

$m=\sqrt{n}$

Если нет, то - целое число из интервала

$\sqrt{n}-1<m<\sqrt{n}$

[Simplar]

tatkuz1990
Прочитайте выше, задачей было логарифмирование.

[provincialka]

Simplar в сообщении #813824 писал(а):

Решительно не могу понять, как из неравенства вывести формулу. Это же неравенство.

Про функцию"целая часть" слышали? Ее определение как раз содержит двойное неравенство.

[tatkuz1990]

Simplar, ничего подобного. Автор ни о каком логарифмировании не говорил. Ему нужно как можно проще решить.

[provincialka]

tatkuz1990 ему нужно как можно проще найти квадратный корень!
Хотя это, конечно, странно: сводить корень а логарифму...

-- 13.01.2014, 22:43 --

Кстати, Simplar и есть автор вопроса.

[Someone]

provincialka в сообщении #813544 писал(а):

Кстати, для извлечения корня из числа $2147483647$ методом Ньютона с точностью до целых достаточно 20 итераций (шагов). А вашим способом вы будете вычитать все 46340 раз (это и есть искомый корень).

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

Счёты.
Реализация такая. Разбиваем числа на грани по две цифры, начиная справа (с младших разрядов; если число не целое — начиная от десятичной запятой): $21'47'48'36'47$.

Вычитаем из старшей грани последовательные нечётные числа, начиная с $1$ (сколько получится): $21-1-3-5-7=5$.
Вычли $4$ числа, значит, старшая цифра корня — $4$.

К остатку $5$ сносим следующую грань (получаем $547$); к последнему вычтенному числу прибавляем $1$ ($7+1=8$). Вычитаем из $547$ последовательные нечётные числа, начиная с $8\cdot 10+1=81$: $547-81-83-85-87-89-91=31$.
Вычли $6$ чисел, значит, следующая цифра корня — $6$; получаем $46$.

К остатку $31$ сносим следующую грань (получаем $3148$); к последнему вычтенному числу прибавляем $1$ ($91+1=92$).
Вычитаем из $3148$ последовательные нечётные числа, начиная с $92\cdot 10+1=921$: $3148-921-923-925=379$.
Вычли $3$ числа, значит, следующая цифра корня — $3$; получаем $463$.

К остатку $379$ сносим следующую грань (получаем $37936$); к последнему вычтенному числу прибавляем $1$ ($925+1=926$).
Вычитаем из $37936$ последовательные нечётные числа, начиная с $926\cdot 10+1=9261$: $37936-9261-9263-9265-9267=880$.
Вычли $4$ числа, поэтому следующая цифра корня — $4$; получаем $4634$.

К остатку $880$ сносим последнюю грань (получаем $88047$); к последнему вычтенному числу прибавляем $1$ ($9267+1=9268$).
Так как $88047\leqslant 9268\cdot 10=92680$, то вычесть следующее число ($92680+1=92681$) нельзя, поэтому последняя цифра целой части корня равна $0$, а целая часть корня равна $46340$.

Количество вычитаний в данном случае равно $4+6+3+4+0=17$ и оказалось меньше числа итераций в методе Ньютона.

При желании можно продолжить вычисления и найти цифры дробной части. Например, чтобы найти цифру десятых, вычитаем из $8804700$ ($00$ сносится уже из дробной части заданного числа) последовательные нечётные числа, начиная с $92680\cdot 10+1=926801$.

P.S. Хорошо потренировавшись, эти вычисления на счётах можно проделать очень быстро.

[svv]

Можно представить, что в некотором (со)процессоре вычисление $e^x$ и $\ln x$ производится одной командой, а $\sqrt{x}$ нет. Тогда поможет формула

$$\sqrt{x}=e^{\frac{\ln x}{2}}$$

Someone
В старой-престарой «Детской энциклопедии» (том 3) описывался метод извлечения квадратного корня на счетах, но я никогда его внимательно не изучал, а сейчас этой книги у меня нет. Интересно, тот метод совпадает с Вашим хотя бы на уровне идеи? Надо найти и посмотреть.

[Someone]

Я с этим методом познакомился по книжке А.П.Доморяда "Математические игры и развлечения", когда учился в четвёртом классе (благо и счёты у меня тогда были). Многое в книге мне было непонятно, но этот метод я понял. Детская энциклопедия у меня была гораздо позже, но я не помню, был ли в ней этот метод.

[_Ivana]

(Оффтоп)

Как-то раз Фейнман читерски обыграл безвестного японца со счетами

[EtCetera]

Я в детстве пользовался таким способом:

Мне этот способ был известен как "вычисление квадратного корня с помощью граней", а сейчас его чаще всего называют (если судить по заметкам в интернете) "вычисление квадратного корня столбиком"). Метод основан на том, что

$$(10a+b)^2=100a^2+(10\cdot 2a+b)\cdot b.$$

Краткий алгоритм:

• Разбивают число на грани (по 2 цифры в каждой) влево и вправо от запятой. В самой левой ($g_0$) и самой правой гранях может оказаться по одной цифре, тогда их дополняют нулями.
• $q\gets 0$, $r\gets 0$, $k\gets 0$.
• Повторяют, пока хватает терпения, не кончились грани и $r\ne 0$:
  
  • $r\gets 100r+g_k$, $k\gets k+1$
  • $f(x)=(2q\cdot 10+x)\cdot x$
  • $a=\max\limits_{0\le x\le 9}f(x)$, $b=\arg\max\limits_{0\le x\le 9}f(x)$
  • $q\gets 10q+b$, $r\gets r-a$

По-видимому, это практически то же самое, что так подробно описал Someone.

[svv]

Описание из «Детской энциклопедии».

На счетах можно также извлекать корни квадратные из чисел. Так как сумма последовательных нечетных чисел (начиная с единицы) равна $1+3+5+...+(2n-3)+(2n-1)=n^2$, то вычисление $\sqrt N$ можно свести к проверке того, сумма скольких слагаемых вида $1,3,5...$ не будет превосходить числа $N$. При больших $N$ такая проверка утомительна, поэтому лучше последовательно определять отдельные цифры искомого корня. Для этого разбивают число на грани и из старшей грани вычитают $1,3,5...$ до тех пор, пока это возможно. Таким способом получают цифру старшего разряда искомого числа ($a$). К остатку присоединяют следующую грань и из полученного числа последовательно вычитают $20a+1, 20a+3, 20a+5$ и т.д. На рис. 9 показано извлечение этим способом квадратного корня из $74\;529$.

[provincialka]

EtCetera, нас в школе тоже учили этому методу, но это все же не то, что у Someone. В "нашем" методе нужно умножать, а главное - как-то подбирать следующую цифру. Здесь же просто вычитание.

[EtCetera]

provincialka

provincialka в сообщении #814112 писал(а):

как-то подбирать следующую цифру

Это довольно легко приноровиться делать. Однако числа для подбора быстро растут, поэтому на практике метод хорош лишь для быстрого нахождения $3\text{--}4$ значащих цифр, дальше становится слишком тоскливо, да и вероятность ошибки неуклонно возрастает.
Еще я хорошо помню, как тогда пытался найти аналогичный метод для нахождения кубических корней (и, вообще, корней других степеней). Меня очень расстроило, что ничего не вышло (да и выйти, по-видимому, не могло).