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

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

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

| an - b - раунд (a n - b)|

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

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

Источник

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.

Источник

Вы можете вычислить непрерывную дробь для отношения 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).

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

Источник

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

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

Источник

Сначала рассмотрим более простой случай, когда 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.

Источник
Другие вопросы по тегам