Java에서 가장 빠른 인수 분해 과정

Question

주어진 값의 sqrt를 계산하기 위해 java로 프로그램을 작성했습니다. 최대 값은 10^100 입니다. 이를 위해 BigInteger를 사용해야한다는 것을 알고 있지만, 처리하는 프로세스는 많은 시간이 소요되는만큼 효율적이지 않습니다. 프로그램을 처리하기 위해 숫자를 분해하는 가장 빠른 프로세스는 무엇입니까? 빠른 알고리즘이란 무엇입니까?

미리 감사드립니다.

Answer 1

먼저, 대부분의 입력 값에 제곱근에 대한 정확한 정수 값이 지정되지 않았 으면합니다. BigDecimal 대신 BigInteger를 사용하여이 작업을 수행 하시겠습니까?

여러분은 확실히 각 값을 n까지 반복하고 싶지는 않습니다. 응답을 훨씬 더 빨리 향상시킬 방법이 필요합니다. 그렇게하는 간단한 방법은 제곱근의 값에 대한 초기 추측을하는 것입니다 (n/2를 추천합니다). 그리고 co-factor (n/guess)를 찾으십시오. 평등하다면, 평등하지 않다면 추측과 그 공동 요소의 평균이 될 것입니다. 그 중 하나는 실제 제곱근보다 커질 것이고 다른 하나는 더 작 으면 평균화하면 실제 제곱근에 더 가까운 값이 생성됩니다. 비누로 씻고, 반복하십시오. 정확한 제곱근이 없으면 factor와 cofactor가 서로 1이 될 때 정지합니다.

부록 : 여기가 의사 코드에 (실제로 루비,하지만 거의 같은 일이) : 자바

def sqrt(n) 
    guess = n/2 
    cofactor = 2 
    loop do 
    cofactor = n/guess 
    break if (guess - cofactor).abs <= 1 
    guess = (guess + cofactor)/2 
    end 
    return [guess, cofactor].min 
end 

번역은 매우 간단합니다.