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

질문자 :Community Wiki

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

1. Math.sqrt() 함수를 사용하여 쉬운 방법으로 수행했지만 정수 전용 도메인으로 제한하여 더 빠르게 수행할 수 있는 방법이 있는지 궁금합니다.
2. 조회 테이블을 유지 관리하는 것은 비실용적입니다(제곱이 2 ^{63 보다 작은 정수가 약 2 31.5} 개 있기 때문에).

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

 public final static boolean isPerfectSquare(long n) { if (n < 0) return false; long tst = (long)(Math.sqrt(n) + 0.5); return tst*tst == n; }

_{참고: 많은 프로젝트 오일러 문제에서 이 기능을 사용하고 있습니다. 따라서 다른 누구도 이 코드를 유지 관리할 필요가 없습니다. 그리고 이러한 종류의 미세 최적화는 실제로 차이를 만들 수 있습니다. 문제의 일부는 모든 알고리즘을 1분 이내에 수행하는 것이고 이 함수는 일부 문제에서 수백만 번 호출해야 하기 때문입니다.}

---

나는 문제에 대한 다른 해결책을 시도했습니다.

• 철저한 테스트 후에 0.5 를 추가할 필요가 없다는 것을 발견했습니다. 적어도 제 컴퓨터에서는 그렇지 않습니다.
• 빠른 역제곱근 은 더 빠르지만 n >= 410881에 대해 잘못된 결과를 제공했습니다. 그러나 BobbyShaftoe 에서 제안한 대로 n < 410881에 대해 FISR 핵을 사용할 수 있습니다.
• Newton의 방법은 Math.sqrt() 보다 약간 느렸습니다. Math.sqrt() 가 Newton의 방법과 유사한 것을 사용하기 때문일 것입니다. 그러나 하드웨어에서 구현되어 Java보다 훨씬 빠릅니다. 또한 Newton의 방법은 여전히 복식을 사용해야 했습니다.
• 정수 수학만 포함되도록 몇 가지 트릭을 사용하는 수정된 Newton의 방법은 오버플로를 피하기 위해 몇 가지 해킹이 필요했으며(이 함수가 모든 양의 부호 있는 64비트 정수에서 작동하기를 원합니다) 여전히 Math.sqrt() .
• 바이너리 촙은 더 느렸습니다. 이것은 이진 절단이 64비트 숫자의 제곱근을 찾는 데 평균 16번의 패스를 필요로 하기 때문에 의미가 있습니다.
• John의 테스트에 따르면 or switch 사용하는 것보다 C++에서 더 빠르지 or 와 switch 사이에 차이가 없는 것으로 보입니다.
• 또한 조회 테이블(64개 부울 값의 개인 정적 배열)을 만들려고 했습니다. 그런 다음 switch 또는 or 문 if(lookup[(int)(n&0x3F)]) { test } else return false; . 놀랍게도 이것은 (약간) 더 느렸습니다. Java에서 배열 경계를 확인 하기 때문입니다.

적어도 내 CPU(x86) 및 프로그래밍 언어(C/C++)에서 6비트+Carmack+sqrt 코드보다 ~35% 더 빠르게 작동하는 방법을 알아냈습니다. 결과는 다를 수 있습니다. 특히 Java 요소가 어떻게 작동할지 모르기 때문입니다.

내 접근 방식은 세 가지입니다.

1. 첫째, 명백한 답변을 걸러냅니다. 여기에는 음수와 마지막 4비트가 포함됩니다. (나는 마지막 6개를 보는 것이 도움이 되지 않는다는 것을 알았다.) 나는 또한 0에 대해 yes라고 대답한다. (아래 코드를 읽을 때 내 입력이 int64 x 임을 주목하라.)

    if( x < 0 || (x&2) || ((x & 7) == 5) || ((x & 11) == 8) ) return false; if( x == 0 ) return true;

2. 다음으로, 그것이 제곱 모듈로 255 = 3 * 5 * 17인지 확인하십시오. 그것은 3개의 고유한 소수의 곱이기 때문에 나머지 mod 255의 약 1/8만이 제곱입니다. 그러나 내 경험상 모듈로 연산자(%)를 호출하면 얻는 이점보다 비용이 더 많이 들기 때문에 255 = 2^8-1과 관련된 비트 트릭을 사용하여 나머지를 계산합니다. (좋든 나쁘든, 나는 단어에서 개별 바이트를 읽는 트릭을 사용하지 않고 비트 및 시프트만 사용합니다.)

    int64 y = x; y = (y & 4294967295LL) + (y >> 32); y = (y & 65535) + (y >> 16); y = (y & 255) + ((y >> 8) & 255) + (y >> 16); // At this point, y is between 0 and 511. More code can reduce it farther.

Community Wiki

나는 파티에 꽤 늦었지만 더 나은 답변을 제공하기를 바랍니다. 더 짧고 (내 벤치 마크 가 정확 하다고 가정) 훨씬 빠릅니다 .

 long goodMask; // 0xC840C04048404040 computed below { for (int i=0; i<64; ++i) goodMask |= Long.MIN_VALUE >>> (i*i); } public boolean isSquare(long x) { // This tests if the 6 least significant bits are right. // Moving the to be tested bit to the highest position saves us masking. if (goodMask << x >= 0) return false; final int numberOfTrailingZeros = Long.numberOfTrailingZeros(x); // Each square ends with an even number of zeros. if ((numberOfTrailingZeros & 1) != 0) return false; x >>= numberOfTrailingZeros; // Now x is either 0 or odd. // In binary each odd square ends with 001. // Postpone the sign test until now; handle zero in the branch. if ((x&7) != 1 | x <= 0) return x == 0; // Do it in the classical way. // The correctness is not trivial as the conversion from long to double is lossy! final long tst = (long) Math.sqrt(x); return tst * tst == x; }

첫 번째 테스트는 대부분의 비정사각형을 빠르게 포착합니다. long으로 포장된 64개 항목 테이블을 사용하므로 배열 액세스 비용(간접 및 경계 검사)이 없습니다. 균일하게 임의의 long 의 경우 여기에서 끝날 확률이 81.25%입니다.

두 번째 테스트는 인수분해에서 2가 홀수인 모든 숫자를 포착합니다. Long.numberOfTrailingZeros 메서드는 단일 i86 명령어에 JIT를 적용하므로 매우 빠릅니다.

