не обязательно извлекать...

нужно только знать, извлекается ли целый квадратный корень из целого неотрицательного числа...

срочно...

-------------------------------------------------------------------------------------------------

Дополнение:

вообщем проблема вот в чем:

Код

#include <iostream.h> #include <math.h> void main() {     unsigned int number;     number = 21040569;//число, корень из него равен 4587     cout << number << ":";//выводим число 21040569     cout << sqrt((double)number) << ":";//выводим корень квадратный этого числа 4587     cout << (int)sqrt((double)number) << "\n";//отбрасываем дробную часть числа 4587 //теперь внимание: сюрприз!     number = 21040570;//число, корень из него равен 4587,0001090037..бла-бла-бла     cout << number << ":";//выводим число 21040570     cout << sqrt((double)number) << ":";//выводим корень квадратный этого числа 4587!!!!!!!     cout << (int)sqrt((double)number) << "\n";//отбрасываем дробную часть числа 4587 }

вывод:

Код

21040569:4587:4587 21040570:4587:4587 Press any key to continue

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

может кто что подскажет....

Это сообщение отредактировал(а) MOP - 31.8.2005, 17:56

Ну если число относительно мелкое(допустим, в районе миллиона), то можно разложить на множители через заране построенную таблицу простых чисел.
Очевидно, что если корень извлекается, то при разложении получится что-то типа a*a*b*b*b*b*c*c(a,b,c - простые), а корень будет a*b*b*c.
Ещё у нас где-то была у нас темка по извлечению корней из целых чисел... Вот она: http://forum.vingrad.ru/index.php?showtopic=54722. Посмотри, может там что полезное найдешь.

объясню, зачем мне это надо...

решал я одну задачку :
http://acm.timus.ru/problem.aspx?space=1&num=1209

по ходу решил её (на листочке). все правильно, ошибок нет, если решать на калькуляторе.

в общем мое решение свелось к тому, что нужно определить является ли арифметический квадратный корень из (8*k-7) целым числом. если целое, то на k-той позиции - единица, если дробное - ноль. (если кому интересно решение - пишите - выложу). на листочке - все правильно... но когда пытаюсь решить с помощью С++ - тонет на больших числах... вот код:

Код

#include <iostream.h> #include <math.h> void main() {     unsigned short length;     unsigned int input;     char i;     cin >> length;     for ( i = 0; i < length; i++ )     {         cin >> input;         if ( (int)(sqrt((double)(8*input - 7))) == sqrt((double)(8*input - 7)) )             cout << '1';         else             cout << '0';     } }

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

задачка интересная... но кроме написания специализированной функции для вычисления корней из целых чисел в голову ничего не приходит
что-нибудь вроде этого:

Код

bool IsSquare(unsigned int x) {   usnigned int RootLow=0;   unsigned int RootDelta=x/2;   while(RootDelta>0)   {     unsigned int temp=RootLow+RootDelta;     if(temp*temp<=x)       RootLow=temp;     RootDelta/=2;   }   return (x==SquareLow); }

сразу говорю - не проверял
идея такая: ищем корень двоичным поиском
RootLow - левая граница отрезка
RootDelta - половина длины отрезка
на каждом шагу сравниваем RootLow+RootDelta и sqrt(x)
если меньше - выбираем левый полуотрезок, больше - правый
чтобы выбрать левый - просто делим RootDelta на 2
правый - добавляем RootDelta к RootLow, и опять делим RootDelta пополам
дальше - пользуемся тем что, y<sqrt(x) - то же самое, что y*y<x
таким образом подходим все ближе к корню из x снизу
превысить его мы не можем
если в конце дошли до него - значит, корень целый, если нет - значит нет...

по идее, долго функция работать не должна - максимум 31 проход по циклу
кроме того, за верхнюю оценку корня из x здесь взято само x
можно смело брать x/2, что уменьшит количество проходов на 1
или вообще в начале проверить x>2^16 и в этом случае за оценку взять x/2^8, что уменьшит количество проходов на 8, т.е. на четверть - тоже неплохо...
конечно, можно было городить что-то более сложное, чтобы получить более хорошую оценку, но не факт, что оно стоит того, т.к. тело цикла вычислительно очень простое, а предварительная проверка должна занимать меньше времени, чем она экономит, чтобы было выгодно ее делать...
Добавлено @ 00:20

Цитата

8*input - 7

а вот это, кстати, - опасно
если input будет 2^30, число благополучно выйдет за пределы unsigned int
насколько я понял, изначально в задаче нужно определить, можно ли представить число k в виде n*(n+1)/2
тогда лучше такую задачу и решать, чтобы было поменьше мороки с опасностью выхода за границы диапазона
т.к. функция n*(n+1)/2 такая же монотонная, как и корень, предложенную функцию можно переделать для нее...
(только надо будет осторожно вычислять n*(n+1)/2 - сначала найти среди n и n+1 четное число, поделить его на 2, а уже потом перемножать, опять же на тот случай, если мы подойдем слишком близко к границе диапазона)

