파이썬에서 십진수를 사용하여 큐브 루를 효과적으로 계산하는 방법

Question

저는 파이썬에서 십진수 모듈을 사용하여 새로운 것이므로 큐브 - 루트 (또는 루트)를 계산하는 가장 효율적인 방법이 무엇인지 궁금합니다. 나는 num ** (Decimal(1)/Decimal(3)을 시도했지만 꽤 오래 걸렸다. 예를 들어, 아래 코드는 인텔 i5 프로세서를 실행 파이썬 3에 약 20 초 정도 걸립니다 :

from decimal import * 

getcontext().prec = 10000 
a0 = Decimal(3.0) 

import time 
beg = time.time() 
cuber = a0**(Decimal(1)/Decimal(3)) 
end = time.time() 
print(end-beg) 

난 그냥 간단한 뉴턴 알고리즘을 쓰기 때문에 할 수있는 더 나은 뭔가를 알고는 훨씬 짧은 실행 시간을 제공합니다 (아래 코드 참조) . 그래서, 내 질문에 좋은 방법입니다 (내장 선호 선호) 십진수의 정수 뿌리 걸릴?

훨씬 빠릅니다 빠른 뉴턴의 방법은, (~ 0.2 초) 다음과 같습니다 :

def cube_root(A): 
    guess = (A-Decimal(1))/Decimal(3) 
    x0 = (Decimal(2) * guess + A/Decimal(guess*guess))/Decimal(3.0) 
    while 1: 
     xn =(Decimal(2) * x0 + A/Decimal(x0*x0))/Decimal(3.0) 
     if xn == x0: 
      break 
     x0 = xn 
    return xn 

beg = time.time() 
print(cuber - cube_root(a0)) 
end = time.time() 
print(end-beg) 

위의 모든 코드의 샘플 출력은, 내 시스템에있다 :

23.898984670639038 
0E-9999 
0.10790443420410156 

Answer 1

그런 낮은 큐브 루트의 경우 Newton 's가 최선의 방법이 될 것입니다. 나는 내부 테스트를 제거하여 루프를보다 효율적으로 만들었으며 속도가 약 5 % 향상되었습니다. 여분의 Decimal 전환을 제거하면 2-3 %의 추가 비용이 발생합니다.

def cube_root(A): 
    d1 = Decimal(1) 
    d2 = Decimal(2) 
    d3 = Decimal(3) 

    x0 = (A-d1)/d3 
    xn = (d2 * x0 + A/Decimal(x0*x0))/d3 

    while xn != x0: 
     x0 = xn 
     xn = (d2 * x0 + A/Decimal(x0*x0))/d3 

    return xn