후행 0을 삭제한 후 세 번째 테스트는 이진법에서 011, 101 또는 111로 끝나는 숫자를 처리합니다. 이 숫자는 완전제곱수가 아닙니다. 또한 음수와 0도 처리합니다.

최종 테스트는 double 산술로 대체됩니다. double 에는 가수가 53비트만 있으므로 long 에서 double 로의 변환에는 큰 값에 대한 반올림이 포함됩니다. 그럼에도 불구하고 테스트는 정확합니다( 증명 이 잘못된 경우 제외).

mod255 아이디어를 통합하려는 시도는 성공하지 못했습니다.

Community Wiki

벤치마킹을 해야 합니다. 최고의 알고리즘은 입력 분포에 따라 달라집니다.

알고리즘이 거의 최적일 수 있지만 제곱근 루틴을 호출하기 전에 몇 가지 가능성을 배제하기 위해 빠른 검사를 수행할 수 있습니다. 예를 들어, 비트 단위 "and"를 수행하여 16진수로 된 숫자의 마지막 자릿수를 확인합니다. 완벽한 제곱은 16진법에서 0, 1, 4 또는 9로만 끝날 수 있으므로 입력의 75%(균일하게 분포되어 있다고 가정)에 대해 매우 빠른 비트 트위들링에 대한 대가로 제곱근 호출을 피할 수 있습니다.

Kip은 16진수 트릭을 구현하는 다음 코드를 벤치마킹했습니다. 1에서 100,000,000까지의 숫자를 테스트할 때 이 코드는 원본보다 두 배 빠르게 실행되었습니다.

 public final static boolean isPerfectSquare(long n) { if (n < 0) return false; switch((int)(n & 0xF)) { case 0: case 1: case 4: case 9: long tst = (long)Math.sqrt(n); return tst*tst == n; default: return false; } }

