Форум программистов [Powered by Invision Power Board]

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

Форум программистов > C/C++: Общие вопросы > Извлечение квадратного корня

Автор: mr.Anderson 12.2.2006, 19:38

Не сумел найти ответа в FAQ (там есть похожая тема, но она не открывается). Как написать примерно по такому алгоритму прогу:

1. Юзер вводит число.
2. Если из числа можно извлечь корень, и полученное число будет целым, то вывести полученное число.
3. Если из числа можно извлечь корень, но полученное число нецелое, то сказать об этом и вывести нецелый результат.
4. Если корень не извлекается (т.е. число иррациональное), то сказать об этом и ничего не делать.

Я не прошу написать программочку за меня, я прошу объяснить мне алгоритм ее написания. И подбросьте плиз функцию извлечения кв. корня из чисел, из которых он нацело не извлекается...

Автор: Mayk 12.2.2006, 19:45

sqrt

Цитата

SQRT(3) Linux Programmer's Manual SQRT(3)

NAME
sqrt, sqrtf, sqrtl - square root function

SYNOPSIS
#include <math.h>

double sqrt(double x);
float sqrtf(float x);
long double sqrtl(long double x);

Link with -lm.

DESCRIPTION
The sqrt() function returns the non-negative square root of x. It
fails and sets errno to EDOM, if x is negative.
ERRORS
EDOM x is negative.

CONFORMING TO
SVID 3, POSIX, BSD 4.3, ISO 9899. The float and the long double vari-
ants are C99 requirements.

SEE ALSO
cbrt(3), csqrt(3), hypot(3)

2002-07-27 SQRT(3)

Автор: mr.Anderson 12.2.2006, 19:48

Спасибо! Только вот на этот вопрос нет ответа:

Цитата

Если из числа можно извлечь корень, но полученное число нецелое

Автор: DeadSoul 12.2.2006, 19:50

Цитата(sim7 @ 12.2.2006, 19:48

)

Спасибо! Только вот на этот вопрос нет ответа:
Цитата
Если из числа можно извлечь корень, но полученное число нецелое

А такое возможно? По-моему не существует нецелых чисел квадрат которых - целое число

Автор: profispb 12.2.2006, 19:52

sim7, Умнож дробное число на 1.0 и функция SQRT(3.567*1.0);

Автор: Mayk 12.2.2006, 19:52

Цитата(sim7 @ 12.2.2006, 23:48

)

(static_cast<int>(v) == v) будет истинным <=> v целое

Автор: mr.Anderson 12.2.2006, 19:54

Тьфу ты. Точно. А код

Код


