Question

Given a number c, what is the smartest way to find |x - y| such that x * y =c and |x - y| is minimum

Answer 1

As @Goldstern commented, if you don't have the factorization of $c$, then in general you can't even necessarily find non-trivial factors.

Even assuming you're given the full prime factorization of $c$ this looks like an optimization version of the partition problem, so I think an exact solution will still be hard in the most general case.

Write $c=\prod p_i$ as a product of primes (allowing repetitions), then your question is finding a partion of the multiset $S=\{\log p_i\}$ into $S1$ and $S2$ so that $|\exp(\sum_{S1})-\exp(\sum_{S2})|$ is minimized. Since $\sum_{S1}+\sum_{S2}$ is fixed, this also corresponds to the minimum of $|\sum_{S1}-\sum_{S2}|$.

While the problem is usually posed as a discrete one, I expect that some of the algorithms referenced on Wikipedia can be applied effectively.

Answer 2

I will suggest the following:

First, assume $x,y \in \mathbb{R}$, as the line $y=x$ and the hyperbola $y=\frac{c}{x}$ intersect, denote the intersection coordinate as $(x_0,y_o)$. If $(x_0,y_o)$ is an integer coordinate, then $|x_0-y_0|=0$ is the minimum.

If $(x_0,y_o)$ is not an integer coordinate. then consider the $x$-coordinate of $x_0$, say $[x_0]$ and $\lceil x_0 \rceil$, the greatest and least integer respectively. Now look for the $y$-coordinate $\frac{c}{[x_0]}$ and $\frac{c}{\lceil x_0 \rceil}$, If any of these $y$-coordinates is an integer, then just take the difference $|x_0-\frac{c}{[x_0]}|$ or $|x_0-\frac{c}{\lceil x_0 \rceil}|$ , one has the desired result, If none $\frac{c}{[x_0]}$ and $\frac{c}{\lceil x_0 \rceil}$ are integer, then like before repeat the process, this time consider $x$-corodinates $[x_0]-1$ and $\lceil x_0 \rceil +1$ and proceed similarly. Once one knows $c$ before, then it is easy to proceed.

The main thing is one has to know divisors of $c$ to make the above process, quick. Also $c$ has to be small integer, else, there is no smart or easy way.