Czy zakres liczb całkowitych zawiera co najmniej jeden idealny kwadrat?

Question

Biorąc pod uwagę dwie liczby całkowite a i b, czy istnieje skuteczny sposób sprawdzenia, czy istnieje inna liczba całkowita n taka, że ​​a ≤ n2 < b?

nie muszę wiedzieć n, tylko czy co najmniej jeden taki n istnieje, czy nie, więc mam nadzieję, że unika obliczeniowych pierwiastki kwadratowe jakichkolwiek liczb w przedziale.

Mimo że testing whether an individual integer is a perfect square is faster than computing the square root, zakres może być duży i wolałbym również unikać wykonywania tego testu dla każdej liczby w zakresie.

Przykłady:

• intervalContainsSquare(2, 3) => false
• intervalContainsSquare(5, 9) => fałszem (uwaga: 9, jest poza tym przedziale)
• intervalContainsSquare(9, 9) => fałszem (przedział ten jest pusta)
• intervalContainsSquare(4, 9) = > true (4 znajduje się w tym przedziale)
• intervalContainsSquare(5, 16) => true (9 znajduje się w tym przedziale)
• intervalContainsSquare(1, 10) => prawdziwe (1, 4 i 9 znajdują się wewnątrz tego przedziału)

Answer 1

Obliczanie, czy liczba jest kwadratem, nie jest tak naprawdę szybsze niż obliczenie pierwiastka kwadratowego w trudnych przypadkach, o ile wiem. Prawdą jest to, że możesz dokonać precomputation, aby wiedzieć, że nie jest to kwadrat, który może zaoszczędzić czas średnio.

Podobnie w przypadku tego problemu, można wykonać obliczenia wstępne, aby określić, że sqrt (b) -sqrt (a)> = 1, co oznacza, że ​​a i b są na tyle daleko od siebie, że między nimi musi być kwadrat. W przypadku pewnej algebry ta nierówność jest równoważna warunkowi, że (ba-1)^2> = 4 * a, lub jeśli chcesz go w bardziej symetrycznej formie, to (ab)^2 + 1> = 2 * (a + b). Zatem to obliczenie wstępne można wykonać bez pierwiastków kwadratowych, tylko z jednym produktem całkowitym i pewnymi dodatkami i odejmacjami.

Jeśli a i b są prawie dokładnie takie same, to nadal możesz wykorzystać sztuczkę szukania cyfr binarnych niskiego rzędu jako wstępnego obliczenia, aby wiedzieć, że między nimi nie ma kwadratu. Ale muszą być tak blisko siebie, że to wcześniejsze obliczenie może nie być tego warte.

Jeśli te wstępne obliczenia są niejednoznaczne, to nie mogę wymyślić niczego innego niż rozwiązanie innych osób, tj. < = ceil (sqrt (a))^2 < b.

---

Ponieważ nie była to kwestia robi prawo algebry:

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 

---

także: Ogólnie, kiedy to duża liczba, by obliczyć sqrt (a) metodą Newtona lub z tabelą odnośników, po której następuje kilka kroków metody Newtona. Zasadniczo przyspieszenie obliczenia ceil (sqrt (a)) jest mniejsze niż sqrt (a), ponieważ arytmetyka zmiennoprzecinkowa może być uproszczona do arytmetycznej liczby całkowitej, a także dlatego, że nie potrzeba tylu kroków metody Newtona, aby uzyskać wysoką precyzję, po prostu wyrzucisz. Ale w praktyce funkcja biblioteki numerycznej może być znacznie szybsza, jeśli używa ona pierwiastków kwadratowych zaimplementowanych w mikrokodzie. Jeśli z jakiegoś powodu nie masz tego mikrokodu, który mógłby ci pomóc, to może warto go zaszyfrować (sqrt (a)). Być może najciekawszym przypadkiem byłoby, gdyby a i b były nieograniczonymi liczbami całkowitymi (np. Tysiąc cyfr). Ale w przypadku zwykłych liczb całkowitych na zwykłym, nieaktualnym komputerze, nie można pokonać jednostki FPU.

Answer 2

znaleźć integralną część sqrt (a) i sqrt (B), np SA i SB.

Jeśli sa = a, a następnie wypisać tak.

Jeśli sb = b i sa = sb-1, to wynik nie.

Jeśli sa < wyjście sb tak.

Inny numer wyjścia

Możesz zoptymalizować powyższe, aby pozbyć się obliczeń sqrt (b) (podobnie jak w odpowiedzi JDunkerly'ego).

A może chcesz uniknąć obliczania pierwiastków kwadratowych z aib?

---

Możesz całkowicie pominąć obliczanie pierwiastków kwadratowych przy użyciu metody podobnej do wyszukiwania binarnego.

Zaczynasz z przypuszczeniem n, n = 1 i obliczyć n

Rozważmy jeśli < < b = n, można zatrzymać.

Jeśli n < a < b, podwajasz swoje domysły n. , jeśli < b < n, zbliżasz się do średniej bieżącego + poprzedniego wyniku.

To będzie godzina O (logb).

Answer 3

Jeśli będzie akceptować obliczania dwa pierwiastki kwadratowe, ze względu na jej monotoniczności masz tę nierówność, która jest równoważna do listy zaczynające One:

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

zatem, jeśli floor(sqrt(a)) != floor(sqrt(b)), floor(sqrt(b)) - 1 jest gwarancją taka n.

Answer 4

1. uzyskać pierwiastek kwadratowy z mniejszą liczbą i zaokrąglić w górę
2. uzyskać pierwiastek kwadratowy z większą liczbą i zaokrąglić w dół
3. jeśli 1 jest mniejsza lub równa 2, nie będzie idealny kwadrat

Answer 5

Uzyskaj pierwiastek kwadratowy z niższej liczby. Jeśli jest to liczba całkowita, to skończysz. W przeciwnym razie należy zaokrąglić w górę i wyrównać liczbę. Jeśli jest to mniej niż b, to jest to prawda.

Musisz obliczyć tylko jeden pierwiastek kwadratowy w ten sposób.

Aby uniknąć problemu, kiedy a jest równe b, należy to najpierw sprawdzić. Ponieważ ta sprawa jest zawsze fałszywa.

Answer 6

Jednym ze sposobów jest użycie metody Newtona do znalezienia integer square root dla b. Następnie możesz sprawdzić, czy ta liczba mieści się w zakresie. Wątpię, że to szybciej niż po prostu wywołanie funkcji pierwiastka kwadratowego, ale na pewno jest bardziej interesująca:

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; 
} 

Answer 7

Poza ładnym rozwiązania JDunkerley'S (+1), nie może być możliwa poprawa, która musi być przetestowany i używa integer square roots do obliczania całkowitych pierwiastków kwadratowych

Answer 8

Dlaczego masz nadzieję całkowicie uniknąć pierwiastków kwadratowych? Nawet zanim osiągniesz najbardziej efektywny sposób rozwiązania tego problemu, widziałeś metody, które wymagają tylko 2 pierwiastków kwadratowych. Robi się to w czasie O (1), więc wydaje mi się, że jakiekolwiek ulepszenie, które mógłbyś mieć nadzieję, zajęłoby więcej czasu, niż KIEDYKOLWIEK zaoszczędziłoby ci czas komputerowy. Czy się mylę?