int x,y;
if(!(x==sqrt(y)) cout<<"Число иррациональное";

Будет работать правильно? Т.е. програ скажет, что корень извлечь нельзя?

Автор: Mayk 12.2.2006, 20:02

Цитата(sim7 @ 12.2.2006, 23:54

)

Тьфу ты. Точно. А код
int x,y;
if(!(x==sqrt(y)) cout<<"Число иррациональное";
Будет работать правильно? Т.е. програ скажет, что корень извлечь нельзя?

ээ. скорее всего выделенный участок никогда не выполнится.

Цитата(Mayk @ 12.2.2006, 23:45

)

ERRORS
EDOM x is negative.

Автор: Adil' 13.2.2006, 17:16

Цитата(Mayk @ 12.2.2006, 19:52

)

(static_cast<int>(v) == v) будет истинным <=> v целое

, это как повезет - если не ошибаюсь static_cast<int>(v) при сравнении с v (которое doulbe) будет приведено к double, и если static_cast<int>(v) нельзя разложить в ряд по степеням двойки, то...
Лучше сравнивать так if(fabs(v-(int)v)<1.e-10)

Автор: threef 13.2.2006, 18:52

a^2=x
a= x/a
2a=a+x/a
a[k]=(a[k-1]+x/a)/2
| a[k]-a[k-1] | < epsilon
Это формула Ньютона, к - шаг итерации. А проверить , является ли число целым - привести к int корень и возвести в квадрат. С учетом того, что целые должны входить в диапазон целых чисел.

Автор: Mayk 13.2.2006, 19:43

Цитата(Adil' @ 13.2.2006, 21:16

)

static_cast<int>(v) нельзя разложить в ряд по степеням двойки

А когда это двоичное число нельзя разложить по степеням двойки?

Проверим:

Код


#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>

int main()
{
    int stat_check[2]={};
    int fabs_check[2]={};
    int iterations=10240000;
    srand(time(0));
    srand48(time(0));
    while(iterations--){
#ifdef DO_RAND
        double f = drand48() * rand();
#else
        double f = iterations;
#endif
        double s = sqrt(f);
        bool r1 = static_cast<int>(s) == s;
        bool r2 = (fabs(s - (int)s) < 1.e-10);
        if(r1 != r2){
            printf("%f/%f\n",f,s);
        }
        stat_check[r1]++;
        fabs_check[r2]++;
    }
    printf("stat: %d dbls/%d ints;",stat_check[0],stat_check[1]);
    printf("fabs: %d dbls/%d ints ",fabs_check[0],fabs_check[1]);
    printf("(RAND_MAX=%d)\n", RAND_MAX);
}

Тест 1. Абсолютно случайные.

Цитата(bash)

22:29 ~/src/pol$ g++ -oa.out a.cpp -DDO_RAND -O6
22:29 ~/src/pol$ for ((i=0;i<15;++i)); do nice -n0 ./a.out; done
stat: 10240000 dbls/0 ints;fabs: 10240000 dbls/0 ints (RAND_MAX=2147483647)
(и так 15 раз)

Тест 2. Сверх малые ( [0;1) ).
0) Убрать * rand().
1) Запустить. Очевидно, результат тот же самый что и в предыдущем примере.

Тест 3. Случайные целые.
Заменить double f = drand48(); на double f = rand();

Цитата

22:38 ~/src/pol$ for ((i=0;i<15;++i)); do nice -n0 ./a.out; done
stat: 10239770 dbls/230 ints;fabs: 10239770 dbls/230 ints (RAND_MAX=2147483647)
stat: 10239762 dbls/238 ints;fabs: 10239762 dbls/238 ints (RAND_MAX=2147483647)
stat: 10239803 dbls/197 ints;fabs: 10239803 dbls/197 ints (RAND_MAX=2147483647)
stat: 10239787 dbls/213 ints;fabs: 10239787 dbls/213 ints (RAND_MAX=2147483647)
stat: 10239788 dbls/212 ints;fabs: 10239788 dbls/212 ints (RAND_MAX=2147483647)
stat: 10239799 dbls/201 ints;fabs: 10239799 dbls/201 ints (RAND_MAX=2147483647)
stat: 10239801 dbls/199 ints;fabs: 10239801 dbls/199 ints (RAND_MAX=2147483647)
stat: 10239789 dbls/211 ints;fabs: 10239789 dbls/211 ints (RAND_MAX=2147483647)
stat: 10239764 dbls/236 ints;fabs: 10239764 dbls/236 ints (RAND_MAX=2147483647)
stat: 10239789 dbls/211 ints;fabs: 10239789 dbls/211 ints (RAND_MAX=2147483647)
stat: 10239788 dbls/212 ints;fabs: 10239788 dbls/212 ints (RAND_MAX=2147483647)
stat: 10239761 dbls/239 ints;fabs: 10239761 dbls/239 ints (RAND_MAX=2147483647)
stat: 10239791 dbls/209 ints;fabs: 10239791 dbls/209 ints (RAND_MAX=2147483647)
stat: 10239800 dbls/200 ints;fabs: 10239800 dbls/200 ints (RAND_MAX=2147483647)
stat: 10239788 dbls/212 ints;fabs: 10239788 dbls/212 ints (RAND_MAX=2147483647)

Тест 4. Последовательные целые.

Цитата

22:39 ~/src/pol$ g++ -oa.out a.cpp -UDO_RAND -O6
22:40 ~/src/pol$ ./a.out
stat: 10236800 dbls/3200 ints;fabs: 10236800 dbls/3200 ints (RAND_MAX=2147483647)

Итого проверено 10240000 * 15 * 3 + 10240000 = 471.040.000 чисел.

Надежность static_cast проверки считаю доказанной.