Difference of the Closest Multiples of Two Real Numbers

Question

I am trying to find an algorithm / function for a computer program that I am working on. It looks like the following:

$$F(f_1,f_2) = \Delta $$

where $\Delta$ is to be the smallest possible difference among a constrained set of integer multiples of $f_1$ and integer multiples of $f_2$. To put it another way,

$$\Delta = \left\lvert n_1f_1 - n_2f_2\right\rvert\,\,s.t.\,\,\forall a_1,a_2 \in \{z_1,z_1+1,...,z_2\}, \left\lvert n_1f_1-n_2f_2 \right\rvert \le \left\lvert a_1f_1-a_2f_2 \right\rvert \; where\; z_1,z_2 \in \mathbb Z_{\gt 0}$$

Since I only need this for a very specific application, if it helps, we can also assume a few things about $f_1,\,f_2,\,z_1,$ and $z_2$:

$f_1$ and $f_2$ are musical notes from a 12 note, equally tempered scale. This means that $f_1 = (\sqrt[12]{2})^{c_1}f_0$ and $f_2 = (\sqrt[12]{2})^{c_2}f_0$ for some integers $c_1$, $c_2$ and some fundamental frequency $f_0$. Typically $f_0$ is $440hz$. This cannot be assumed here, but we can assume that $f_0$ is some known constant.

We can also assume that $z_1=1$ and $z_2=6$

Obviously, this problem could be solved very easily with a brute force computer program, as illustrated in the pseudo code below:

function(f1,f2){
      var delta = f1 - f2
      var temp = 0
      for(i=1;i<7;i++) {
         for(k=1;k<7;k++){
            temp = abs(i*f1 - k*f2)
            if(temp < delta){
               delta = temp
            }
         }
      }

      return delta
   }

But, there has to be a more elegant solution, right? Can someone help me out here?

Answer 1

First, I'm not entirely sure what's wrong with the "brute force" approach: it will solve your problem, and will do so in a trivial amount of time on even the simplest and slowest computer.

However, let's say you wanted to solve the problem for much larger $z_2$. You are essentially trying to solve the Diophantine approximation problem of finding a "best" rational approximation to $f_1/f_2$, and the general approach is to look at the convergents of the continued fraction of $f_1/f_2$.

So for example, let's say $f_1=f_0$ and $f_2 = 2^{4/12}f_0$ (i.e. a major third).

We have $$f_1/f_2 = \cfrac{1}{1+\cfrac{1}{3+\cfrac{1}{1+ \cfrac{1}{5+\cfrac{1}{1+\ddots}}}}}$$ and the convergents are $$1, \frac{3}{4}, \frac{4}{5}, \frac{23}{29},\ldots$$ so if $z_2 = 6$, you want $n_1 = 5, n_2 =4$; if $z_2 = 30$, you can do better by setting $n_1 = 29$ and $n_2 = 23$.