숫자의 sqrt를 찾는 재귀 함수의 문제점

다음은 이진을 사용하여 sqrt를 계산하는 간단한 프로그램입니다. sqrtr (4,1,4)와 같은 호출로이를 실행하는 동안 무한 재귀가 발생합니다. 왜 이런 일이 일어나는지 알 수 없습니다. 당신은 당신의 low == high 비교 범위를 넣어 할 수 있습니다숫자의 sqrt를 찾는 재귀 함수의 문제점

double sqrtr(double N , double Low ,double High ) 
{ 

    double value = 0.00; 

    double mid = (Low + High + 1)/2; 

    if(Low == High) 
    { 
     value = High; 

    } 

    else if (N < mid * mid) 
    { 
     value = sqrtr(N,Low,mid-1) ; 


    } 
    else if(N >= mid * mid) 
    { 
     value = sqrtr(N,mid,High) ; 

    } 

    return value; 

}

출처

2010-05-20 Eternal Learner

반올림 불일치 경계 조건이 냄새가납니다. –

http://docs.sun.com/source/806-3568/ncg_goldberg.html –

@Platinum Azure : 놀랍게도 충분하지 않습니다. +1 부분이 정수 알고리즘에서 도난 당했다고 적힌 jpalecek의 공로. 그것은 당신에게 완전히 잘못된 경계를 제공하므로 더 이상 둥근 방법이 중요하지 않습니다. – MSalters

, 정밀의 여섯 소수점 이하 자릿수를위한 즉 high - low < .000001 : 아래 기능입니다.

출처

2010-05-20 22:39:50

어, N = 143214.4213e22는 어떨까요? 지금 당신은 어떻게 시험을 좋아하니, 최고 최저 <0.000001? 내 대답보기 –

외에도 나쁜 종료 조건을 가지고에서, 당신은 어떻게이셨어요 :

else if (N < mid * mid) 
{ 
    value = sqrtr(N,Low,mid-1) ;

어떻게 정당화 mid-1입니까? 정수 바이너리 검색을위한 코드를 잘라 붙이지 않았습니까?

출처

2010-05-20 22:42:37 jpalecek

나 자신도 똑같은 생각을하고 있었다. -1이 가야 해! –

예. 즉시 증명을 위해'sqrtr (0.0001, 0.0, 0.1)'을 시도하십시오. – MSalters

서로 같은 부동 소수점 값에 의존하는 것이 거의 불가능합니다. 정수와 달리 표현하는 값의 범위에서 모든 값을 나타낼 수 없으므로 약간의 차이로 인해 쉽게 벗어날 수 있습니다.

그렇다면 정확한 평등보다는 지정된 정밀도를 비교해야 할 것입니다.

위의 의견 중 하나에서 지적한 것처럼 서류 "What Every Computer Scientist Should Know About Floating-Point Arithmetic"을보아야합니다. 부동 소수점 수의 특성에 대한 고전적이고 우수한 논문입니다.

출처

2010-05-20 22:56:57

몇 가지 문제가 있습니다. jpalecek에서 알 수 있듯이 인덱스 배열에 대한 이진 검색 루틴을 잘라내어 붙여 넣은 것처럼 보이며 작동 방식을 이해하지 못합니다. 또한 종료 기준은 지나치게 엄격합니다.

저는 이분법과 재귀가 sqrt()를 풀기에 매우 열악한 방법이기 때문에 이것은 학습 연습이라고 가정합니다.

아래 코드는 작동하지만 끔찍하게 느리고 부정확합니다.

#include <iostream> 
using namespace std; 

double sqrtr(double N , double Low ,double High ) 
{ 
    // Precondition: Low and High, Low <= High, must be non-negative, and must 
    // bracket sqrt(N). 

    const double sqrt_mef = 1e-8; // Approximate square root of machine efficiency 

    double mid = (Low + High)/2; // No +1 

    if((High-Low)/(1+mid) < sqrt_mef) 
    { 
     return mid; 
    } 

    else if (N < mid * mid) 
    { 
     return sqrtr(N,Low,mid) ; // No -1 
    } 
    else 
    { 
     return sqrtr(N,mid,High) ; 
    } 

} 

int main() 
{ 
    double sqrt_2 = sqrtr(2.0, 0, 2.0); 
    cout << sqrt_2*sqrt_2 << endl; 
    getchar(); 
}

출처

2010-05-21 01:02:19

숫자의 sqrt를 찾는 재귀 함수의 문제점

답변

관련 문제