Given a number c, what is the smartest way to find |x - y| such that x * y =c and |x - y| is minimum
5
-
$\begingroup$ Need more clarification: whether $x, y \in \mathbb{R}$ or $\mathbb{C}$. $\endgroup$– NeerajCommented Jun 2, 2012 at 7:38
-
$\begingroup$ x, y are inegers $\endgroup$– SahilCommented Jun 2, 2012 at 8:03
-
$\begingroup$ I don't think this is smart enough, but one approach is to make a sorted list of the divisors of $c$ (see velocityreviews.com/forums/…) and then do a binary search for the divisor that is closest to $\sqrt{c}$. $\endgroup$– Tony HuynhCommented Jun 2, 2012 at 8:52
-
$\begingroup$ What does "smart" mean? How large are your numbers? If $c$ is very large, then no smart (i.e., fast) way of finding nontrivial $x,y$ with $x*y=c$ is known. $\endgroup$– GoldsternCommented Jun 2, 2012 at 9:21
-
$\begingroup$ I agree with Goldstern, $c$ should not be very lagre. $\endgroup$– NeerajCommented Jun 2, 2012 at 9:31
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
-
2$\begingroup$ And conversely, given a hard instance $S \subset {\bf R}^{> 0}$ of the partition problem, one can find $C>0$ and primes close enough to $\exp C\cdot S$ that their product is a hard instance of the nearest-factor problem at hand. $\endgroup$ Commented Jun 2, 2012 at 15:51
$\begingroup$
$\endgroup$
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.
