Имеет ли диапазон целых чисел по крайней мере один идеальный квадрат?

Ответ 1

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

Аналогично для этой проблемы вы можете сделать предварительную вычисление, чтобы определить, что sqrt (b) -sqrt (a) >= 1, что означает, что a и b достаточно далеко друг от друга, что между ними должен быть квадрат. С некоторой алгеброй это неравенство эквивалентно условию (ba-1) ^ 2 >= 4 * a или если вы хотите, чтобы он был в более симметричной форме, то (ab) ^ 2 + 1 >= 2 * (a + б). Таким образом, эта предварительная оценка может быть выполнена без квадратных корней, только с одним целым продуктом и некоторыми дополнениями и вычитаниями.

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

Если эти предварительные вычисления неубедительны, то я не могу думать ни о чем другом, кроме решения всех остальных, a <= ceil (sqrt (a)) ^ 2 < б.

Так как возник вопрос о правильной алгебре:

sqrt(b)-sqrt(a) >= 1
sqrt(b) >= 1+sqrt(a)
b >= 1+2*sqrt(a)+a
b-a-1 >= 2*sqrt(a)
(b-a-1)^2 >= 4*a

Также: Обычно, когда a является большим числом, вы должны вычислять sqrt (a) с помощью метода Newton или с помощью таблицы поиска, за которой следуют несколько шагов метода Newton. В принципе, быстрее вычислять ceil (sqrt (a)), чем sqrt (a), поскольку арифметику с плавающей запятой можно упростить до целочисленной арифметики и потому, что вам не нужно столько шагов метода Newton, чтобы прибить высокую точность, что вы просто собираетесь выбросить. Но на практике функция числовой библиотеки может быть намного быстрее, если она использует квадратные корни, реализованные в микрокоде. Если по какой-либо причине у вас нет этого микрокода, который может вам помочь, тогда это может стоить для кода-кода (sqrt (a)). Может быть, самым интересным будет случай, если a и b - неограниченные целые числа (например, тысяча цифр). Но для обычных чисел на обычном не устаревшем компьютере вы не можете победить FPU.

Ответ 2

Получите квадратный корень из нижнего числа. Если это целое число, то все готово. В противном случае округлите и закруглите число. Если это меньше, чем b, это верно.

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

Чтобы избежать проблемы, когда a равно b, вы должны сначала проверить это. Поскольку этот случай всегда неверен.

Ответ 3

Если вы примете вычисление двух квадратных корней, из-за его монотонности у вас есть это неравенство, которое эквивалентно вашему начальному:

sqrt(a) <= n < sqrt(b)

таким образом, если floor(sqrt(a)) != floor(sqrt(b)), floor(sqrt(b)) - 1 гарантированно будет таким n.

Ответ 4

• получить квадратный корень из нижнего числа и округлить его
• получить квадратный корень из большего числа и округлить его
• если 1 меньше или равно 2, будет идеальный квадрат

Ответ 5

Найдите неотъемлемую часть sqrt (a) и sqrt (b), скажем sa и sb.

Если sa ²= a, тогда выведите yes.

Если sb ²= b и sa = sb-1, тогда выведите no.

Если sa < sb output yes.

Остаток вывода

Вы можете оптимизировать вышеупомянутое, чтобы избавиться от вычисления sqrt (b) (похоже на ответ JDunkerly).

Или вы не хотели бы вычислять квадратные корни a и b тоже?

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

Вы начинаете с предположения о n, n = 1 и вычисляете n ²

Рассмотрим, если a <= n < b, вы можете остановиться.

Если n < a < b, вы удваиваете свое предположение n. если a < b < n, вы приближаетесь к среднему значению текущего + предыдущего предположения.

Это будет время O (logb).

Ответ 6

Один из способов - использовать метод Ньютона, чтобы найти целочисленный квадратный корень для b. Затем вы можете проверить, попадает ли этот номер в диапазон. Я сомневаюсь, что это быстрее, чем просто вызвать функцию квадратного корня, но это, безусловно, более интересно:

int main( int argc, char* argv[] )
{
    int a, b;
    double xk=0, xk1;
    int root;
    int iter=0;
    a = atoi( argv[1] );
    b = atoi( argv[2] );

    xk1 = b / 32 + 1;  // +1 to ensure > 0
    xk1 = b;
    while( fabs( xk1 - xk ) >= .5 ) {
        xk = xk1;
        xk1 = ( xk + b / xk ) / 2.;
        printf( "%d) xk = %f\n", ++iter, xk1 );
    }

    root = (int)xk1;

    // If b is a perfect square, then this finds that root, so it also
    // needs to check if (n-1)^2 falls in the range.
    // And this does a lot more multiplications than it needs
    if ( root*root >= a && root*root < b ||
         (root-1)*(root-1) >= a && (root-1)*(root-1) < b )
        printf( "Contains perfect square\n" );
    else
        printf( "Does not contain perfect square\n" );

    return 1;
}

Ответ 7

В дополнение к приятному решению JDunkerley (+1) может быть возможное улучшение, которое необходимо протестировать, и использует целые квадратные корни для вычисления целочисленных квадратных корней

Ответ 8

Почему вы надеетесь полностью избежать квадратных корней? Даже до того, как вы доберетесь до самого эффективного способа решения этого вопроса, вы видели методы, которые требуют только 2 квадратных корня. Это было сделано в O (1) раз, поэтому мне кажется, что любое улучшение, которое вы могли бы надеяться сделать, уделило бы больше времени, чтобы подумать, чем ЭТО бы экономить ваше вычислительное время. Я не прав?