스캔라인을 따라 반경을 계산하는 반복적인 방법이 있습니까?

StackOverflow https://stackoverflow.com/questions/1423918

문제

Y 값은 모두 동일하지만 X 값이 다른 일련의 점을 처리 중입니다.X를 1씩 증가시켜 포인트를 살펴봅니다.예를 들어 Y = 50이고 X는 -30에서 30 사이의 정수일 수 있습니다.내 알고리즘에는 각 지점에서 원점까지의 거리를 찾은 다음 추가 처리를 수행하는 작업이 포함됩니다.

프로파일링 후에 거리 계산의 sqrt 호출이 상당한 시간을 소모한다는 사실을 발견했습니다.거리를 계산하는 반복적인 방법이 있습니까?

다시 말해서:

효율적으로 계산하고 싶습니다. r[n] = sqrt(x[n]*x[n] + y*y)).이전 반복의 정보를 저장할 수 있습니다.각 반복은 x를 증가시켜 변경됩니다. x[n] = x[n-1] + 1.sqrt나 trig 함수는 각 스캔라인의 시작 부분을 제외하면 너무 느리기 때문에 사용할 수 없습니다.

충분히 양호하고(오류 0.1% 미만) 도입된 오류가 원활하다면(미리 계산된 근사치 테이블에 저장할 수 없음) 근사치를 사용할 수 있습니다.

추가 정보:x와 y는 항상 -150에서 150 사이의 정수입니다.

내일 몇 가지 아이디어를 시도해보고 가장 빠른 것을 바탕으로 가장 좋은 답변을 표시할 예정입니다.

결과

타이밍 좀 맞춰봤는데

  • 거리 공식:16ms/반복
  • Pete의 상호작용 솔루션:8ms/반복
  • wrang-wrang 사전 계산 솔루션:8ms/반복

나는 두 가지 답변을 모두 좋아하기 때문에 테스트에서 둘 중 하나를 결정하기를 바랐습니다.메모리를 덜 사용하기 때문에 Pete's를 선택하겠습니다.

도움이 되었습니까?

해결책

범위 y = 50의 경우 x = 0은 r = 50 및 y = 50, x = +/- 30은 r ~ = 58.3을 제공합니다. +/- 0.1%또는 +/- 0.05 절대에 대한 근사치를 원합니다. 그것은 대부분의 라이브러리 SQRT보다 정확도가 훨씬 낮습니다.

두 가지 근사 접근법 - 이전 값에서 보간을 기반으로 R을 계산하거나 적합한 시리즈의 몇 가지 용어를 사용합니다.

이전 r에서 보간

r = (x2 + y2 ) 1/2

dr/dx = 1/2. 2x. (x2 + y2 ) -1/2 = x/r

    double r = 50;

    for ( int x = 0; x <= 30; ++x ) {

        double r_true = Math.sqrt ( 50*50 + x*x );

        System.out.printf ( "x: %d r_true: %f r_approx: %f error: %f%%\n", x, r, r_true, 100 * Math.abs ( r_true - r ) / r );

        r = r + ( x + 0.5 ) / r; 
    }

제공 :

x: 0 r_true: 50.000000 r_approx: 50.000000 error: 0.000000%
x: 1 r_true: 50.010000 r_approx: 50.009999 error: 0.000002%
....
x: 29 r_true: 57.825065 r_approx: 57.801384 error: 0.040953%
x: 30 r_true: 58.335225 r_approx: 58.309519 error: 0.044065%

0.1% 오류의 요구 사항을 충족하는 것으로 보이므로 약간 더 많은 계산 단계가 필요하기 때문에 다음 중 하나를 코딩하는 것을 방해하지 않았습니다.

잘린 시리즈

SQRT (1 + x)의 Taylor 시리즈는

sqrt (1 + x) = 1 + 1/2 x -1/8 x2 ... + ( - 1 / 2 )n+1 엑스N

r = y sqrt 사용 (1 + (x/y)2 ) 그럼 당신은 t = (-1 / 2)라는 용어를 찾고 있습니다.n+1 0.36N 크기가 0.001보다 작고 로그 (0.002)> n log (0.18) 또는 n> 3.6이므로 x^4에 용어를 가져 가면 괜찮습니다.

다른 팁

Y=10000
Y2=Y*Y
for x=0..Y2 do
  D[x]=sqrt(Y2+x*x)

norm(x,y)=
  if (y==0) x
  else if (x>y) norm(y,x) 
  else {
     s=Y/y
     D[round(x*s)]/s
  }

좌표가 원활한 경우 선형 보간으로 아이디어를 확장 할 수 있습니다. 더 정확성을 위해 Y를 늘리십시오.