C++에서 유사한 코드를 테스트했을 때 실제로 원본보다 느리게 실행되었습니다. 그러나 switch 문을 제거하면 16진수 트릭이 다시 한 번 코드를 두 배 빠르게 만듭니다.

 int isPerfectSquare(int n) { int h = n & 0xF; // h is the last hex "digit" if (h > 9) return 0; // Use lazy evaluation to jump out of the if statement as soon as possible if (h != 2 && h != 3 && h != 5 && h != 6 && h != 7 && h != 8) { int t = (int) floor( sqrt((double) n) + 0.5 ); return t*t == n; } return 0; }

switch 문을 제거해도 C# 코드에는 거의 영향을 미치지 않았습니다.

Community Wiki

수치해석 과정에서 보낸 끔찍한 시간에 대해 생각하고 있었습니다.

그리고 나서 Quake 소스 코드에서 'net' 주위를 돌고 있는 이 함수가 있었던 것으로 기억합니다.

 float Q_rsqrt( float number ) { long i; float x2, y; const float threehalfs = 1.5F; x2 = number * 0.5F; y = number; i = * ( long * ) &y; // evil floating point bit level hacking i = 0x5f3759df - ( i >> 1 ); // wtf? y = * ( float * ) &i; y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration // y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed #ifndef Q3_VM #ifdef __linux__ assert( !isnan(y) ); // bk010122 - FPE? #endif #endif return y; }

기본적으로 뉴턴의 근사 함수를 사용하여 제곱근을 계산합니다(정확한 이름을 기억할 수 없음).

그것은 사용 가능해야 하고 더 빠를 수도 있습니다. 그것은 경이로운 id 소프트웨어 게임 중 하나에서 나온 것입니다!

C++로 작성되었지만 아이디어를 얻은 후에는 Java에서 동일한 기술을 재사용하는 것이 너무 어렵지 않아야 합니다.

나는 원래 그것을 찾았습니다: http://www.codemaestro.com/reviews/9

wikipedia에 설명된 Newton의 방법: http://en.wikipedia.org/wiki/Newton%27s_method

작동 방식에 대한 자세한 설명을 보려면 링크를 따라갈 수 있지만 그다지 신경 쓰지 않는다면 블로그를 읽고 수치 분석 과정을 수강하면서 대략적으로 기억나는 내용입니다.

• * (long*) &y 는 기본적으로 long으로의 빠른 변환 함수이므로 정수 연산이 원시 바이트에 적용될 수 있습니다.
• 0x5f3759df - (i >> 1); line은 근사 함수에 대해 미리 계산된 시드 값입니다.
• * (float*) &i 는 값을 다시 부동 소수점으로 변환합니다.
• y = y * ( threehalfs - ( x2 * y * y ) ) 라인은 기본적으로 함수에 대해 값을 다시 반복합니다.

근사 함수는 결과에 대해 함수를 반복할수록 더 정확한 값을 제공합니다. Quake의 경우 한 번의 반복으로 "충분히 좋습니다". 그러나 그것이 당신에게 적합하지 않다면... 필요한 만큼 반복을 추가할 수 있습니다.

이것은 순진한 제곱근에서 수행되는 나누기 연산의 수를 2로 간단한 나누기(실제로는 * 0.5F 곱하기 연산)로 줄이고 대신 몇 개의 고정된 곱셈 연산으로 대체하기 때문에 더 빨라야 합니다.

Community Wiki

더 빠르거나 정확한지 확실하지 않지만 John Carmack의 Magical Square Root 알고리즘을 사용하여 제곱근을 더 빨리 풀 수 있습니다. 가능한 모든 32비트 정수에 대해 이것을 쉽게 테스트하고 근사치일 뿐이므로 실제로 올바른 결과를 얻었는지 확인할 수 있습니다. 그러나 지금 생각해보면 복식을 사용하는 것도 근사하므로 그것이 어떻게 작용할지 잘 모르겠습니다.

Community Wiki

"올바른" 제곱근을 찾기 위해 이진 절단을 수행하면 얻은 값이 다음과 같이 말할 수 있을 만큼 가까운지 상당히 쉽게 감지할 수 있습니다.

 (n+1)^2 = n^2 + 2n + 1 (n-1)^2 = n^2 - 2n + 1

n^2 를 계산하면 옵션은 다음과 같습니다.

• n^2 = target : 완료, true 반환
• n^2 + 2n + 1 > target > n^2 : 가깝지만 완벽하지 않음: return false
• n^2 - 2n + 1 < target < n^2 : 동일
• target < n^2 - 2n + 1 : 더 낮은 n
• target > n^2 + 2n + 1 : 더 높은 n

(죄송합니다. 이것은 현재 추측으로 n 을 사용하고 매개변수의 target

이것이 더 빠를지 여부는 모르겠지만 시도해 볼 가치가 있습니다.

(2^x)^2 = 2^(2x) 정수의 전체 범위를 취할 필요가 없으므로 일단 대상에서 최상위 세트 비트를 찾으면(일 수 있습니다 약간의 트릭으로 완료; 나는 정확히 어떻게) 잠재적인 답변의 범위를 빠르게 얻을 수 있는지 잊어버렸습니다. 순진한 바이너리 절단은 여전히 최대 31 또는 32번의 반복만 수행해야 합니다.

Community Wiki

이 스레드에서 여러 알고리즘에 대한 자체 분석을 실행하고 몇 가지 새로운 결과를 도출했습니다. 이 답변의 편집 기록에서 오래된 결과를 볼 수 있지만 내가 실수를 했고 가깝지 않은 여러 알고리즘을 분석하는 데 시간을 낭비했기 때문에 정확하지 않습니다. 그러나 여러 다른 답변에서 교훈을 얻은 결과 이제 이 스레드의 "승자"를 압도하는 두 가지 알고리즘이 있습니다. 다른 사람들과 다르게 내가 하는 핵심은 다음과 같습니다.

 // This is faster because a number is divisible by 2^4 or more only 6% of the time // and more than that a vanishingly small percentage. while((x & 0x3) == 0) x >>= 2; // This is effectively the same as the switch-case statement used in the original // answer. if((x & 0x7) != 1) return false;

그러나 대부분의 경우 하나 또는 두 개의 매우 빠른 명령을 추가하는 이 간단한 행은 switch-case 문을 하나의 if 문으로 크게 단순화합니다. 그러나 테스트된 숫자 중 많은 수가 2의 제곱인 요인이 상당한 경우 런타임에 추가될 수 있습니다.

아래 알고리즘은 다음과 같습니다.

• 인터넷 - Kip의 게시된 답변
• Durron - 원 패스 답변을 기본으로 사용하여 수정한 답변
• DurronTwo - 2단계 답변(@JohnnyHeggheim 작성)을 사용하여 수정한 답변과 약간의 다른 수정 사항이 있습니다.

Math.abs(java.util.Random.nextLong()) 사용하여 숫자를 생성한 경우의 샘플 런타임입니다.

 0% Scenario{vm=java, trial=0, benchmark=Internet} 39673.40 ns; ?=378.78 ns @ 3 trials 33% Scenario{vm=java, trial=0, benchmark=Durron} 37785.75 ns; ?=478.86 ns @ 10 trials 67% Scenario{vm=java, trial=0, benchmark=DurronTwo} 35978.10 ns; ?=734.10 ns @ 10 trials benchmark us linear runtime Internet 39.7 ============================== Durron 37.8 ============================ DurronTwo 36.0 =========================== vm: java trial: 0

다음은 처음 백만 개의 long에서만 실행되는 경우의 샘플 런타임입니다.

 0% Scenario{vm=java, trial=0, benchmark=Internet} 2933380.84 ns; ?=56939.84 ns @ 10 trials 33% Scenario{vm=java, trial=0, benchmark=Durron} 2243266.81 ns; ?=50537.62 ns @ 10 trials 67% Scenario{vm=java, trial=0, benchmark=DurronTwo} 3159227.68 ns; ?=10766.22 ns @ 3 trials benchmark ms linear runtime Internet 2.93 =========================== Durron 2.24 ===================== DurronTwo 3.16 ============================== vm: java trial: 0

보시다시피 DurronTwo 는 마법의 트릭을 매우 자주 사용하기 때문에 큰 입력에 더 적합하지만 숫자가 훨씬 작기 때문에 Math.sqrt 한편, 더 간단한 Durron 은 처음 백만 개의 숫자에서 4로 여러 번 나눌 필요가 없기 때문에 큰 승자입니다.

여기 Durron .

 public final static boolean isPerfectSquareDurron(long n) { if(n < 0) return false; if(n == 0) return true; long x = n; // This is faster because a number is divisible by 16 only 6% of the time // and more than that a vanishingly small percentage. while((x & 0x3) == 0) x >>= 2; // This is effectively the same as the switch-case statement used in the original // answer. if((x & 0x7) == 1) { long sqrt; if(x < 410881L) { int i; float x2, y; x2 = x * 0.5F; y = x; i = Float.floatToRawIntBits(y); i = 0x5f3759df - ( i >> 1 ); y = Float.intBitsToFloat(i); y = y * ( 1.5F - ( x2 * y * y ) ); sqrt = (long)(1.0F/y); } else { sqrt = (long) Math.sqrt(x); } return sqrt*sqrt == x; } return false; }

그리고 DurronTwo

 public final static boolean isPerfectSquareDurronTwo(long n) { if(n < 0) return false; // Needed to prevent infinite loop if(n == 0) return true; long x = n; while((x & 0x3) == 0) x >>= 2; if((x & 0x7) == 1) { long sqrt; if (x < 41529141369L) { int i; float x2, y; x2 = x * 0.5F; y = x; i = Float.floatToRawIntBits(y); //using the magic number from //http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf //since it more accurate i = 0x5f375a86 - (i >> 1); y = Float.intBitsToFloat(i); y = y * (1.5F - (x2 * y * y)); y = y * (1.5F - (x2 * y * y)); //Newton iteration, more accurate sqrt = (long) ((1.0F/y) + 0.2); } else { //Carmack hack gives incorrect answer for n >= 41529141369. sqrt = (long) Math.sqrt(x); } return sqrt*sqrt == x; } return false; }

그리고 내 벤치마크 하네스: (Google 캘리퍼스 0.1-rc5 필요)

 public class SquareRootBenchmark { public static class Benchmark1 extends SimpleBenchmark { private static final int ARRAY_SIZE = 10000; long[] trials = new long[ARRAY_SIZE]; @Override protected void setUp() throws Exception { Random r = new Random(); for (int i = 0; i < ARRAY_SIZE; i++) { trials[i] = Math.abs(r.nextLong()); } } public int timeInternet(int reps) { int trues = 0; for(int i = 0; i < reps; i++) { for(int j = 0; j < ARRAY_SIZE; j++) { if(SquareRootAlgs.isPerfectSquareInternet(trials[j])) trues++; } } return trues; } public int timeDurron(int reps) { int trues = 0; for(int i = 0; i < reps; i++) { for(int j = 0; j < ARRAY_SIZE; j++) { if(SquareRootAlgs.isPerfectSquareDurron(trials[j])) trues++; } } return trues; } public int timeDurronTwo(int reps) { int trues = 0; for(int i = 0; i < reps; i++) { for(int j = 0; j < ARRAY_SIZE; j++) { if(SquareRootAlgs.isPerfectSquareDurronTwo(trials[j])) trues++; } } return trues; } } public static void main(String... args) { Runner.main(Benchmark1.class, args); } }

업데이트: 일부 시나리오에서는 더 빠르고 다른 시나리오에서는 더 느린 새로운 알고리즘을 만들었습니다. 다른 입력을 기반으로 다른 벤치마크를 얻었습니다. 모듈로 0xFFFFFF = 3 x 3 x 5 x 7 x 13 x 17 x 241 을 계산하면 제곱이 될 수 없는 숫자의 97.82%를 제거할 수 있습니다. 이것은 5개의 비트 연산으로 한 줄에서 (일종의) 수행될 수 있습니다.

 if (!goodLookupSquares[(int) ((n & 0xFFFFFFl) + ((n >> 24) & 0xFFFFFFl) + (n >> 48))]) return false;

결과 인덱스는 1) 잔여물, 2) 잔여물 + 0xFFFFFF 또는 3) 잔여물 + 0x1FFFFFE 입니다. 0xFFFFFF 대한 조회 테이블이 필요합니다(이 경우 ASCII 텍스트 십진수로 저장되며 최적은 아니지만 ByteBuffer 등으로 명확하게 개선할 수 있습니다. 하지만 사전 계산이므로 별로 중요하지 않습니다. 여기에서 파일을 찾 거나 직접 생성할 수 있습니다.

 public final static boolean isPerfectSquareDurronThree(long n) { if(n < 0) return false; if(n == 0) return true; long x = n; while((x & 0x3) == 0) x >>= 2; if((x & 0x7) == 1) { if (!goodLookupSquares[(int) ((n & 0xFFFFFFl) + ((n >> 24) & 0xFFFFFFl) + (n >> 48))]) return false; long sqrt; if(x < 410881L) { int i; float x2, y; x2 = x * 0.5F; y = x; i = Float.floatToRawIntBits(y); i = 0x5f3759df - ( i >> 1 ); y = Float.intBitsToFloat(i); y = y * ( 1.5F - ( x2 * y * y ) ); sqrt = (long)(1.0F/y); } else { sqrt = (long) Math.sqrt(x); } return sqrt*sqrt == x; } return false; }

다음과 같이 boolean 배열에 로드합니다.

 private static boolean[] goodLookupSquares = null; public static void initGoodLookupSquares() throws Exception { Scanner s = new Scanner(new File("24residues_squares.txt")); goodLookupSquares = new boolean[0x1FFFFFE]; while(s.hasNextLine()) { int residue = Integer.valueOf(s.nextLine()); goodLookupSquares[residue] = true; goodLookupSquares[residue + 0xFFFFFF] = true; goodLookupSquares[residue + 0x1FFFFFE] = true; } s.close(); }

예제 런타임. 내가 실행한 모든 시험에서 Durron (버전 1)을 이겼습니다.

 0% Scenario{vm=java, trial=0, benchmark=Internet} 40665.77 ns; ?=566.71 ns @ 10 trials 33% Scenario{vm=java, trial=0, benchmark=Durron} 38397.60 ns; ?=784.30 ns @ 10 trials 67% Scenario{vm=java, trial=0, benchmark=DurronThree} 36171.46 ns; ?=693.02 ns @ 10 trials benchmark us linear runtime Internet 40.7 ============================== Durron 38.4 ============================ DurronThree 36.2 ========================== vm: java trial: 0

Community Wiki

Newton의 방법 을 사용하여 Integer Square Root 를 계산한 다음 현재 솔루션에서와 같이 이 숫자를 제곱하고 확인하는 것이 훨씬 빠릅니다. Newton의 방법은 다른 답변에서 언급한 Carmack 솔루션의 기초입니다. 근의 정수 부분에만 관심이 있으므로 근사 알고리즘을 더 빨리 중지할 수 있으므로 더 빠른 답을 얻을 수 있어야 합니다.

시도할 수 있는 또 다른 최적화: 숫자의 디지털 근 이 1, 4, 7 또는 9로 끝나지 않으면 숫자는 완전제곱수가 아닙니다. 이것은 더 느린 제곱근 알고리즘을 적용하기 전에 입력의 60%를 제거하는 빠른 방법으로 사용할 수 있습니다.

Community Wiki

이 함수가 모든 양의 64비트 부호 있는 정수와 함께 작동하기를 원합니다.

Math.sqrt() 는 입력 매개변수로 double을 사용하므로 2^53 보다 큰 정수에 대해서는 정확한 결과를 얻을 수 없습니다.

Community Wiki

기록을 위해 또 다른 접근 방식은 소수 분해를 사용하는 것입니다. 분해의 모든 요인이 짝수이면 그 수는 완전제곱수입니다. 따라서 원하는 것은 숫자가 소수의 제곱의 곱으로 분해될 수 있는지 확인하는 것입니다. 물론 그러한 분해가 있는지 확인하기 위해 이러한 분해를 얻을 필요는 없습니다.

먼저 2^32보다 작은 소수의 제곱표를 만듭니다. 이것은 이 한계까지의 모든 정수의 표보다 훨씬 작습니다.

솔루션은 다음과 같습니다.

 boolean isPerfectSquare(long number) { if (number < 0) return false; if (number < 2) return true; for (int i = 0; ; i++) { long square = squareTable[i]; if (square > number) return false; while (number % square == 0) { number /= square; } if (number == 1) return true; } }

좀 신비로운 것 같아요. 그것이 하는 일은 모든 단계에서 소수의 제곱이 입력 숫자를 나누는지 확인하는 것입니다. 그렇다면 가능한 한 숫자를 제곱으로 나누어 소수 분해에서 이 제곱을 제거합니다. 이 과정을 거쳐 1이 되면 입력된 숫자는 소수의 제곱을 분해한 것입니다. 제곱이 숫자 자체보다 커지면 이 제곱이나 더 큰 제곱이 이를 나눌 수 없으므로 숫자는 소수의 제곱의 분해가 될 수 없습니다.

오늘날의 sqrt가 하드웨어에서 수행되고 여기서 소수를 계산해야 할 필요성을 감안할 때 이 솔루션이 훨씬 느린 것 같습니다. 그러나 그의 대답에서 mrzl이 말했듯이 2^54 이상에서 작동하지 않는 sqrt를 사용한 솔루션보다 더 나은 결과를 제공해야 합니다.

Community Wiki

정수 문제는 정수 솔루션을 받을 자격이 있습니다. 따라서

(음수가 아닌) 정수에 대해 이진 검색을 수행하여 t**2 <= n 되는 가장 큰 정수 t 를 찾습니다. 그런 다음 r**2 = n 인지 정확히 테스트합니다. 이것은 O(log n) 시간이 걸립니다.

집합이 무제한이기 때문에 양의 정수를 이진 검색하는 방법을 모르는 경우 쉽습니다. f(t) = t**2 - n )를 2의 거듭제곱으로 계산하여 시작합니다. 양수로 바뀌면 상한선을 찾은 것입니다. 그런 다음 표준 이진 검색을 수행할 수 있습니다.

Community Wiki

d 자리는 특정 값만 취할 수 있다는 것이 지적되었습니다. n 의 마지막 d 자리( b 밑수)는 n b d 로 나눈 나머지와 같습니다. 즉. C 표기법 n % pow(b, d) .

m 으로 일반화될 수 있습니다. n % m 은 완전제곱수에서 일부 백분율을 배제하는 데 사용할 수 있습니다. 현재 사용하고 있는 계수는 64로 12를 허용합니다. 나머지의 19%는 가능한 제곱입니다. 약간의 코딩으로 계수 110880을 찾았습니다. 이 계수는 2016만 허용합니다. 나머지의 1.8%는 가능한 제곱입니다. 따라서 모듈러스 연산(예: 나눗셈) 및 테이블 조회 대 컴퓨터의 제곱근 비용에 따라 이 모듈러스를 사용하는 것이 더 빠를 수 있습니다.

그런데 Java에 조회 테이블에 대한 압축된 비트 배열을 저장할 수 있는 방법이 있다면 사용하지 마십시오. 110880 32비트 단어는 요즘 RAM이 많지 않으며 기계어를 가져오는 것이 단일 비트를 가져오는 것보다 빠를 것입니다.

Community Wiki

maaartinus의 솔루션을 다음과 같이 단순화하면 런타임에서 몇 퍼센트 포인트를 줄이는 것처럼 보이지만 신뢰할 수 있는 벤치마크를 생성하기 위한 벤치마킹에는 능숙하지 않습니다.

 long goodMask; // 0xC840C04048404040 computed below { for (int i=0; i<64; ++i) goodMask |= Long.MIN_VALUE >>> (i*i); } public boolean isSquare(long x) { // This tests if the 6 least significant bits are right. // Moving the to be tested bit to the highest position saves us masking. if (goodMask << x >= 0) return false; // Remove an even number of trailing zeros, leaving at most one. x >>= (Long.numberOfTrailingZeros(x) & (-2); // Repeat the test on the 6 least significant remaining bits. if (goodMask << x >= 0 | x <= 0) return x == 0; // Do it in the classical way. // The correctness is not trivial as the conversion from long to double is lossy! final long tst = (long) Math.sqrt(x); return tst * tst == x; }

첫 번째 테스트를 생략하는 방법을 확인하는 것이 좋습니다.

 if (goodMask << x >= 0) return false;

성능에 영향을 미칠 것입니다.

Community Wiki

성능을 위해 매우 자주 몇 가지 타협을 해야 합니다. 다른 사람들은 다양한 방법을 표현했지만 Carmack의 hack은 N의 특정 값까지 더 빨랐다고 언급했습니다. 그런 다음 "n"을 확인하고 해당 숫자 N보다 작으면 Carmack의 hack을 사용하고, 그렇지 않으면 설명된 다른 방법을 사용하십시오. 여기 답변에서.

Community Wiki

이것은 이 스레드의 다른 사람들이 제안한 기술의 조합을 사용하여 내가 생각해낼 수 있는 가장 빠른 Java 구현입니다.

• Mod-256 테스트
• 정확하지 않은 mod-3465 테스트(일부 가양성 비용으로 정수 나누기 방지)
• 부동 소수점 제곱근, 반올림 및 입력 값과 비교

또한 이러한 수정을 시도했지만 성능에 도움이 되지 않았습니다.

• 추가 mod-255 테스트
• 입력 값을 4의 거듭제곱으로 나누기
• 빠른 역제곱근(N의 높은 값에 대해 작동하려면 하드웨어 제곱근 기능보다 느리게 만들기에 충분한 3번의 반복이 필요합니다.)

 public class SquareTester { public static boolean isPerfectSquare(long n) { if (n < 0) { return false; } else { switch ((byte) n) { case -128: case -127: case -124: case -119: case -112: case -111: case -103: case -95: case -92: case -87: case -79: case -71: case -64: case -63: case -60: case -55: case -47: case -39: case -31: case -28: case -23: case -15: case -7: case 0: case 1: case 4: case 9: case 16: case 17: case 25: case 33: case 36: case 41: case 49: case 57: case 64: case 65: case 68: case 73: case 81: case 89: case 97: case 100: case 105: case 113: case 121: long i = (n * INV3465) >>> 52; if (! good3465[(int) i]) { return false; } else { long r = round(Math.sqrt(n)); return r*r == n; } default: return false; } } } private static int round(double x) { return (int) Double.doubleToRawLongBits(x + (double) (1L << 52)); } /** 3465<sup>-1</sup> modulo 2<sup>64</sup> */ private static final long INV3465 = 0x8ffed161732e78b9L; private static final boolean[] good3465 = new boolean[0x1000]; static { for (int r = 0; r < 3465; ++ r) { int i = (int) ((r * r * INV3465) >>> 52); good3465[i] = good3465[i+1] = true; } } }

Community Wiki

처음부터 N의 2승 부분을 제거해야 합니다.

2nd Edit 아래의 m에 대한 마법의 표현은 다음과 같아야 합니다.

 m = N - (N & (N-1));

그리고 쓰여진 대로가 아니라

2차 수정 끝

 m = N & (N-1); // the lawest bit of N N /= m; byte = N & 0x0F; if ((m % 2) || (byte !=1 && byte !=9)) return false;

첫 번째 편집:

사소한 개선:

 m = N & (N-1); // the lawest bit of N N /= m; if ((m % 2) || (N & 0x07 != 1)) return false;

1차 수정 끝

이제 평소대로 계속하십시오. 이런 식으로 부동 소수점 부분에 도달할 때 2승 부분이 홀수(약 절반)인 모든 숫자를 이미 제거한 다음 남은 것의 1/8만 고려합니다. 즉, 숫자의 6%에서 부동 소수점 부분을 실행합니다.

Community Wiki

프로젝트 오일러는 태그에 언급되어 있으며 많은 문제는 숫자 확인이 필요합니다 >> 2^64 . 위에서 언급한 대부분의 최적화는 80바이트 버퍼로 작업할 때 쉽게 작동하지 않습니다.

나는 자바 BigInteger와 약간 수정된 Newton의 방법을 사용했는데, 이 방법은 정수에서 더 잘 작동합니다. 문제는 n^2-1 = (n-1)(n+1) 이기 때문에 n^2 가 n (n-1) 수렴되었고 최종 오차는 최종 제수보다 한 단계 아래에 있었고 알고리즘이 종료되었습니다. 오류를 계산하기 전에 원래 인수에 하나를 추가하면 쉽게 수정할 수 있습니다. (큐브 루트 등의 경우 2개 추가)

이 알고리즘의 좋은 특성 중 하나는 숫자가 완전제곱수인지 즉시 알 수 있다는 것입니다. Newton 방법의 최종 오류(수정 아님)는 0입니다. 간단한 수정을 통해 가장 가까운 정수 대신 floor(sqrt(x)) 를 빠르게 계산할 수도 있습니다. 이것은 여러 오일러 문제에 유용합니다.

Community Wiki

이것은 Ruby에서 이 질문에 맞게 특별히 조정된 이전 Marchant 계산기 알고리즘의 십진수에서 이진수로의 재작업입니다(죄송합니다. 참조가 없습니다).

 def isexactsqrt(v) value = v.abs residue = value root = 0 onebit = 1 onebit <<= 8 while (onebit < residue) onebit >>= 2 while (onebit > residue) while (onebit > 0) x = root + onebit if (residue >= x) then residue -= x root = x + onebit end root >>= 1 onebit >>= 2 end return (residue == 0) end

다음은 유사한 작업입니다(코딩 스타일/냄새 또는 투박한 O/O에 대해 저에게 투표하지 마십시오. 중요한 것은 알고리즘이며 C++은 제 모국어가 아닙니다). 이 경우 잔류물 == 0을 찾습니다.

 #include <iostream> using namespace std; typedef unsigned long long int llint; class ISqrt { // Integer Square Root llint value; // Integer whose square root is required llint root; // Result: floor(sqrt(value)) llint residue; // Result: value-root*root llint onebit, x; // Working bit, working value public: ISqrt(llint v = 2) { // Constructor Root(v); // Take the root }; llint Root(llint r) { // Resets and calculates new square root value = r; // Store input residue = value; // Initialise for subtracting down root = 0; // Clear root accumulator onebit = 1; // Calculate start value of counter onebit <<= (8*sizeof(llint)-2); // Set up counter bit as greatest odd power of 2 while (onebit > residue) {onebit >>= 2; }; // Shift down until just < value while (onebit > 0) { x = root ^ onebit; // Will check root+1bit (root bit corresponding to onebit is always zero) if (residue >= x) { // Room to subtract? residue -= x; // Yes - deduct from residue root = x + onebit; // and step root }; root >>= 1; onebit >>= 2; }; return root; }; llint Residue() { // Returns residue from last calculation return residue; }; }; int main() { llint big, i, q, r, v, delta; big = 0; big = (big-1); // Kludge for "big number" ISqrt b; // Make q sqrt generator for ( i = big; i > 0 ; i /= 7 ) { // for several numbers q = b.Root(i); // Get the square root r = b.Residue(); // Get the residue v = q*q+r; // Recalc original value delta = vi; // And diff, hopefully 0 cout << i << ": " << q << " ++ " << r << " V: " << v << " Delta: " << delta << "\n"; }; return 0; };

Community Wiki

sqrt 호출은 앞서 언급한 것처럼 완벽하게 정확하지는 않지만 속도 면에서 다른 답변을 날려버리지 않는다는 점은 흥미롭고 유익합니다. 결국, sqrt에 대한 어셈블리 언어 명령의 순서는 작습니다. 인텔에는 IEEE를 준수하지 않기 때문에 Java에서 사용하지 않는 하드웨어 명령이 있습니다.

그래서 느린 이유는 무엇입니까? Java는 실제로 JNI를 통해 C 루틴을 호출하고 있기 때문에 실제로 인라인으로 수행하는 것보다 느린 Java 서브루틴을 호출하는 것보다 그렇게 하는 것이 더 느립니다. 이것은 매우 성가신 일이며 Java는 더 나은 솔루션, 즉 필요한 경우 부동 소수점 라이브러리 호출을 구축해야 합니다. 오 글쎄.

C++에서는 모든 복잡한 대안이 속도를 잃을 것이라고 생각하지만 모두 확인하지는 않았습니다. 내가 한 일, 그리고 Java 사람들이 유용하다고 생각하는 것은 A. Rex가 제안한 특수 사례 테스트의 확장인 간단한 해킹입니다. 경계가 확인되지 않은 하나의 긴 값을 비트 배열로 사용하십시오. 그렇게하면 64 비트 부울 조회가 있습니다.

 typedef unsigned long long UVLONG UVLONG pp1,pp2; void init2() { for (int i = 0; i < 64; i++) { for (int j = 0; j < 64; j++) if (isPerfectSquare(i * 64 + j)) { pp1 |= (1 << j); pp2 |= (1 << i); break; } } cout << "pp1=" << pp1 << "," << pp2 << "\n"; } inline bool isPerfectSquare5(UVLONG x) { return pp1 & (1 << (x & 0x3F)) ? isPerfectSquare(x) : false; }

isPerfectSquare5 루틴은 내 core2 듀오 머신에서 약 1/3로 실행됩니다. 동일한 라인을 따라 추가로 조정하면 평균적으로 시간이 더 단축될 수 있다고 생각하지만 확인할 때마다 더 많은 테스트를 제거하기 위해 더 많은 테스트를 교환하게 되므로 해당 도로에서 너무 멀리 갈 수 없습니다.

물론, 음성에 대해 별도의 테스트를 하는 것보다 상위 6비트를 동일한 방식으로 확인할 수 있습니다.

내가 하는 모든 것은 가능한 사각형을 제거하는 것이지만 잠재적인 경우가 있을 때 원래의 인라인된 isPerfectSquare를 호출해야 합니다.

init2 루틴은 pp1 및 pp2의 정적 값을 초기화하기 위해 한 번 호출됩니다. C++로 구현한 경우 unsigned long long을 사용하고 있으므로 서명되어 있으므로 >>> 연산자를 사용해야 합니다.

배열을 경계 확인해야 할 본질적인 필요는 없지만 Java의 최적화 프로그램은 이 항목을 매우 빠르게 파악해야 하므로 이에 대해 비난하지 않습니다.

Community Wiki

나는 일부 입력에 대해 거의 올바른 방법을 사용하는 아이디어를 좋아합니다. 다음은 "오프셋"이 더 높은 버전입니다. 코드가 작동하는 것으로 보이며 간단한 테스트 케이스를 통과합니다.

다음을 교체하십시오.

 if(n < 410881L){...}

이것으로 코드 :

 if (n < 11043908100L) { //John Carmack hack, converted to Java. // See: http://www.codemaestro.com/reviews/9 int i; float x2, y; x2 = n * 0.5F; y = n; i = Float.floatToRawIntBits(y); //using the magic number from //http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf //since it more accurate i = 0x5f375a86 - (i >> 1); y = Float.intBitsToFloat(i); y = y * (1.5F - (x2 * y * y)); y = y * (1.5F - (x2 * y * y)); //Newton iteration, more accurate sqrt = Math.round(1.0F / y); } else { //Carmack hack gives incorrect answer for n >= 11043908100. sqrt = (long) Math.sqrt(n); }

Community Wiki

일반적인 비트 길이를 고려하여(여기서 특정 유형을 사용했지만) 아래와 같이 단순한 알고리즘을 설계하려고 했습니다. 처음에는 0,1,2 또는 <0에 대한 간단하고 명확한 확인이 필요합니다. 다음은 기존 수학 함수를 사용하지 않는다는 점에서 간단합니다. 대부분의 연산자는 비트 연산자로 대체할 수 있습니다. 그러나 벤치 마크 데이터로 테스트하지 않았습니다. 저는 특히 수학이나 컴퓨터 알고리즘 설계 전문가가 아닙니다. 문제를 지적해 주셨으면 합니다. 거기에 많은 개선 기회가 있다는 것을 알고 있습니다.

 int main() { unsigned int c1=0 ,c2 = 0; unsigned int x = 0; unsigned int p = 0; int k1 = 0; scanf("%d",&p); if(p % 2 == 0) { x = p/2; } else { x = (p/2) +1; } while(x) { if((x*x) > p) { c1 = x; x = x/2; }else { c2 = x; break; } } if((p%2) != 0) c2++; while(c2 < c1) { if((c2 * c2 ) == p) { k1 = 1; break; } c2++; } if(k1) printf("\n Perfect square for %d", c2); else printf("\n Not perfect but nearest to :%d :", c2); return 0; }

Community Wiki

정사각형의 마지막 n비트가 관찰될 때 가능한 모든 결과를 확인했습니다. 더 많은 비트를 연속적으로 검사함으로써 최대 5/6의 입력을 제거할 수 있습니다. 저는 실제로 이것을 Fermat의 Factorization 알고리즘을 구현하기 위해 설계했으며 매우 빠릅니다.

 public static boolean isSquare(final long val) { if ((val & 2) == 2 || (val & 7) == 5) { return false; } if ((val & 11) == 8 || (val & 31) == 20) { return false; } if ((val & 47) == 32 || (val & 127) == 80) { return false; } if ((val & 191) == 128 || (val & 511) == 320) { return false; } // if((val & a == b) || (val & c == d){ // return false; // } if (!modSq[(int) (val % modSq.length)]) { return false; } final long root = (long) Math.sqrt(val); return root * root == val; }

의사 코드의 마지막 비트는 테스트를 확장하여 더 많은 값을 제거하는 데 사용할 수 있습니다. 위의 테스트는 k = 0, 1, 2, 3에 대한 것입니다.

a는 (3 << 2k) - 1 형식입니다.

b는 (2 << 2k) 형식입니다.

c는 (2 << 2k + 2) - 1 형식입니다.

d는 (2 << 2k - 1) * 10 형식입니다.

먼저 계수가 2인 제곱 잔차가 있는지 테스트한 다음 최종 계수를 기반으로 테스트한 다음 Math.sqrt를 사용하여 최종 테스트를 수행합니다. 나는 상단 게시물에서 아이디어를 생각해 냈고, 그것을 확장하려고 시도했습니다. 모든 의견이나 제안에 감사드립니다.

업데이트: 모듈러스(modSq) 및 모듈러스 기반 44352에 의한 테스트를 사용하여 최대 1,000,000,000 숫자에 대한 OP 업데이트의 테스트 시간의 96%에서 테스트가 실행됩니다.

Community Wiki

정수 산술을 사용한 뉴턴의 방법

정수가 아닌 연산을 피하려면 아래 방법을 사용할 수 있습니다. 기본적으로 정수 산술을 위해 수정된 Newton의 방법을 사용합니다.

 /** * Test if the given number is a perfect square. * @param n Must be greater than 0 and less * than Long.MAX_VALUE. * @return <code>true</code> if n is a perfect * square, or <code>false</code> otherwise. */ public static boolean isSquare(long n) { long x1 = n; long x2 = 1L; while (x1 > x2) { x1 = (x1 + x2) / 2L; x2 = n / x1; } return x1 == x2 && n % x1 == 0L; }

Math.sqrt 를 사용하는 솔루션과 경쟁할 수 없습니다. 그러나 다른 게시물에서 설명한 필터링 메커니즘을 사용하여 성능을 향상시킬 수 있습니다.

Community Wiki

다음은 분할 정복 솔루션입니다.

자연수 (의 제곱근 경우 number ) 자연수이다 ( solution ), 당신은 쉽게에 대한 범위를 결정할 수 solution 의 자리의 수에 따라 number :

• number 는 1자리입니다: solution = 1 - 4
• number 는 2자리입니다: solution = 3 - 10
• number 는 3자리입니다: solution = 10 - 40
• number 는 4자리입니다: solution = 30 - 100
• number 는 5자리입니다: solution = 100 - 400

반복을 눈치채셨나요?

이진 검색 접근 방식에서 이 범위를 사용하여 다음과 같은 solution 이 있는지 확인할 수 있습니다.

 number == solution * solution

다음은 코드입니다.

여기 내 클래스 SquareRootChecker가 있습니다.

 public class SquareRootChecker { private long number; private long initialLow; private long initialHigh; public SquareRootChecker(long number) { this.number = number; initialLow = 1; initialHigh = 4; if (Long.toString(number).length() % 2 == 0) { initialLow = 3; initialHigh = 10; } for (long i = 0; i < Long.toString(number).length() / 2; i++) { initialLow *= 10; initialHigh *= 10; } if (Long.toString(number).length() % 2 == 0) { initialLow /= 10; initialHigh /=10; } } public boolean checkSquareRoot() { return findSquareRoot(initialLow, initialHigh, number); } private boolean findSquareRoot(long low, long high, long number) { long check = low + (high - low) / 2; if (high >= low) { if (number == check * check) { return true; } else if (number < check * check) { high = check - 1; return findSquareRoot(low, high, number); } else { low = check + 1; return findSquareRoot(low, high, number); } } return false; } }

그리고 그것을 사용하는 방법에 대한 예가 있습니다.

 long number = 1234567; long square = number * number; SquareRootChecker squareRootChecker = new SquareRootChecker(square); System.out.println(square + ": " + squareRootChecker.checkSquareRoot()); //Prints "1524155677489: true" long notSquare = square + 1; squareRootChecker = new SquareRootChecker(notSquare); System.out.println(notSquare + ": " + squareRootChecker.checkSquareRoot()); //Prints "1524155677490: false"

Community Wiki

숫자가 완전제곱인 경우 숫자의 제곱근입니다.

복잡성은 log(n)

 /** * Calculate square root if the given number is a perfect square. * * Approach: Sum of n odd numbers is equals to the square root of n*n, given * that n is a perfect square. * * @param number * @return squareRoot */ public static int calculateSquareRoot(int number) { int sum=1; int count =1; int squareRoot=1; while(sum<number) { count+=2; sum+=count; squareRoot++; } return squareRoot; }

Community Wiki

속도가 문제라면 가장 일반적으로 사용되는 입력 집합과 해당 값을 조회 테이블로 분할한 다음 예외적인 경우에 대해 생각해낸 최적화된 마법 알고리즘을 수행하지 않겠습니까?

Community Wiki

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

대답은 인상적이지만 간단한 확인을 보지 못했습니다.

오른쪽의 첫 번째 숫자가 집합의 구성원인지 확인하십시오 (0,1,4,5,6,9) . 그렇지 않은 경우 '완벽한 정사각형'이 될 수 없습니다.

예를 들어

4567 - 완전제곱수가 될 수 없습니다.

Community Wiki

그것보다 훨씬 더 효율적으로 '마지막 X자리가 N이면 완전제곱수가 될 수 없다'를 포장하는 것이 가능해야 합니다! Java 32비트 정수를 사용하고 숫자의 마지막 16비트를 확인하기에 충분한 데이터를 생성합니다. 이는 2048개의 16진수 정수 값입니다.

...

확인. 나보다 조금 더 많은 수 이론을 접했거나 내 코드에 버그가 있습니다. 어쨌든 다음은 코드입니다.

 public static void main(String[] args) { final int BITS = 16; BitSet foo = new BitSet(); for(int i = 0; i< (1<<BITS); i++) { int sq = (i*i); sq = sq & ((1<<BITS)-1); foo.set(sq); } System.out.println("int[] mayBeASquare = {"); for(int i = 0; i< 1<<(BITS-5); i++) { int kk = 0; for(int j = 0; j<32; j++) { if(foo.get((i << 5) | j)) { kk |= 1<<j; } } System.out.print("0x" + Integer.toHexString(kk) + ", "); if(i%8 == 7) System.out.println(); } System.out.println("};"); }

결과는 다음과 같습니다.

(ed: prettify.js의 저조한 성능 때문에 생략되었습니다. 확인하려면 개정 내역을 확인하세요.)

Community Wiki

Newton의 방법으로 제곱근을 계산하는 것은 끔찍할 정도로 빠릅니다... 시작 값이 합리적이라면. 그러나 합리적인 시작 값이 없으며 실제로는 bisection 및 log(2^64) 동작으로 끝납니다.
정말 빠르게 하려면 합리적인 시작 값에 도달할 수 있는 빠른 방법이 필요하며, 이는 기계 언어로 내려가야 함을 의미합니다. 프로세서가 Pentium에서 POPCNT와 같은 명령을 제공하면 선행 0을 계산하여 유효 비트의 절반으로 시작 값을 갖도록 사용할 수 있습니다. 주의 깊게 우리는 항상 충분할 고정된 수의 뉴턴 단계를 찾을 수 있습니다. (따라서 루프가 필요하고 매우 빠른 실행이 필요합니다.)

두 번째 솔루션은 i87 보조 프로세서와 같은 빠른 sqrt 계산을 가질 수 있는 부동 소수점 기능을 사용하는 것입니다. exp() 및 log()를 통한 이탈도 이진 검색으로 퇴화된 Newton보다 빠를 수 있습니다. 이것에는 까다로운 측면이 있습니다. 프로세서에 따라 나중에 개선이 필요한지 여부에 대한 분석입니다.

세 번째 솔루션은 약간 다른 문제를 해결하지만 상황이 질문에 설명되어 있기 때문에 언급할 가치가 있습니다. 약간 다른 숫자에 대해 많은 제곱근을 계산하려는 경우 시작 값을 다시 초기화하지 않고 이전 계산이 중단된 위치에 그대로 두면 Newton 반복을 사용할 수 있습니다. 나는 이것을 적어도 하나의 오일러 문제에서 성공적으로 사용했습니다.

Community Wiki

문제에 가장 적합한 알고리즘은 빠른 정수 제곱근 알고리즘입니다. https://stackoverflow.com/a/51585204/5191852

@Kde는 Newton 방법을 3번 반복하면 32비트 정수에 대해 ±1의 정확도로 충분하다고 주장합니다. 확실히, 64비트 정수에는 더 많은 반복이 필요하며 6 또는 7이 될 수 있습니다.

Community Wiki

출처 : http:www.stackoverflow.com/questions/295579/fastest-way-to-determine-if-an-integers-square-root-is-an-integer