Быстрое [s]взятие квадратного корня из целого 64-битного числа[/s] нахождение расстояния между двумя целочисленными точками. (4 стр)

entryway
> int64 разве нет в твоем делфи чтобы сделать (a*8780) shr 16? Ну и разрядов еще
> парочку сократить можно. Вначале проверить на "очень большое число" и перейти
> на инт64 при необходимости.

int64 есть.
Работает через call mulII, как-то так называется функция. Она даже не инлайнится. Короче, это полный писец.

entryway
> http://www.flipcode.com/archives/Fast_Approximate_Distance_Functions.shtml

Спасибо.
Там, правда, та же фигня, что я придумал, только для 8-угольников.

*441/1024 - это примерно то же самое. Работает только для чисел, меньших 100*(2^16).

А уберфункция та даёт правильный 8-угольник, только немного пнутый.

А по скорости совпадает с моим 12-угольником.

Может мой вариант на С переписать, заменить на деление на 128 и на флипкод отправить?
К тому же для физики шариков такая форма намного лучше, ведь шарики одного размера скапливаются в треугольнички и форма, кратная трём, там в тему.

Ещё вариант. Он грубее. Годится для чисел до 1800*(2^16)

function Dist(dx, dy: integer): integer;
begin
  dx := abs(dx);
  dy := abs(dy);
  if dx>dy then begin
    dy := dy shr 1 - (dx*17) shr 7;
    if dy >= 0 then result := dx+dy else result := dx;
  end else begin
    dx := dx shr 1 - (dy*17) shr 7;
    if dx >= 0 then result := dx+dy else result := dy;
  end;
end;

В нём нет умножений, на самом деле.
Правда, жаль, что dcc вместо lea делает сдвиг и сумму.

Ещё грубее вариант. Ограничений сверху нет.

function Dist(dx, dy: integer): integer;
begin
  dx := abs(dx);
  dy := abs(dy);
  if dx>dy then begin
    dy := dy shr 1 - dx shr 3;
    if dy >= 0 then result := dx+dy else result := dx;
  end else begin
    dx := dx shr 1 - dy shr 3;
    if dx >= 0 then result := dx+dy else result := dy;
  end;
end;

Разброс на круге 3.65%
Выглядит прилично.

entryway
> Разброс на круге 3.65%
Ану дай какую-нибудь пару, чтобы погрешость была больше 3%.

TarasB
Какой у тебя целевой процессор (какой максимальный SSE поддерживает?). Потом команда не пошла это ты получил SIGILL или оно даже не скомпилировалось (чтобы скомпилировал Delphi нужно некоторое шаманство)

Bishop
> Какой у тебя целевой процессор
Селерон 600

entryway
> Селерон 600
Это издевательство или серьёзно? (если серьёзно, то всё очень печально)

entryway
> Ану дай какую-нибудь пару, чтобы погрешость была больше 3%.

Возьми точку в углу и на основании перпендикуляра из центра на сторону.
(520,520) и (616,352) и (715,178.75) , например.
Моя функция для всех этих пар даёт 715
А Теорема Пифагора даёт
735.39105243400942500, 709.47868185027236900, 737.00513057915682300
наибольшее соотношение этих чисел равно
1.03879813366216634

Только это не погрешность, а разброс.

Bishop
> Потом команда не пошла это ты получил SIGILL или оно даже не скомпилировалось

Не скомпилилось. Но если  SSE4 нужно, но у меня вряд ли взлетит.

> (чтобы скомпилировал Delphi нужно некоторое шаманство)

Посмотреть опкод и написать db что-то там, это понятно.

Bishop
> entryway
> > Селерон 600
> Это издевательство или серьёзно? (если серьёзно, то всё очень печально)

А схрена ли менять комп? За последние 10 лет прикладные пользовательские программы обрели только одну принципиально новую возможность - тормозить на нескольких гигагерцах и гигабайтах.

Вопрос: если у вас такие огромные погрешности, нафиг использовать 64 битные числа?

TarasB
Ну можно инструкцию DPPD заменить на несколько других (потому версию SSE и просил. Посмотри в CPU-Z что у тебя есть, я тебе напишу под данную версию)

ALPINE
> если у вас такие огромные погрешности, нафиг использовать 64 битные числа?
Переполнение инта же. В последнем тараскином варианте его нет.

TarasB
> За последние 10 лет прикладные пользовательские программы обрели только одну
> принципиально новую возможность - тормозить на нескольких гигагерцах и
> гигабайтах.
  Intel Core i3 (всего 4000 руб, может даже дешевле, если подержаный) + 4Гб оперативки = ничего не тормозит. Ничего, даже Windows 7 с запущенными одновременно оперой, скайпом, вордом, экселем, аутлуком и эклипсом (иногда с несколькими экземплярами отлаживаемых программ). Даже не знаю, что бы такого запустить, чтобы нагрузить проц больше, чем на 20% и занять больше 2 Гб памяти :)

TarasB
Подсчитать кол-во значащих бит, делить на 2, умножить на предвычисленный корень из первых 6 или 8

// возвращает кол-во значащих бит
int ilog2(int x)
{
  int r=0;
  if(x>=(1<<16)) {r+=16;x>>=16;}
  if(x>=(1<<8)) {r+=8;x>>=8;}
  if(x>=(1<<4)) {r+=4;x>>=4;}
  if(x>=(1<<2)) {r+=2;x>>=2;}
  if(x>=(1<<1)) {r+=1;x>>=1;}
  return r+x;
}

#define NB 6

int isqrt(int x)
{
  if(x==0)
    return 0;
  int k=ilog2(x); // кол-во значащих бит
  // 2^k<=x<2^(k+1)
  int s=NB+(k&1); // ограничиваем точность аргумента первыми NB+(k mod 2) битами
  x<<=(32-k); // сдвинуть влево до бита 31
  x>>=(32-s); // сдвинуть вправо до бита s-1, оставить первые s бит
  // 2^NB<=x<2^(NB+2)
  // корни из чисел [2^NB,2^(NB+2)-1] в fixed point с точностью NB+2 бит
  static int a[3*(1<<NB)]={...}; 
  return a[x-(1<<NB)]<<(k>>1);
}

Zefick
> Intel Core i3 (всего 4000 руб, может даже дешевле, если подержаный)

Я чё, быдлокодеров должен финансировать? Покупать новый комп только из-за того, что очередной педиковатый дизайнер из дуровской когорты решил, что полупрозрачная гей-перделка - это красиво? А пошли они науй!!!

Bishop
> потому версию SSE и просил. Посмотри в CPU-Z что у тебя есть, я тебе напишу под
> данную версию

Ну вот код из 0-поста он держит.
И даже действительно быстро получается, (в отличие от MMX, работающего у меня так же медленно, как побайтовое сложение с проверкой переполнения на чистом паскалокоде).

  cvtsi2ss xmm0,eax
  sqrtss   xmm0,xmm0
  cvtss2si eax,xmm0

Aslan
> Подсчитать кол-во значащих бит, делить на 2, умножить на предвычисленный корень
> из первых 6 или 8

Хорошо, перепиши мой код из 47 поста на С и сравни скорость. Ну и с "кармаковским" вариантом сравни (когда я его придумал, я не знал, что он кармаковский).

TarasB
На твоем компе могуть быть совсем другие результаты, наверное наибольшие тормоза будут от if-ов, быстрее всего команда сопроцессора, метод Ньютона (с делением) - даже одна итерация значительно повысит точность при хорошем начальном приближении, я еще писал эмуляцию float