아이디어는 s*(x, y)가 선 Y = Y 라인에 있으며 거리를 미리 계산했습니다. 거리를 얻은 다음 s로 나눕니다.

나는 당신을 정말로 가정합니다 하다 사각형이 아닌 거리가 필요합니다.

속도에 대한 정확성을 희생하는 일반적인 SQRT 구현을 찾을 수도 있지만 FPU가 할 수있는 일을 때리는 것을 상상하는 데 어려움을 겪고 있습니다.

선형 보간으로, 나는 변화를 의미합니다 D[round(x)] 에게:

f=floor(x)
a=x-f
D[f]*(1-a)+D[f+1]*a

이것은 실제로 귀하의 질문에 대한 답변은 아니지만 도움이 될 수 있습니다 ...

내가 물어볼 첫 번째 질문은 다음과 같습니다.

  • "Sqrt가 전혀 필요합니까?".
  • "그렇지 않다면 어떻게 sqrts 수를 줄일 수 있나요?"
  • 그럼 당신 것 :"나머지 sqrts를 영리한 계산으로 대체할 수 있나요?"

그래서 나는 다음과 같이 시작할 것입니다 :

  • 정확한 반경이 필요합니까, 아니면 반경 제곱이 허용됩니까?sqrt에 대한 빠른 근사치가 있지만 아마도 귀하의 사양에 비해 정확하지 않을 수 있습니다.
  • 미러링된 사분면 또는 8분면을 사용하여 이미지를 처리할 수 있습니까?동일한 반경 값의 모든 픽셀을 일괄 처리하면 계산 횟수를 8배까지 줄일 수 있습니다.
  • 반경 값을 미리 계산할 수 있나요?처리 중인 이미지 크기의 1/4(또는 8분의 1)에 해당하는 테이블만 있으면 되며, 테이블은 한 번만 미리 계산한 다음 여러 알고리즘 실행에 재사용하면 됩니다.

따라서 영리한 수학이 가장 빠른 해결책이 아닐 수도 있습니다.

글쎄, 항상 당신의 SQRT를 최적화하려고 노력하고 있습니다. 내가 본 가장 빠른 것은 오래된 Carmack Quake 3 sqrt입니다.

http://betterexplained.com/articles/understanding-quakes-fast inverse-square-root/

즉, SQRT는 비선형이므로 라인을 따라 간단한 선형 보간을 수행하여 결과를 얻을 수 없습니다. 가장 좋은 아이디어는 테이블 조회를 사용하여 데이터에 빠르게 액세스 할 수 있기 때문입니다. 그리고 전체 정수에 의해 반복되는 것처럼 보이므로 테이블 조회가 매우 정확해야합니다.

글쎄, 당신은 x = 0 주위에 미러를 시작하여 시작할 수 있습니다 (n> = 0 만 계산하면 해당 n <0에 해당 결과를 계산하면됩니다). 그 후, 나는 일정한 dx를 활용하기 위해 sqrt (a^2+b^2) (또는 해당 죄)에서 미분을 사용하는 것을 살펴 봅니다.

그것이 충분히 정확하지 않다면, 이것이 SIMD에게 꽤 좋은 일이라고 지적 할 수 있습니다. 이것은 SSE와 VMX (및 셰이더 모델 2) 모두에 대한 상호 제곱근 OP를 제공 할 것입니다.

이것은 일종의 a와 관련이 있습니다 Hakmem 항목:

항목 149 (Minsky) : Circle Algorithm 여기서는 포인트 플로팅 디스플레이에서 거의 원을 그리는 우아한 방법입니다.

NEW X = OLD X - epsilon * OLD Y
NEW Y = OLD Y + epsilon * NEW(!) X

이것은 초기 지점에 의해 결정된 크기로 원점을 중심으로 매우 둥근 타원을 만듭니다. Epsilon은 순환 지점의 각속도를 결정하고 편심에 약간 영향을 미칩니다. Epsilon이 2의 힘이라면, 우리는 제곱근, 죄, 코사인은 물론 곱셈이 필요하지 않습니다! "원"은 포인트가 곧 주기적이기 때문에 완벽하게 안정적입니다.

Display Hack에 하나의 레지스터를 저장하려고 할 때 Circle Atgorithm이 실수로 발명되었습니다! Ben Gurley는 약 6 ~ 7 개의 지침을 사용하여 놀라운 디스플레이 해킹을했으며 놀라운 일이었습니다. 그러나 그것은 기본적으로 선 지향적이었습니다. 곡선을 갖는 것이 흥미로울 것이며, 최소한의 지침으로 곡선 디스플레이 해킹을 얻으려고 노력했습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top