A fast algorithm to minimize a pseudo Diophantine equation

Question

We're looking for an algorithm to solve this problem in under O(N).

given two real numbers a and b (without loss of generality you can assume they are both between 0 and 1) Find an integer n between -N and N that minimizes the expression:

|a n - b - round(a n - b)|

We have thought that the Euclidean Algorithm might work well for this, but can't figure it out. It certainly looks like there should be much faster ways to do this than via an exhaustive search over integers n.

Note: in our situation a and b could be changing often, so fixing a and b for a lookup table is possible, it gets kind of ugly as N can vary as well. Haven't looked in detail into the lookup table yet, to see how small we can get it as a function of N.

Answer 1

It sounds like you may be looking for something like continued fractions...

How are they related? Suppose you can substitute b with a rational number b1/b2. Now you are looking for integers n and m such that an-b1/b2 is approximately m. Put it otherwise, you are looking for n and m such that (m+(b1/b2))/n = (mb2+b1)/nb1, a rational number, is approximately a. Set a1 = mb2+b1 and a2 = nb1. Find values for a1 and a2 from a continued fractions approximation and solve for n and m.

Another approach could be this:

1. Find a good rational approximations for a and b: a ~ a1/a2 and b ~ b1/b2.
2. Solve n(a1/a2)-(b1/b2) = m for n and m.

I'm not too sure it would work though. The accuracy needed for a depends on n and b.

Answer 2

You are effectively searching for the integer N that makes the expression aN - b as close as possible to an integer. Are a and b fixed? If yes you can pre-compute a lookup table and have O(1) :-)

If not consider looking for the N that makes aN close to I + b for all integers I.

Answer 3

You can compute a continued fraction for the ratio a/b. You can stop when the denominator is greater than N, or when your approximation is good enough.

// 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);

The value for n you're looking for is d0 (or d1 if it is still smaller than N).

This doesn't necessarily give you the minimum solution, but it will likely be a very good approximation.

Answer 4

First, let us consider a simpler case where b=0 and 0 < a < 1. F(a,n) = |an-round(an)|

Let 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

As you can see you can reduce F(v, *) to any level you want. Final solution n = step_size.