정수의 제곱근이 정수인지 확인하는 가장 빠른 방법은 무엇입니까?

정수의 제곱근이 정수인지 확인하는 가장 빠른 방법

문제 설명

다음을 찾고 있습니다. 긴 정수가 완전제곱수인지 확인하는 가장 빠른 방법(즉, 제곱근이 다른 정수임):

1. 내장된 Math.sqrt() 함수를 이용해서 했는데, 혹시 할 수 있는 방법이 있는지 궁금합니다. 정수 필드를 사용하여 속도를 높입니다.
   

2. 조회 테이블을 유지하는 것은 비실용적입니다(제곱이 2⁶³보다 작은 정수가 대략 2^31.5개 있기 때문입니다).

지금 제가 하는 매우 간단하고 간단한 방법은 다음과 같습니다.

{<br> if (n < 0)</p><div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:php;toolbar:false">return false;

로그인 후 복사

long tst = (long)(Math.sqrt(n) 0.5);
return tst*tst == n;
}

_{참고: 저는 이 함수를 많은 프로젝트 오일러 문제에 사용합니다. 따라서 앞으로 이 코드에 대한 유지 관리는 없을 것입니다. 그리고 이러한 미세 최적화는 실제로 차이를 만들 수 있습니다. 왜냐하면 문제의 일부는 각 알고리즘을 완료하는 데 1분도 채 걸리지 않는 반면, 일부 문제에서는 이 함수를 수백만 번 호출해야 하기 때문입니다.}

---

저는 이 문제에 대해 다양한 해결책을 시도했습니다:

• 철저한 테스트 후에 적어도 내 컴퓨터에서는 Math.sqrt()의 결과에 0.5를 추가하는 것이 불필요하다는 것을 알았습니다.


• 빠른 역제곱근은 Math.sqrt()보다 빠르지만 n >= 410881에 대해 잘못된 결과를 제공합니다. 그러나 BobbyShaftoe가 제안한 것처럼 n
  
• Newton의 방법은 Math.sqrt()보다 훨씬 느립니다. 이는 아마도 Math.sqrt()가 Newton의 방법과 유사한 것을 사용하지만 하드웨어로 구현되므로 Java보다 훨씬 빠르기 때문일 것입니다. 또한 Newton 방법에서는 여전히 배정밀도 부동 소수점 숫자를 사용해야 합니다.
양의 64비트 부호 있는 정수), Math.sqrt()보다 느립니다.

이진 검색은 훨씬 더 느립니다. 이진 검색에서는 64비트 숫자의 제곱근을 찾기 위해 평균 16번의 패스가 필요하기 때문에 이는 의미가 있습니다.

John의 테스트에 따르면 or 문을 사용하는 것이 C에서 스위치를 사용하는 것보다 빠르지만 Java와 C#에서는 or와 스위치 사이에 차이가 없는 것 같습니다.

또한 조회 테이블(64개 부울의 개인 정적 배열)을 만들어 보았습니다. 그런 다음 스위치나 문을 사용하는 대신 if(lookup[(int)(n&0x3F)]) { test } else return false;라고 말하면 됩니다. 놀랍게도 이 방법은 (약간) 더 느립니다. 이는 Java에서 배열 범위를 확인하기 때문입니다.

위 내용은 정수의 제곱근이 정수인지 확인하는 가장 빠른 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!