Existe uma maneira iterativa para calcular raios ao longo de uma linha de varredura?

Question

Eu estou processando uma série de pontos que todos têm o mesmo valor de Y, mas diferentes valores de X. I percorrer os pontos incrementando X por um. Por exemplo, eu poderia ter Y = 50 e X é os inteiros de -30 a 30. Parte do meu algoritmo envolve encontrar a distância à origem de cada ponto e, em seguida, fazer processamento adicional.

Depois de perfis, eu descobri que a chamada sqrt no cálculo da distância está tomando uma quantidade significativa de meu tempo. Existe uma maneira iterativa para calcular a distância?

Em outras palavras:

Eu quero calcular de forma eficiente: r[n] = sqrt(x[n]*x[n] + y*y)). I pode salvar informações da iteração anterior. Cada iteração muda incrementando x, então x[n] = x[n-1] + 1. Eu não posso usar sqrt ou funções trigonométricas, porque eles são muito lento, exceto no começo de cada linha de varredura.

Eu posso usar aproximações, enquanto eles são bons o suficiente (menos de 0.l erro%) e os erros introduzidos são suaves (eu não posso bin a uma tabela pré-calculada de aproximações).

Informações adicionais: x e y são sempre inteiros entre -150 e 150

Eu vou tentar algumas idéias fora amanhã e marcar a melhor resposta com base no que é mais rápido.

Resultados

Eu fiz alguns horários

• fórmula Distância: 16 ms / iteração
• solução interperlating de Pete: 8 ms / iteração
• solução de pré-cálculo wrang-wrang: 8ms / iteração

Eu estava esperando que o teste iria decidir entre os dois, porque eu gosto de ambas as respostas. Eu estou indo para ir com Pete, porque ele usa menos memória.

Answer 1

Só para ter uma idéia de que, para sua faixa y = 50, x = 0 dá r = 50 e y = 50, x = +/- 30 dá r ~ = 58,3. Você quer uma boa aproximação para +/- 0,1% ou +/- 0,05 absoluta. Isso é muito menor precisão do que a maioria das raízes quadradas biblioteca fazer.

Duas abordagens aproximados - você calcular r baseado em interpolação do valor anterior, ou usar alguns termos de uma série adequado.

interpolação de r anterior

r = (x ² + y ² ) ^1/2

dr / dx = 1/2. 2x. (X ² + y ² ) ^-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; 
    }

Dá:

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%

que parece cumprir a exigência de erro de 0,1%, então eu não me incomodei de codificação o próximo, uma vez que exigiria um pouco mais passos de cálculo.

truncado Series

As séries de Taylor para sqrt (1 + x) para x próximo de zero é

sqrt (1 + x) = 1 + 1/2 x - x 1/8 ² ... + (- 1/2) ^{n + 1} x ⁿ

Usando r = sqrt y (1 + (x / y) ² ), então você está procurando um termo t = (- 1/2) ^{n + 1} 0,36 ⁿ com magnitude menor que uma 0,001, log (0,002)> n log (0,18) ou n> 3,6, de modo a tomar termos de x ^ 4 deve ser OK.

Answer 2

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
  }

Se suas coordenadas são lisas, em seguida, a idéia pode ser estendido com a interpolação linear. Para mais precisão, aumentar Y.

A idéia é que S * (x, y) está na linha y = Y, que você pré-computados distâncias para. Obter a distância, em seguida, dividi-lo por s.

Eu suponho que você realmente não precisa a distância e não o seu quadrado.

Você também pode ser capaz de encontrar uma aplicação geral sqrt que sacrifica um pouco de precisão para a velocidade, mas eu tenho um tempo difícil imaginar que bater o que o FPU pode fazer.

Por interpolação linear, quero dizer à mudança D[round(x)] a:

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

Answer 3

Isto realmente não responder à sua pergunta, mas pode ajudar ...

As primeiras perguntas que eu gostaria de pedir seria:

• "eu preciso o sqrt em tudo?".
• "Se não, como posso reduzir o número de raízes quadradas?"
• Em seguida, o seu: "Posso substituir as raízes quadradas restantes com um cálculo inteligente"

Então, eu começaria com:

• Você precisa o raio exato, ou raio-quadrado seria aceitável? Há rápido approximatiosn para sqrt, mas o suficiente provavelmente não precisa para o seu spec.
• Você pode processar a imagem utilizando quadrantes espelhadas ou oitavos? Ao processar todos os pixels ao mesmo valor de raio em um lote, você pode reduzir o número de cálculos por 8x.
• Você pode precalculate os valores de raio? Você só precisa de uma tabela que é um quarto (ou, eventualmente, um oitavo) do tamanho da imagem que você está processando, ea mesa só precisa ser pré-calculada uma vez e, em seguida, re-utilizado para várias execuções do algoritmo.

Assim a matemática inteligente pode não ser a solução mais rápida.

Answer 4

Bem, há sempre tentando otimizar seu sqrt, o mais rápido que eu já vi é o velho carmack Quake 3 sqrt:

http://betterexplained.com/articles/understanding- tremores-fast-inverso do quadrado da raiz /

Dito isto, uma vez que sqrt é não-linear, você não vai ser capaz de fazer uma interpolação linear simples ao longo de sua linha para obter o resultado. A melhor idéia é usar uma consulta à tabela uma vez que lhe dará acesso veloz aos dados. E, desde que você parece ser a iteração por números inteiros, uma pesquisa de tabela deve ser extremamente preciso.

Answer 5

Bem, você pode espelhar em torno de x = 0 para começar (você só precisa calcular n> = 0, ea dupe esses resultados a correspondente n <0). Depois disso, eu uma olhada utilizando o derivado de sqrt (a ^ + b ^ 2 2) (ou o correspondente sin) para tirar vantagem da constante dx.

Se isso não é suficiente preciso, posso salientar que este é um trabalho muito bom para SIMD, que irá fornecer-lhe com um op raiz quadrada recíproca em ambos SSE e VMX (e Shader Model 2).

Answer 6

Esta é uma espécie de relacionado a um HAKMEM artigo :

ITEM 149 (Minsky): CIRCLE ALGORITMO Aqui é uma maneira elegante de chamar quase círculos em um display de plotagem ponto:

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

Isto faz uma elipse muito redondo centrado na origem com o seu tamanho determinado pelo ponto inicial. epsilon determina o angular velocidade do ponto de circulação, e afeta um pouco a excentricidade. E se epsilon é uma potência de 2, então não fazer mesmo necessidade de multiplicação, e muito menos raízes quadradas, senos, cossenos e! o "Círculo" será perfeitamente estável porque os pontos em breve se tornar periódica.

O algoritmo círculo foi inventado por erro quando tentei salvar um registrar em um hack exposição! Ben Gurley teve um corte espantosa exibição usando apenas cerca de seis ou sete instruções e foi uma grande maravilha. Mas era basicamente linha-orientado. Ocorreu -me que seria emocionante ter curvas, e eu estava tentando obter um corte curva com um mínimo de exposição instruções.