Кто-нибудь подскажет алгоритм извлечения квадратного корня из целочисленного числа?
Все расчеты надо проводить без использования дробных чисел.

как обычно - в столбик... какие проблемы-то?

http://algolist.manual.ru/maths/count_fast/intsqrt.php

Думаю, это то, что тебе нужно...

Цитата(Akina @ 7.6.2005, 08:37)

как обычно - в столбик... какие проблемы-то?

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

Цитата(dvs15 @ 7.6.2005, 08:38)

Думаю, это то, что тебе нужно...

Точно! Спасибо! Ньютон воистину рулит!

Тогда в тему, как его вычислять столбиком?

Akina и я не знаю, как в столбик его вычислять... Рассказывай, с нас "+" и добавим материал в ФАК.

Мне тоже интересно
разве что начиная с единицы столбиком числа перемножать и проверять

Можно так сделать...

Код

int x = 31366;   // число    int i = 1;            // его корень     int c = 0;           // кол-во операций        while (i*i < x)    {       i = (i+2/i)/2+i;       c++;    }    while (i*i > x)    {       i--;       c++;    }

Это такая мысля на быструю руку просто. Можно сравнить кол-во операций в решении Ньютона с этим решением (значение c).

Увы, медленно. Лучше сравнить время нахождения корня от 1 до некоего max, так как кол-во операций все же не так важно.
max=553600
Ньютоновский:0.11 сек
Кардинальный(?):0.64 сек

Это сообщение отредактировал(а) Mayk - 8.6.2005, 00:08

Потому что ньютоновский использует производную функцию

Цитата(Mayk @ 7.6.2005, 22:07)

Увы, медленно.

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

Код

while (i*i > x)    {       i--;       c++;    }

Что уже само собой тупо Но корень вычисляется

Цитата(sergej @ 8.6.2005, 01:04)

Потому что ньютоновский использует производную функцию

Смысл Вашей фразы от меня ускользает.
Что все методы которые используют производные быстро сходятся? Вроде бы нет.

Цитата(cardinal @ 8.6.2005, 02:14)

Мой способ пошел из одного рекурсивного способа нахождения корня (если интересно напишу)

Я весь внимание.

Кстати, я нашел еще один способ нахождения корня. Внимательный читатель заметит здесь идеи бинарного поиска. Получается довольно быстро.
Правда дает округление в любую сторону. Как следствие, график от этой функции не является возрастающем на всех допустимых X.(А при больших X функция вообще не верна - overflow). Особенно радует sq(1) и sq(3). Зато при остальных результат верен с учетом рандомного округления :-)

Код

unsigned sq(int n) {     unsigned long sq2;     register unsigned sq = 0;     register unsigned l = 0;     register unsigned u = n / 2;              while (l < u) {         sq = (l + u) / 2;         sq2 = sq * sq; //      printf("n=%d\t sq2=%d\t sq=%d\n",n,sq2,sq);         if (sq2 == n)             break;         if (sq2 < n)             l = sq + 1;         else             u = sq;     }     return sq; }

Результат(для того же max)
Ньютон: 0,09
Мой: 0,10
Кардинальный: 0,63
Я почти что Ньютон(ну и что, что при больших и сверхмалых X алгоритмы Ньютона и Кардинала дают одинаковй результат, быть может мой корень определен для X != {1,3,[262144;+oo) )

Цитата(esperant0 @ 8.6.2005, 06:46)

Смысл Вашей фразы от меня ускользает. Что все методы которые используют производные быстро сходятся? Вроде бы нет.

А я не улавливаю смысл Вашей Разве я говорил, что все? Но в этом случае это так.

Всё-таки нашёл наглядное обьяснение ) Это правда обобщённый Ньютон, но всё равно интересно

Есть вот такая формула:
[formula]a_{k+1}=\frac{1}{2}(a_{k}+\frac{b}{a_{k}}), k=0,1,2,..., a_{0}=1[/formula]
Она как понимаешь рекурсивная. После определенного кол-ва итераций ты получаешь sqrt(b) с такой то точностью. Чем дольше считаешь, тем точнее будет. То что эта формула сводится к корню от b можно математически доказать...