비트별 연산을 사용하여 큰 정수가 완전제곱수인지 빠르게 판단할 수 있는 방법은 무엇입니까?

알고리즘은 알려주신 코드보다 약 35% 빠르지만 실제 결과는 CPU(x86)와 프로그래밍 언어(C/C)에 따라 다를 수 있습니다. 본 글의 방법은 세 부분으로 나누어져 있습니다.

1. 뻔한 답변 필터링: 음수 포함, 마지막 4자리 확인(마지막 6자리 확인 시 발견) 도움이 되지 않습니다), 0으로 답하세요. (다음 코드를 읽을 때 내 입력은 int64입니다. 두 개의 서로 다른 소수의 곱이므로 제곱 모듈로 255의 나머지는 약 1/8뿐입니다. 하지만 제 경험상 모듈로 연산자(%)를 사용하는 데 드는 비용이 이점보다 더 크기 때문에 255를 포함하는 비트 트릭을 사용하여 나머지를 계산했습니다. (좋든 나쁘든 단어에서 개별 바이트를 읽는 트릭을 사용하지 않고 비트 AND 및 이동만 사용했습니다.)

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

나머지가 실제로 제곱수인지 확인하기 위해 미리 계산된 테이블을 사용했습니다. .

2. 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.

   헨젤의 정리와 유사한 방법을 사용하여 제곱근을 계산해 보려고 합니다

   : 이 전에는 두 가지를 사용했습니다. 검색에서는 2의 거듭제곱으로 발생한 모든 나머지를 나눕니다.

   if( bad255[y] )
       return false;
   // However, I just use a table of size 512

이 시점에서 숫자가 제곱수가 되려면 모듈러스가 8/1이어야 합니다.

3. 헨젤의 보조정리의 기본 구조는 다음과 같습니다. (참고: 테스트되지 않은 코드. 작동하지 않으면 t=2 또는 8을 시도하십시오.)

   if((x & 4294967295LL) == 0)
       x >>= 32;
   if((x & 65535) == 0)
       x >>= 16;
   if((x & 255) == 0)
       x >>= 8;
   if((x & 15) == 0)
       x >>= 4;
   if((x & 3) == 0)
       x >>= 2;

   아이디어는 각 반복마다 r에 1비트를 추가한다는 것입니다." (r이 의 거듭제곱의 제곱근인 경우 참고하세요.) 실제 제곱근은 2^32보다 작기 때문에 이 시점에서 r 또는 t/2-r이 x의 실제 제곱근인지 실제로 확인할 수 있습니다. 실제 코드에서는 다음과 같은 수정된 루프를 사용했습니다.

   if((x & 7) != 1)
       return false;

   여기서 속도 이득은 세 가지 방법으로 얻을 수 있습니다. 미리 계산된 시작 값(약 10회 루프 반복에 해당), 루프를 더 일찍 종료하고 일부 t 값을 건너뜁니다. 마지막 부분에서는 z=r-x*x를 관찰하고 비트 트릭을 사용하여 t를 z로 나눈 2의 가장 큰 거듭제곱으로 설정합니다. 이를 통해 어쨌든 r 값에 영향을 주지 않는 t 값을 건너뛸 수 있습니다. 내 경우에는 미리 계산된 시작 값이 "최소 양수" 제곱근 모듈로 8192를 선택했습니다.

   int64 t = 4, r = 1;
   t <<= 1; r += ((x - r * r) & t) >> 1;
   t <<= 1; r += ((x - r * r) & t) >> 1;
   t <<= 1; r += ((x - r * r) & t) >> 1;
   // Repeat until t is 2^33 or so.  Use a loop if you want.

   이 코드가 더 빨리 작동하지 않더라도 아이디어를 즐기시기 바랍니다. 미리 계산된 테이블을 포함한 전체 테스트 코드는 다음과 같습니다.

   int64 r, t, z;
   r = start[(x >> 3) & 1023];
   do {
       z = x - r * r;
       if( z == 0 )
           return true;
       if( z < 0 )
           return false;
       t = z & (-z);
       r += (z & t) >> 1;
       if( r > (t >> 1) )
           r = t - r;
   } while( t <= (1LL << 33) );

위 내용은 비트별 연산을 사용하여 큰 정수가 완전제곱수인지 빠르게 판단할 수 있는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!