정수 범위에 하나 이상의 완벽한 사각형이 포함되어 있습니까?

Question

두 개의 정수 a과 b이 주어 졌을 때, 과 같은 다른 정수가 있는지 확인하는 효과적인 방법이 있습니까? a ≤ n2 < b?

나는 적어도 하나의 n 존재 여부를 여부 만, n을 알 필요가 없다, 그래서 제곱근을 계산 피하기 위해 희망의 간격에있는 숫자의.

testing whether an individual integer is a perfect square is faster than computing the square root이지만 범위가 클 수도 있고 범위 내의 모든 숫자에 대해이 테스트를 수행하지 않는 것이 좋습니다.

예 :

• intervalContainsSquare(2, 3) => 거짓
• intervalContainsSquare(5, 9) = "거짓 (참고 : 9이 간격 밖에)
• intervalContainsSquare(9, 9) ="거짓 (이 간격이 비어)
• intervalContainsSquare(4, 9) = > true (이 간격 안에 4가 있음)
• intervalContainsSquare(5, 16) => true (이 간격 안에 9가 있음)
• intervalContainsSquare(1, 10) => (1, 4, 9,이 구간 안에 모두)

Answer 1

숫자가 사각형인지 아닌지를 계산하는 것은 어려운 경우에 제곱근을 계산하는 것보다 빠르지 않습니다. 사실입니다. 사전 계산을 수행하여 사각형이 아니라는 것을 알면 평균 시간을 절약 할 수 있습니다.

마찬가지로이 문제의 경우 미리 계산을 수행하여 sqrt (b) -sqrt (a)> = 1이라고 결정할 수 있습니다. 그러면 a와 b가 충분히 떨어져있어 그 사이에 정사각형이 있어야 함을 의미합니다. 일부 대수학의 경우,이 부등식은 (ba-1)^2> = 4 * a와 같은 조건이나,보다 대칭적인 형태로 원한다면 (ab)^2 + 1> = 2 * (a + b). 따라서이 사전 계산은 제곱근을 사용하지 않고 하나의 정수 곱과 일부 더하기 및 빼기 만 사용하여 수행 할 수 있습니다.

a와 b가 거의 동일하면 사전 계산으로 낮은 차수의 이진수를 보는 트릭을 사용하여 그 사이에 사각형이 없음을 알 수 있습니다. 그러나 그들은이 사전 계산이 가치가 없을만큼 가까이에 있어야합니다.

이러한 사전 계산이 결론적이지 않은 경우 다른 사람의 솔루션 이외의 다른 것을 생각할 수 없습니다. < = ceil (sqrt (a))^2 < b.

---

대수를 오른쪽으로하고의 문제가 있었다 버젼 :

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)는 뉴턴의 방법, 또는 조회 테이블과 몇 가지 뉴턴의 방법 단계가 뒤 따른다. 부동 소수점 산술은 정수 연산으로 단순화 될 수 있고 높은 정밀도를 보장하기 위해 많은 뉴턴의 방법 단계가 필요 없기 때문에 sqrt (a)보다 ceil (sqrt (a))을 계산하는 것이 더 빠릅니다 너는 그냥 버릴거야. 그러나 실제로는 마이크로 코드로 구현 된 제곱근을 사용하면 수치 라이브러리 함수가 훨씬 더 빠를 수 있습니다. 어떤 이유에서 건 당신이 도움이되는 마이크로 코드를 가지고 있지 않다면, ceil (sqrt (a))을 직접 코딩 할 가치가있을 것입니다. 어쩌면 가장 흥미로운 경우는 a와 b가 무한대의 정수 (예 : 1000 자리) 인 경우 일 것입니다. 그러나 일반적인 쓸데없는 컴퓨터의 일반 크기 정수의 경우 FPU를 이길 수 없습니다.

Answer 2

SQRT (a) 및 SQRT (b)의 정수 부분을 찾아, SA 및 SB라고 참.

= a이면 출력 예.

sb = b 및 sa = sb-1 인 경우 출력 번호.

< 출력이 예인 경우.

기타 출력 번호.

sqrt (b)의 계산을 없애기 위해 위의 것을 최적화 할 수 있습니다 (JDunkerly의 답과 비슷 함).

또는 a와 b의 제곱근을 계산하지 않으시겠습니까?

---

이진 검색과 비슷한 방법을 사용하여 제곱근을 완전히 계산할 필요가 없습니다.

당신은 N에 대한 추측으로 시작, N = 1과는 < = N < B, 중지 할 수 있는지 생각해 N ²

계산한다.

n < a < b이면 추측 n을 두 배로 늘립니다. < b < n이면 현재 + 이전 추측의 평균에 가깝게 만듭니다.

이것은 O (logb) 시간입니다.

Answer 3

당신은 그것의 단순성 당신이 당신의 일을 시작하는 것과 같습니다이 불평등이 있기 때문에, 두 제곱근을 계산 받아 들일 것입니다 경우

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

따라서, floor(sqrt(a)) != floor(sqrt(b)) 경우, floor(sqrt(b)) - 1이 같은 n이 보장됩니다.

Answer 4

1. 는 낮은 숫자의 제곱근을 가져 와서 라운드까지
2. 광장 높은 숫자의 뿌리와 그 아래
3. 1가 낮거나 2와 동일한 경우는 라운드를 얻을 완벽한 정사각형이있을 것

Answer 5

낮은 숫자의 제곱근을 가져옵니다. 이것이 정수이면 당신은 끝난다. 그렇지 않으면 숫자를 반올림하고 제곱하십시오. 이것이 b보다 작 으면 사실입니다.

이 방법으로 한 개의 제곱근 만 계산하면됩니다.

a가 b와 같은 문제를 피하려면 먼저 그 점을 확인해야합니다. 이 경우는 항상 거짓이므로

Answer 6

한 가지 방법은 뉴턴의 방법을 사용하여 b의 integer square root을 찾는 것입니다. 그런 다음 해당 숫자가 해당 범위에 속하는지 확인할 수 있습니다. 나는 단순히 제곱근 함수를 호출하는 것보다 빠르다는 것을 의심하지 않지만, 그것은 확실히 더 재미있다 :

JDunkerley의 좋은 솔루션 (+1), 테스트 할 필요가 가능한 개선이있을 수 있습니다뿐만 아니라

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

integer square roots을 사용하여 정수 제곱근 계산

Answer 8

왜 제곱근을 완전히 피하려고합니까? 이 문제를 해결하는 가장 효율적인 방법을 배우기 전에도 2 개의 제곱근만을 요구하는 방법을 보았습니다. 그것은 O (1) 시간에 완료되었으므로, 당신이 할 수있는 개선이 생각하면 컴퓨팅 시간을 절약 할 수있는 것보다 시간이 더 많이 걸릴 것으로 생각됩니다. 내가 잘못?