Самый быстрый способ рассчитать расстояние между двумя CGPoints?

Расстояние между двумя точками:

sqrt((x1-x2)^2 + (y1-y2)^2)

Есть ли способ сделать эту математику быстрее в objective-C?

РЕДАКТОР: Я думаю, что мне нужно прояснить выше. Я написал формулу выше, чтобы уточнить, какую формулу я использую, чтобы вычислить расстояние. ^ не предназначен для представления xor - я просто хотел представить математическую формулу без использования каких-либо функций, таких как pow или что-нибудь еще, поэтому я хотел использовать ^ для "повышения мощности". Мне было интересно, знает ли кто-нибудь, если использовать побитовые операторы или иначе писать код в сборке, даст оптимизированную версию. Я использую формулу в приложении iPhone/iPad.

Ответы

Ответ 1

Нет, если вам нужно точное расстояние, вы не можете победить эту формулу.

Хотя ясно, что ^ не является оператором для квадратизации значения, а является битовым оператором, который делает xor.

вам понадобится что-то вроде

double dx = (x2-x1);
double dy = (y2-y1);
double dist = sqrt(dx*dx + dy*dy);

Если вы можете жить только с квадратом (что полезно, когда вы просто хотите сделать что-то вроде сортировки по расстоянию, вы можете использовать гораздо более эффективный

double dx = (x2-x1);
double dy = (y2-y1);
double dist = dx*dx + dy*dy;

Это будет, по крайней мере, так же хорошо, как решение pow. В худшем случае pow() будет использовать стек и быть менее эффективным, но, возможно, ваш компилятор превратит его в x * x для этого случая.

Ответ 2

На Intel Mac Clang будет компилироваться:

double distance = ({double d1 = x1 - x2, d2 = y1 - y2; sqrt(d1 * d1 + d2 * d2); });

в общей сложности 6 инструкций для математики: sub, mul, sub, mul, add, sqrt; довольно сложно победить. (sqrt - это одна команда, хотя требуется несколько циклов).

Ответ 3

Просто предлагая это как простое, приятное решение. Скорее всего, это не так быстро, как раньше, но короче. Я лично использую hypot.

double dist = hypot((x1-x2), (y1-y2));

В docs это вернет вам "Квадратный корень из (x ^ 2 + y ^ 2)".

Ответ 4

double dist = sqrt ( pow((x1-x2), 2) + pow((y1-y2), 2) );

учитывая x1, x2, y1, y2: float или double или integer.

Ответ 5

О единственном, что можно улучшить здесь, - это функция вычисления квадратного корня.

Я пробовал эти две функции (найти в статью Википедии о вычислении квадратного корня) для вычисления приблизительных значений квадратного корня:

float fsqrt(float x)
{
  float xhalf = 0.5f * x;
  union
  {
    float x;
    int i;
  } u;

  u.x = x;
  u.i = 0x5f3759df - (u.i >> 1);
  x *= u.x * (1.5f - xhalf * u.x * u.x);

  return x;
}

float fsqrt2(float z)
{
    union
    {
        int tmp;
        float f;
    } u;

    u.f = z;

    /*
     * To justify the following code, prove that
     *
     * ((((val_int / 2^m) - b) / 2) + b) * 2^m = ((val_int - 2^m) / 2) + ((b + 1) / 2) * 2^m)
     *
     * where
     *
     * val_int = u.tmp
     * b = exponent bias
     * m = number of mantissa bits
     *
     * .
     */

    u.tmp -= 1 << 23; /* Subtract 2^m. */
    u.tmp >>= 1; /* Divide by 2. */
    u.tmp += 1 << 29; /* Add ((b + 1) / 2) * 2^m. */

    return u.f;
}

Но на моем Core 2 Duo Pentium CPU они, похоже, не быстрее, чем инструкция x90 FPU FSQRT. Посмотрите, работают ли они быстрее, чем стандартный sqrtf()/sqrt() на вашей платформе, и если достаточная точность.