루트 계산 기능 구현

Question

다양한 기능을 구현하는 수학 함수는 충분히 간단합니다. int mul(int,int);, int pow(int,int);, 심지어 double div(float,float);은 쉽게 수행 할 수 있으며 루프 또는 재귀를 통해 구현할 수 있습니다. (이들은 손으로 또는 머리에서 이러한 기능을 수행하는 데 사용 된 것과 동일한 방법입니다.) 곱셈을하려면 숫자를 반복해서 추가하십시오. 나누려면 반복해서 빼십시오. 힘을 얻으려면 반복적으로 번식하십시오. 등등.

그러나 항상 궁금해했던 한 가지 수학적 기능은 뿌리입니다. 예를 들어 숫자의 제곱 (또는 큐브 등) 루트를 계산하는 함수를 작성하는 방법 (예 : double root(float num, float root);)? 나는 주위를 둘러 보았고 알고리즘이나 알고리즘을 찾을 수 없었다.

수작업으로 루트를 계산할 때 일반적으로 추측 방법을 사용합니다 (대략적인 숫자로 시작하고 소수를 추가하고 곱하기, 멀리 떨어져있는 정도보기, 작은 부분 추가, 곱하기, 다시 확인, 만족할 때까지 반복하십시오. 나는 그것이 작동 할 수 있다고 생각하지만, 분명히 더 빠르고 더 빠른 방법이있다 (컴퓨터가 얼마나 빨리 컴퓨터를 할 수 있는지에 관계없이).

분명히 LUT는 관련이 없습니다 (피연산자 세트를 사용하여 게임을 작성하지 않는 한) 피연산자를 가져올만큼 충분히 포괄적이어야하므로 분명합니다. Wikipedia article에는 추측법이 언급되어 있으며 고대 컴퓨터 (컴퓨터가 발명되기 훨씬 오래 전부터)와 일부 순수 수학 및 계산법 (구성 요소로 '무한'이있는 것 포함)을 나열합니다. 전자 제품과 관련이있는 것만이 트릭이나 로그를 사용합니다. (평방근, 큐브 루트는 말할 것도 없습니다.)

쉬운 루트 계산 방법이 없습니까? 계산기가 어떻게합니까? 컴퓨터는 어떻게합니까? (아니요, 단순히 double pow(a,0.5);을 수행하면 double pow(float,float)이 어떻게 구현 될까요?)

단순한 함수로 루트 함수를 잘못 그룹화 했습니까? 그들이 보는 것보다 더 복잡한가?

Answer 1

당신이 말하는 기사에서 직접 연결된 N-th root algorithm을 구현하는 것이 간단합니다. Newton's method에서 파생되었습니다.

Answer 2

두 가지 가능성이 있습니다. 이분법 (bisection)이나 뉴턴 (Newton)과 같은 몇 가지 다른 반복 접근법이 있습니다. 지금까지 pow을 사용하는 한 일부 컴퓨터 (예 : x86)에는 숫자를 권력으로 올리는 지침이 있습니다. 따라서이 문제를 해결하기위한 일련의 프레임 워크를 작성해야합니다.

다음은 16 비트 정수로만 작업하는 제곱근에 대한 Newton의 방법을 어셈블리 언어로 구현 한 것입니다. 그러나 동일한 기본 개념이 다른 유형에도 적용됩니다. 필자는 약 20 년 전 이것을 작성 했으므로 부동 소수점 하드웨어가없는 16 비트 CPU를 사용했습니다. 당신은 일반적으로 단지 반복적으로 빼서 반복 해 추가하여 곱셈이나 나눗셈을 구현하지 않으려는, 그러나,

pow proc 
    ; x^y = 2^(log2(x) * y) 
    fyl2x  
    fld st(0) 
    frndint 
    fld1  
    fscale 
    fxch st(2) 
    fsubrp 
    f2xm1  
    fld1  
    faddp  
    fmulp  
    ret 
endp 

참고 : 여기에

isqrt proc uses di, number:word 
; 
; uses bx, cx, dx 
; 
    mov di,number 
    mov ax,255 
start_loop: 
    mov bx,ax 
    xor dx,dx 
    mov ax,di 
    div bx 
    add ax,bx 
    shr ax,1 
    mov cx,ax 
    sub cx,bx 
    cmp cx,2 
    ja start_loop 
    ret 
isqrt endp 

는 x87 임의의 힘을 계산하기위한 몇 가지 코드입니다 . 오히려, 결과를 훨씬 더 신속하게 얻기 위해 연속적인 2의 제곱을 이동 및 더하기/빼기를 ​​원합니다.여기

는 일반적인 생각을 표시하는 코드입니다 :

mult proc 
; multiplies eax by ebx and places result in edx:ecx 
    xor ecx, ecx 
    xor edx, edx 
mul1: 
    test ebx, 1 
    jz mul2 
    add ecx, eax 
    adc edx, 0 
mul2: 
    shr ebx, 1 
    shl eax, 1 
    test ebx, ebx 
    jnz mul1 
done: 
    ret 
mult endp 

이 그것을 내장 곱셈 지침을 가지고 있기 때문에,하지만 구형 프로세서 (PDP-11, 8080, 6502, 등에, 86 꽤 무의미) 코드는 이며, 코드 번호는입니다.

Answer 3

얼마나 일반적인가에 달려 있습니다. 예를 들어 (-4.2) ^0.23과 같이 계산하려면 복잡한 산술 연산이 필요합니다. Mat가 지적한 것처럼 정수 n과 양수 x에 대해 x ^1/n을 계산하는 빠른 알고리즘이 있습니다. 양수 x와 임의의 y에 대해 x ^y을 원하면 로그와 지수가 작동합니다.