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

집

Java

java지도 시간

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

DDD

Jan 01, 2025 am 07:23 AM

How Can I Quickly Determine if a Large Integer is a Perfect Square Using Bitwise Operations?

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

뻔한 답변 필터링: 음수 포함, 마지막 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;
```
로그인 후 복사

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

로그인 후 복사

헨젤의 보조정리의 기본 구조는 다음과 같습니다. (참고: 테스트되지 않은 코드. 작동하지 않으면 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) );
```
로그인 후 복사