Быстрый алгоритм минимизации псевдодиофантового уравнения

Мы ищем алгоритм для решения этой задачи в рамках O (N).

Учитывая два вещественных числа a и b (без потери общности можно предположить, что они находятся между 0 и 1) Найдите целое число n между -N и N, которое минимизирует выражение:

/ a n - B - round(a n-b) /

Мы думали, что евклидов алгоритм может хорошо работать для этого,но не можем понять его. Это, безусловно, выглядит так, что должны быть гораздо более быстрые способы сделать это, чем через исчерпывающий поиск по целым числам n.

Примечание: в нашей ситуации a и b могут часто меняться, поэтому фиксация a и b для таблицы подстановки возможна, это становится отчасти некрасивым, поскольку N также может меняться. Мы еще не заглядывали подробно в таблицу поиска, чтобы увидеть, насколько мала она в зависимости от N.

4 3
algorithm minimum

4 ответа:

Похоже, вы ищете что-то вроде непрерывных дробей...

Как они связаны? Предположим, что вы можете заменить b рациональным числом b1/b2. Теперь вы ищете целые числа n и m такие, что an-b1/b2 приблизительно m. иными словами, вы ищете n и m такие, что (m+(b1/b2))/n = (mb2+b1)/nb1, рациональное число, приблизительно a. множество a1 = mb2+b1 и a2 = nb1. Найти значения для a1 и a2 из аппроксимации непрерывных дробей и решить для n и m.

Другой подход может быть следующим:

  1. найти хорошие рациональные приближения для a и b: a ~ a1/a2 и b ~ b1/b2.
  2. решите n (a1/a2)-(b1/b2) = m для n и m.
Хотя я не слишком уверен, что это сработает. Точность, необходимая для a, зависит от n и b.
1

Вы эффективно ищете целое число N, которое делает выражение aN - b максимально близким к целому числу. Являются ли a и b фиксированными? Если да, то вы можете предварительно вычислить таблицу поиска и получить O (1): -)

Если не рассматривать поиск N, который делает aN близким к I + b для всех целых чисел I.

1

Вы можете вычислить непрерывную дробь для отношения a/b. вы можете остановиться, когда знаменатель больше, чем N, или когда ваше приближение достаточно хорошо.

// Initialize:
double ratio = a / b;
int ak = (int)(ratio);
double remainder = ratio - ak;

int n0 = 1;
int d0 = 0;

int n1 = ak;
int d1 = 1;

do {
    ratio = 1 / remainder;
    ak = (int)ratio;
    int n2 = ak * n1 + n0;
    int d2 = ak * d1 + d0;
    n0 = n1;
    d0 = d1;
    n1 = n2;
    d1 = d2;
    remainder = ratio - ak;
} while (d1 < N);

Значение для n, которое вы ищете, равно d0 (или d1, если оно все еще меньше, чем N).

Это не обязательно дает вам минимальное решение, но, вероятно, это будет очень хорошее приближение.
1

Сначала рассмотрим более простой случай, когда b=0 и 0

Пусть step_size = 1 

Step 1. Let v=a
Step 2. Let period size p = upper_round( 1/v ).
Step 3. Now, for n=1..p, there must be a number i such that F(v,i) < v.
Step 4. v = F(v,i), step_size = stepsize * i
Step 5. Go to step 2

Как вы можете видеть, вы можете уменьшить F (v, *) до любого уровня, который вы хотите. Окончательное решение n = step_size.

0