C++에서 double sqrt (double x) 구현

표준 라이브러리를 사용하지 않고 C++에서 double sqrt(double x)을 구현하십시오.C++에서 double sqrt (double x) 구현

이것은 내가 본 페이스 북 인터뷰 질문입니다. http://www.glassdoor.com/Interview/Implement-double-sqrt-double-x-in-C-QTN_87210.htm 이것에 대해 다른 좋은 아이디어? ...

! 편집.! (표준 라이브러리를 사용하지 않고.)

출처

2011-02-15 Josh Morrison

'#include '[개행 문자]''double sqrt (double x) {return std :: sqrt (x); }' –

@James :'#include '[개행]'double sqrt (double x) {return std :: pow (x, 0.5); }' –

http : //en.wikipedia.org/wiki/Newton % 27s_method – Anycorn

보기 here. 이 CodeProject 기사는 제곱근을 계산하기위한 14 가지 방법을 비교합니다.

출처

2011-02-15 06:00:22

여기 wikipedia에서 찾을 수있는 가장 천재 SQRT 구현 중 하나입니다 . 가장 정확하고 빠르지는 않습니다.

float fast_sqrt(float number) { 
    long i; 
    float x2, y; 
    const float threehalfs = 1.5F; 

    x2 = number * 0.5F; 
    y = number; 
    i = * (long *) &y;      // floating point bit level hacking [sic] 
    i = 0x5f3759df - (i >> 1);    // Newton's approximation 
    y = * (float *) &i; 
    y = y * (threehalfs - (x2 * y * y)); // 1st iteration 
    y = y * (threehalfs - (x2 * y * y)); // 2nd iteration 
    y = y * (threehalfs - (x2 * y * y)); // 3rd iteration 

    return 1/y; 
}

출처

2011-02-15 05:32:11 regality

그러면 답을 인터뷰에서 생각해야한다고 생각하십니까? –

그는 직업을 원했습니까? 면접을하는 동안 그들에게 깊은 인상을 심어 주어야합니다. – regality

@ 토니 : "Quake의 고속 역 제곱근 함수의 방법론을 사용할 것입니다. 그 수식은 놀랍습니다. 아마 충분할 것이다. (기술적으로 이것은 1 대신 newton-raphson 근사치를 3 번 통과합니다 ... 그렇기 때문에 똑같은 것은 아닙니다) – James

명백한 두 가지 대답은 이분법 (semi-slow)과 Newton-Raphson/Leibniz 반복 (보통 더 빠름)입니다. 사람의 재미를 망치고에서 유지하려면, 나는 질문에 reinterpret_cast을 다하겠습니다 - 여기 뉴튼 - 랩슨 기술을 사용하여 8086 어셈블리 언어의 정수 제곱근의 구현입니다 :

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

이 일부 개선 열려 - sqrt (x)에서 초기 추측으로 x/2를 사용합니다. 386+ 지침을 사용하면 bsr을 사용하여 로그 x의 대략적인 근사값을 얻도록 설정된 최상위 비트를 찾아서이를 2로 나눠서 초기 근사값을 구할 수 있습니다.

OTOH, 이것은 실제로 고대 프로세서에서만 의미가 있습니다. 부동 소수점 하드웨어가 내장 된 486 (또는 그 이후) 이후로, FSQRT 명령어가이 명령어를 능가 할 것이라는 점은 거의 확실합니다.

출처

2011-02-15 05:32:45

내가 알고있는 상호 접근법 http://en.wikipedia.org/wiki/ Methods_of_computing_square_roots # Reciprocal_of_the_square_root는 영리한 해킹을 루핑으로 대체하기 때문에 더 빠릅니다. 나는 그 정밀도를 확신하지 못한다. –

@Matthieu M .: 예, 문제를 변경하면 속도를 약간 향상시킬 수 있습니다. 그들 대부분은 또한 약 10 또는 12 비트 (보통 해상도에서 ~ 1 픽셀)에 대해서만 좋은 * 매우 근사한 근사를 수행합니다. 그러나 실제 제곱근의 경우에는 전용 하드웨어를 이기기가 정말 어렵습니다. –

분명히 네가 쓴 어셈블리 함수를 언급하고있다. 나는 정수에 대해 완벽한 정밀도를 가진 상호 접근법을 사용했고, 뉴턴의 반복을 추가하면 정밀도가 어느 정도 향상 될 것으로 보인다. 흥미로운 점은 어쨌든 좋은 근사치를 얻는 것입니다. 그런 다음 필요에 따라 정밀도를 조정할 수 있습니다. –

log (ln)과 exp를 사용할 수 있다면 물론 exp (log (x)/2)는 제곱근을 줄 것입니다.

하는 것은 가정 :

x는하고 시작 값은 다음 Y를 우리가 Y를 반복의 우리의 가치는 우리가 SQRT를 발견하면 - 중 조건을 것입니다 종료> (Y + X/Y)/2

이전 값에 y가 근접하거나 x에 y * y가 근접해야합니다.

내 X 값으로 385으로 내 반복이 값을 얻을 수 (엑셀)

1 
193 
97.49740933 
50.7231161 
29.15667189 
21.1805984 
19.67880541 
19.62150055 
19.62141687 
19.62141687

사용할 수

에 "대략"2^시작 지점으로 (기본 2 (X)/2 로그) 1 대신에 385는 8과 9 사이의 어딘가에 로그를 가지고 있습니다. 따라서 8.5라고 말하면 2^4.25로 시작하십시오. 우리가 16과 32 사이의 선형을 할 경우, 우리는 그냥 4 단계로 거기 (20)

20을 시작으로 시작하는 것입니다 :

20 
19.625 
19.6214172 
19.62141687

하지만 대략 로그를 계산하기 위해 이전의 "반복"요구 및 지수.

출처

2011-02-15 08:40:57 CashCow

C++에서 double sqrt (double x) 구현

답변

관련 문제