Могу ли я рассчитывать на это, чтобы судить о квадратном числе в C++?

Question

Могу ли я рассчитывать на это, чтобы судить о квадратном числе в C++?

Могу ли я положиться на

sqrt((float)a)*sqrt((float)a)==a

или же

(int)sqrt((float)a)*(int)sqrt((float)a)==a

проверить, является ли число идеальным квадратом? Почему или почему нет?
int a это число, которое будет оценено. Я использую Visual Studio 2005.

Редактировать: Спасибо за все эти быстрые ответы. Я вижу, что не могу полагаться на сравнение типов с плавающей точкой. (Если я написал как выше, будет ли последний a быть брошенным, чтобы плавать неявно?) Если я делаю это как

(int)sqrt((float)a)*(int)sqrt((float)a) - a < e

Как мало я должен взять это e значение?

Edit2: Эй, почему бы нам не оставить в стороне часть сравнения и решить, (int) является необходимым? Как я вижу, с этим разница может быть велика для квадратов; но без этого разница может быть небольшой для не квадратов. Возможно, ни один не подойдет.:-(

5

c++ math floating-point perfect-square

Источник

09 сен '09 в 09:42

12 ответов

Другие вопросы по тегам c++ math floating-point perfect-square

user1584012 09 сен '09 в 09:51 2009-09-09 09:51 · Answer 1 · 2009-09-09 09:51

На самом деле, это не C++, а математический вопрос.

С числами с плавающей точкой вы никогда не должны полагаться на равенство. Если вы хотите протестировать a == b, просто протестируйте против abs(a - b)
Если число, которое вы тестируете, является целым числом, вас может заинтересовать статья в Википедии о целочисленном квадратном корне

РЕДАКТИРОВАТЬ:

Как сказал Кругар, статья, на которую я ссылаюсь, ничего не отвечает. Конечно, нет прямого ответа на ваш вопрос, Фени. Я просто подумал, что основная проблема, с которой вы столкнулись, - это точность с плавающей запятой, и, возможно, вы хотели получить математический фон для своей задачи.

Для нетерпеливых есть ссылка в статье на длительное обсуждение реализации isqrt. Это сводится к коду karx11erx, опубликованному в его ответе.

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

user48387 09 сен '09 в 10:10 2009-09-09 10:10 · Answer 2 · 2009-09-09 10:10

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

Isqrt взят отсюда и является O(log n)

// Finds the integer square root of a positive number
static int Isqrt(int num)
{
    if (0 == num) { return 0; }  // Avoid zero divide
    int n = (num / 2) + 1;       // Initial estimate, never low
    int n1 = (n + (num / n)) / 2;
    while (n1 < n)
    {
        n = n1;
        n1 = (n + (num / n)) / 2;
    } // end while
    return n;
} // end Isqrt()

static bool IsPerfectSquare(int num)
{
    return Isqrt(num) * Isqrt(num) == num;
}

user43614 09 сен '09 в 10:15 2009-09-09 10:15 · Answer 3 · 2009-09-09 10:15

На ваш вопрос уже дан ответ, но вот рабочее решение.

Ваши "идеальные квадраты" являются неявно целочисленными значениями, поэтому вы можете легко решить проблемы точности, связанные с форматом с плавающей запятой, используя некоторую целочисленную функцию квадратного корня для определения целочисленного квадратного корня значения, которое вы хотите проверить. Эта функция вернет наибольшее число r для значения v где r * r <= v, Когда у вас есть r, вам просто нужно проверить, r * r == v,

unsigned short isqrt (unsigned long a)
{
    unsigned long rem = 0;
    unsigned long root = 0;

    for (int i = 16; i; i--) {
        root <<= 1;
        rem = ((rem << 2) + (a >> 30));
        a <<= 2;
        if (root < rem)
            rem -= ++root;
    }

    return (unsigned short) (root >> 1);
}

bool PerfectSquare (unsigned long a)
{
    unsigned short r = isqrt (a);

    return r * r == a;
}

user71883 09 сен '09 в 09:48 2009-09-09 09:48 · Answer 4 · 2009-09-09 09:48

Чтобы не делать один и тот же расчет дважды, я бы сделал это с временным числом:

 int b = (int)sqrt((float)a);
 if((b*b) == a)
 {
     //perfect square
 }

редактировать: Дав сделал хорошую мысль. вместо того, чтобы полагаться на актерский состав, вам нужно сначала закруглить поплавок

так и должно быть:

 int b = (int) (sqrt((float)a) + 0.5f);
 if((b*b) == a)
 {
     //perfect square
 }

user149139 09 сен '09 в 09:53 2009-09-09 09:53 · Answer 5 · 2009-09-09 09:53

Я не следовал формуле, я прошу прощения. Но вы можете легко проверить, является ли число с плавающей запятой целым, приведя его к целочисленному типу, и сравнить результат с числом с плавающей запятой. Так,

bool isSquare(long val) {
    double root = sqrt(val);
    if (root == (long) root)
        return true;
    else return false;
}

Естественно, это выполнимо, только если вы работаете со значениями, которые, как вы знаете, будут вписываться в диапазон целочисленных типов. Но в этом случае вы можете решить проблему таким образом, избавив вас от внутренней сложности математической формулы.

user153619 09 сен '09 в 14:43 2009-09-09 14:43 · Answer 6 · 2009-09-09 14:43

Как говорит Рейнир, вам нужно добавить 0,5, чтобы убедиться, что оно округляется до ближайшего целого числа, так что вы получите

int b = (int) (sqrt((float)a) + 0.5f);
if((b*b) == a) /* perfect square */

Чтобы это работало, b должен быть (точно) равен квадратному корню из a если a это идеальный квадрат. Тем не менее, я не думаю, что вы можете гарантировать это. Предположим, что int 64 бит и float 32 бита (я думаю, что это разрешено). затем a может быть порядка 2^60, поэтому его квадратный корень имеет порядок 2^30. Тем не менее, float хранит только 24 бита в значении, поэтому ошибка округления имеет порядок 2^(30-24) = 2^6. Это больше 1, так b может содержать неправильное целое число. Например, я думаю, что приведенный выше код не идентифицирует a = (2^30+1)^2 как идеальный квадрат.

user14065 09 сен '09 в 16:30 2009-09-09 16:30 · Answer 7 · 2009-09-09 16:30

Я бы сделал.

// sqrt always returns positive value. So casting to int is equivalent to floor()
int down =  static_cast<int>(sqrt(value));
int up   = down+1;                           // This is the ceil(sqrt(value))

// Because of rounding problems I would test the floor() and ceil()
// of the value returned from sqrt().
if (((down*down) == value) || ((up*up) == value))
{
     // We have a winner.
}

1

Источник

user14065 09 сен '09 в 16:30

user199724 30 окт '09 в 15:19 2009-10-30 15:19 · Answer 8 · 2009-10-30 15:19

Самое чистое решение - использовать целочисленную подпрограмму sqrt, а затем выполнить:

bool isSquare( unsigned int a ) {

  unsigned int s = isqrt( a );
  return s * s == a;

}

Это будет работать в полном диапазоне int и с идеальной точностью. Несколько случаев:

a = 0, s = 0, s * s = 0 (add an exception if you don't want to treat 0 as square)  
a = 1, s = 1, s * s = 1  
a = 2, s = 1, s * s = 1  
a = 3, s = 1, s * s = 1  
a = 4, s = 2, s * s = 4  
a = 5, s = 2, s * s = 4

Не подведет, так как вы приближаетесь к максимальному значению для вашего размера int. Например, для 32-битных целых:

a = 0x40000000, s = 0x00008000, s * s = 0x40000000  
a = 0xFFFFFFFF, s = 0x0000FFFF, s * s = 0xFFFE0001

Использование поплавков приводит к ряду проблем. Вы можете найти это sqrt( 4 ) = 1.999999...и аналогичные проблемы, хотя вы можете округлить до ближайшего вместо использования floor(),

Хуже того, у float есть только 24 значащих бита, что означает, что вы не можете привести к целому числу больше 2^24-1 без потери точности, что приводит к ложным положительным / отрицательным значениям. Используя удвоения для тестирования 32-битных целых, у вас все будет хорошо.

Но не забывайте приводить результат sqrt с плавающей точкой обратно к int и сравнивать результат с исходным int. Сравнение между поплавками никогда не бывает хорошей идеей; даже для квадратных значений x в ограниченном диапазоне нет никакой гарантии, что sqrt( x ) * sqrt( x ) == x, или это sqrt( x * x) = x,

user170909 09 сен '09 в 16:02 2009-09-09 16:02 · Answer 9 · 2009-09-09 16:02

Более очевидный, если медленнее - O(sqrt(n)) - путь:

bool is_perfect_square(int i) {
    int d = 1;
    for (int x = 0; x <= i; x += d, d += 2) {
        if (x == i) return true;
    }
    return false;   
}

0

Источник

user170909 09 сен '09 в 16:02

user61539 09 сен '09 в 17:33 2009-09-09 17:33 · Answer 10 · 2009-09-09 17:33

В то время как другие отметили, что вы не должны проверять равенство с плавающей точкой, я думаю, что вы упускаете возможность использовать свойства совершенных квадратов. Во-первых, нет смысла пересчитывать вычисленный корень. Если a тогда идеальный квадрат sqrt(a) является целым числом, и вы должны проверить:

b = sqrt((float)a)
b - floor(b) < e

где e установлено достаточно мало. Есть также несколько целых чисел, которые вы можете пересечь как не квадратные, прежде чем брать квадратный корень. Проверяя Википедию, вы можете увидеть некоторые необходимые условия для a быть квадратным:

Квадратное число может заканчиваться только цифрами 00,1,4,6,9 или 25 в основании 10

Еще одна простая проверка будет видеть, что a % 4 == 1 or 0 до получения рута, так как:

Квадраты четных чисел четные, поскольку (2n)^2 = 4n^2.
Квадраты нечетных чисел нечетны, поскольку (2n + 1)^2 = 4(n^2 + n) + 1.

Это, по существу, устранит половину целых чисел, прежде чем принимать какие-либо корни.

user150740 09 сен '09 в 09:47 2009-09-09 09:47 · Answer 11 · 2009-09-09 09:47

Основы в первую очередь:

если вы (int) число в расчете, он удалит ВСЕ данные после запятой. Если я правильно помню свой C, если у вас есть (int) в любом вычислении (+/-*), он автоматически предполагает int для всех других чисел.

Так что в вашем случае вы хотите плавать на каждом задействованном числе, иначе вы потеряете данные:

sqrt((float)a)*sqrt((float)a)==(float)a

это путь, которым вы хотите идти

user2119053 09 сен '09 в 09:51 2009-09-09 09:51 · Answer 12 · 2009-09-09 09:51

Математика с плавающей точкой неточна по своей природе.

Итак, рассмотрим этот код:

int a=35;
float conv = (float)a;
float sqrt_a = sqrt(conv);
if( sqrt_a*sqrt_a == conv )
    printf("perfect square");

вот что произойдет:

a = 35
conv = 35.000000
sqrt_a = 5.916079
sqrt_a*sqrt_a = 34.999990734

это совершенно ясно, что sqrt_a^2 не равно a.

-2

Источник

user2119053 09 сен '09 в 09:51