Содержит ли диапазон целых чисел хотя бы один идеальный квадрат?

Question

Учитывая два целых числа a и b, существует ли эффективный способ проверить, существует ли другое целое число n такое, что a ≤ n<sup>2</sup> < b?

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

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

Примеры:

• intervalContainsSquare(2, 3) => false
• intervalContainsSquare(5, 9) => false (примечание: 9 выходит за пределы этого интервала)
• intervalContainsSquare(9, 9) => false (этот интервал пуст)
• intervalContainsSquare(4, 9) => true (в этом интервале 4)
• intervalContainsSquare(5, 16) => true (в этом интервале 9)
• intervalContainsSquare(1, 10) => true (1, 4 и 9 находятся внутри этого интервала)

Answer 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 <b. </p>

---

Поскольку встал вопрос о правильной алгебре:

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) с помощью метода Ньютона или таблицы поиска, за которой следуют несколько шагов метода Ньютона. В принципе, быстрее вычислить ceil (sqrt (a)), чем sqrt (a), потому что арифметику с плавающей запятой можно упростить до целочисленной арифметики, а также потому, что вам не нужно столько шагов метода Ньютона, чтобы получить высокую точность, которая Вы просто собираетесь выбросить. Но на практике функция числовой библиотеки может быть намного быстрее, если она использует квадратные корни, реализованные в микрокоде. Если по какой-либо причине у вас нет этого микрокода, который мог бы вам помочь, то, возможно, стоит написать код ceil (sqrt (a)). Возможно, самый интересный случай будет, если a и b - неограниченные целые числа (например, тысяча цифр). Но для целых чисел обычного размера на обычном, не устаревшем компьютере вы не можете превзойти FPU.

Answer 2

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

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

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

Answer 3

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

Answer 4

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

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

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

Answer 5

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

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

Если sb ² = b и sa = sb-1, тогда номер выхода

Если sa

Иначе номер выхода.

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

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

---

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

Вы начинаете с догадки для n, n = 1 и вычисляете n ²

Подумайте, если a <= n <b, вы можете остановиться. </p>

Если n

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

Answer 6

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

Answer 7

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

Answer 8

Один из способов - использовать метод Ньютона, чтобы найти целочисленный квадратный корень для 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;
}