Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Корень квадратный

Автор: Mayk 7.6.2005, 08:10

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

Автор: Akina 7.6.2005, 08:37

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

Автор: dvs 7.6.2005, 08:38

http://algolist.manual.ru/maths/count_fast/intsqrt.php Думаю, это то, что тебе нужно...

Автор: Mayk 7.6.2005, 15:54

Цитата(Akina @ 7.6.2005, 08:37) как обычно - в столбик... какие проблемы-то? Ну, например, я не знаю как вычислять корень квадратный в столбик. Цитата(dvs15 @ 7.6.2005, 08:38) Думаю, это то, что тебе нужно... Точно! Спасибо! Ньютон воистину рулит!

Автор: SoWa 7.6.2005, 19:21

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

Автор: dvs 7.6.2005, 19:44

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

Автор: sergejzr 7.6.2005, 20:15

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

Автор: cardinal 7.6.2005, 21:03

Можно так сделать... Код    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).

Автор: Mayk 8.6.2005, 00:07

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

Автор: sergejzr 8.6.2005, 01:04

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

Автор: cardinal 8.6.2005, 02:14

Цитата(Mayk @ 7.6.2005, 22:07) Увы, медленно. Ну, Ньютон же есть Ньютон Мой способ пошел из одного рекурсивного способа нахождения корня (если интересно напишу), но в том способе можно использовать дробные числа. А тут пришлось немного его изменить, что привело к тому, что корень после поределенного числа итераций мы автоматом не получаем и приходится в случае перелета "спускаться" вниз см. Код    while (i*i > x)    {       i--;       c++;    } Что уже само собой тупо Но корень вычисляется

Автор: esperant0 8.6.2005, 07:46

Цитата(sergej @ 8.6.2005, 01:04) Потому что ньютоновский использует производную функцию Смысл Вашей фразы от меня ускользает. Что все методы которые используют производные быстро сходятся? Вроде бы нет.

Автор: Mayk 8.6.2005, 17:59

Цитата(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) )

Автор: sergejzr 8.6.2005, 18:18

Цитата(esperant0 @ 8.6.2005, 06:46) Смысл Вашей фразы от меня ускользает. Что все методы которые используют производные быстро сходятся? Вроде бы нет. А я не улавливаю смысл Вашей Разве я говорил, что все? Но в этом случае это так. Всё-таки нашёл наглядное обьяснение ) Это правда обобщённый Ньютон, но всё равно интересно http://upload.wikimedia.org/wikipedia/de/e/e0/NewtonIteration_Ani.gif

Автор: cardinal 8.6.2005, 20:19

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

Автор: cardinal 8.6.2005, 20:20

Блин, а формулы еще не отображаются Вот она:

Автор: esperant0 8.6.2005, 20:50

Цитата(Mayk @ 8.6.2005, 17:59) Ньютон: 0,09 Мой: 0,10 Кардинальный: 0,63 Я почти что Ньютон(ну и что, что при больших и сверхмалых X алгоритмы Ньютона и Кардинала дают одинаковй результат, быть может мой корень определен для X != {1,3,[262144;+oo) ) Проверил на числах порядка 10 в степени 40 Ваш метод 15 секунд Метод Ньютона 3 секунды. И в этом ничего удивительного так как метод Ньютона Рафсона имеет сходимость второго порялка, а методы аля Биссекция только первого.

Автор: III.nfo 9.6.2005, 20:06

Судя по всему, от Акина метода нет, так что: http://kvant.mirror0.mccme.ru/1987/03/staryj_algoritm.htm

Автор: dvs 9.6.2005, 23:20

III.nfo, обещанный плюс тебе... - просветил

Автор: cardinal 10.6.2005, 00:11

Я так и не понял: неужели никого так не потрясла та рекурсивная формула как меня?

Автор: esperant0 10.6.2005, 01:07

Цитата(cardinal @ 10.6.2005, 00:11) Я так и не понял: неужели никого так не потрясла та рекурсивная формула как меня? Последняя приведенная Вами формула, является ф-й полученной при использовании метода Ньютона Рафсона ака метод касательных. Метод потрясает. а формула его частный случай.

Автор: ChofCh 17.6.2005, 02:39

Что-то алгоритм нахождения корня в столбик так и не выложили... Исправим: Цитата Алгоритм извлечения корня квадратного Рассмотрим на примере sqrt(273529). Для нахождения произведем следующие действия: 1) десятичную запись числа 273529 разобьем на группы по две цифры, начиная справа; 2) для старшей группы, образующей число 27, подберем такую цифру, чтобы ее квадрат был наибольшим, но не превосходил числа 27; такой цифрой будет 5, ее запишем в качестве первой цифры ответа; 3) из старшей группы цифр вычтем найденный в предыдущем пункте квадрат первой цифры ответа и к полученной разности 27 – 25 = 2 припишем справа следующую группу цифр 35; получим число 235; 4) удвоив записанное в ответе число 5, припишем справа такую цифру , чтобы произведение полученного в результате числа на эту цифру было наибольшим, но не превосходило числа 235; такой цифрой будет 2 (ибо 102 x 2 = 204 < 235, но 103 x 3 = 309 > 235), ее и запишем в качестве второй цифры ответа; 5) из числа 235 вычтем найденное в предыдущем пункте произведение 204 и к остатку 31 снесем следующую группу цифр 29; получим число 3129; 6) удвоив записанное в ответе число 52, припишем справа такую цифру, чтобы произведение полученного в результате числа на эту цифру было наибольшим, но не превосходило числа 3129; такой цифрой будет 3 (ибо 1043 x 3 = 3129), ее и запишем в качестве третьей цифры ответа; 7) разность между снесенным числом 3129 и полученным в предыдущем пункте произведением равна 0, поэтому корень квадратный из числа 273529 извлекается нацело и равен записанному в ответе числу 523.

Автор: cardinal 17.6.2005, 02:48

Помоему III.nfo дал нужную ссылку...

Автор: Маг 4.7.2006, 13:40

Цитата(dvs @ 7.6.2005,  08:38) http://algolist.manual.ru/maths/count_fast/intsqrt.php Думаю, это то, что тебе нужно...  А ни кто не может перевести Сишный код в Алгоритмический или хотябы Делфи!!!   ПЛЗ!!! А то Си чуть-чуть не знаю.....

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)