ага... вот я сам себя и поймал...
если x будет большим, то на первой же итерации произойдет нечто ужасное:
temp будет равен x/2
при вычислении его квадрата произойдет переполнение...
так что более точная оценка снизу все-таки нужна
сделать ее можно вообще по-простому:
считаем количество значащих разрядов x - пусть это будет m
значит x<2^(m+1)
значит хорошей оценкой сверху будет (int)sqrt(2^(m+1))
можно, конечно, считать эти оценки в процессе, но лучше посчитать их на обычном калькуляторе и занести в таблицу, чтобы не терять времени на вычисления (а то ведь при нечетных (m+1) корень придется действительно вычислять)...
Добавлено @ 00:33
P.S.ну и наследил я тут

Цитата(MOP @ 1.9.2005, 03:09)

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

Бери Ньютона, он рулит. http://algolist.manual.ru/maths/count_fast/intsqrt.php все лонги замени на long long'и или даже на long double. Или возьми BigInteger'ы (реализация там же есть).

Цитата(MOP @ 1.9.2005, 03:09)

(если кому интересно решение - пишите - выложу).

угу, интересно.

ps. Лучше использовать логические операции. То есть примерно так:

char pow10[32];
bitArray[0]= 11010010;
bitArray[1]= 00100010;

Ну и так далее.
А потом логическое И. И всё тип-топ.

Это сообщение отредактировал(а) Mayk - 1.9.2005, 06:01

Млин, я идиот. 2**31 битов это 2**28 байт, что офигенно много.
Ладно, где наши не пропадали. Решение в лоб:

Код

int digit(unsigned idx){     unsigned pow=1;     while(idx > 0)          idx -= pow++;         return (idx == 0) ? '1' : '0'; }

довольно быстро находит решение для 0x7FFFFFFF.
Если можно позволить себе хранение 131072 интегеров(а именно столько единиц в последовательности длинной 2**31), то вся задача сводится к бинарному поиску индекса по массиву индексов. Если же такая роскошь не позволительна, то можно использовать как массив, так и лобовой способ и способ с sqrt.

Сейчас бум сравнивать их по времени: находим 0x7ffffff цифр.
При решении с бинарным поиском по массиву затрачивается менее 30 секунд(26-30)
При решении с double'ным sqrt менее 40(34-40) (разброс сильный, так как в фоне много программ висят ресурсоемких). Но тут у sqrt много преобразований int<->double происходит. Счас будем избавляться

Цитата(maxim1000 @ 31.8.2005, 23:14)

насколько я понял, изначально в задаче нужно определить, можно ли представить число k в виде n*(n+1)/2 тогда лучше такую задачу и решать, чтобы было поменьше мороки с опасностью выхода за границы диапазона

на сколько я понял, то почти так...
т.е.
k=n*(n+1)/2 - можно и так (а можно и так:)

Код

k=n*(n+1)/2+1 => n*n + n -2(k-1) = 0 k=const 0<k<(2<<31) k - целые 0<=n n - целые

k - интерпритирует порядковый номер числа(исчисление с единицы - так надо по условию задачи.. поэтому и формула другая)
n - порядковый номер единицы(т.е. какая по счету единица находится в к-ой позиции... исчисление с нуля)

при соблюдении всех этих условий мы попадаем в единицу и обратно - при не соблюдении в ноль....

я решил пойти таким путем

переписал уравнение:

Код

n*n + n -2(k-1) = 0

т.к. k=const мы имеем квадратное уравнение(ax*x+bx+c=0).
если его корни будут удавлетворять условиям

Код

0<=n n - целые

то на позиции k - единица

решаем уравнение...
D=b*b - 4ac;
D= 1+8(k-1) = 8k-7
n = ( -1 + sqrt(D) ) / 2

n = ( -1 - sqrt(D) ) / 2 - это уравнение можем сразу отбросить, т.к. оно не удовлетворяет области определения (?) - при всех положительных целых k (это и есть область определения) n удет отрицательным (вот этто-то и не удовлетворяет)

а для того, чтобы из первого урвнения получить допустимое n, корень из дискриминанта должен быть целым числом... соответственно и значение под корнем должно быть полным квадратом...

вот и получается

Код

8k-7

можно пойти и другим путем, но я пошел этим и случайно обнаружил проблему при работе с С++... если бы на такое наткнуться в реальном проекте - было бы не сладко... хотя кому нужно вычислять такие громадные корни....

Цитата(MOP @ 2.9.2005, 21:20)

хотя кому нужно вычислять такие громадные корни....

Есть библиотеки работы с экстремально большими числами - какие проблемы? хоть миллион цифр... кста, бывает что надобится.

В твоём примере

Цитата(MOP @ 31.8.2005, 23:09)

Код #include <iostream.h> #include <math.h> void main() {     unsigned short length;     unsigned int input;     char i;     cin >> length;     for ( i = 0; i < length; i++ )     {         cin >> input;         if ( (int)(sqrt((double)(8*input - 7))) == sqrt((double)(8*input - 7)) )             cout << '1';         else             cout << '0';     } }

попробуй заменить строку

Код

if ( (int)(sqrt((double)(8*input - 7))) == sqrt((double)(8*input - 7)) )

на

Код

if(pow((int)sqrt(input), 2) == input)