T1 = T2 * N에서 T2 항을 어떻게 효율적으로 추출할 수 있습니까? 소수 지수 분석을 사용하시나요?

이 글에서 저자는 고정 소수점 빅넘버 라이브러리를 사용하여 큰 수의 계승을 계산하는 빠르고 정확한 방법에 대해 논의합니다. 구현에 대해 반복되는 질문은 곱 T1 = T2 * N!에서 T2 항을 추출하는 것이었습니다. 여기서 T1과 N! 이미 알려져 있습니다. T2 항을 찾기 위해 저자는 소수 지수에 대한 분석을 수행하고 이를 계산하는 공식을 제안했습니다.

T2(4N) = multiplication(i=all primes<=4N) of [i^sum(j=1,2,3,4,5,...4N/(i^j)) of [(4N/(i^j))%2]]

T2의 하위 항은 T2(N) 항 내부에 소수 i에 대한 지수 e가 있습니다. 다음과 같이 계산됩니다.

for (e=0,j=N4;j;e+=j&1,j/=p);

여기서 e는 지수, p는 소수, N4는 4*N

계산된 T2 항은 계승 계산을 최적화하는 데 사용되며 결과 알고리즘은 ~O(log(n))에 가까운 계산 복잡성을 나타냅니다.

처음 128개의 계승에 대한 대략적인 시간 측정이 제공됩니다. 저자는 이 구현이 더 이상 단순화될 수 없으며 이미 고도로 최적화되어 있음을 인정합니다.

위 내용은 T1 = T2 * N에서 T2 항을 어떻게 효율적으로 추출할 수 있습니까? 소수 지수 분석을 사용하시나요?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!