큰 숫자가 완전제곱수인지 효율적으로 판단할 수 있는 방법은 무엇입니까?

프로그램 시작 시 일부 사전 필터링을 수행하여 작업 속도를 높이고 음수, 마지막 4자리 숫자가 0인 숫자 등 명백히 정사각형이 아닌 숫자를 필터링합니다. 및 특정 요구 사항을 충족하는 마지막 2자리 숫자(10진수 5 또는 8)입니다. 0의 경우 제곱수라고 생각하세요.

사전 필터를 통과한 숫자의 경우 몫이 홀수가 될 때까지 (이진 검색 방식으로) 2의 거듭제곱으로 나눕니다. 마지막 단계는 헨젤의 보조정리와 유사한 방법을 사용하여 제곱근을 근사화하는 것입니다. 내부 루프는 sqrt(mod 8192)의 근사값을 제공하는 시작 배열에 의해 제공된 초기 값으로 시작됩니다. 이 근사치는 속도를 향상시키기 위해 비트별 트릭을 사용하는 연속 계산을 통해 지속적으로 개선됩니다.

이 방법의 대략적인 구조는 다음과 같습니다.

명백한 제곱수가 아닌 숫자를 제거하기 위한 사전 필터입니다.

나머지 모듈로 255가 제곱수인지 확인하세요.

1. 2의 거듭제곱으로 나눕니다.
2. 헨젤 정리의 변형을 사용하여 대략적인 제곱근을 계산합니다.
3. 이 알고리즘의 작성자는 다른 방법보다 35% 더 빠르게 실행된다고 주장합니다.

위 내용은 큰 숫자가 완전제곱수인지 효율적으로 판단할 수 있는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!