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

Question

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

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

| an - b - round (an - b) |

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

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

Answer 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).

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

Answer 2

Звучит так, будто вы ищете что-то вроде непрерывных дробей ...

Как они связаны?Предположим, вы можете заменить 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.

Answer 3

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

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

Answer 4

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