2
$\begingroup$

For a given integer $n\in\mathbb{N}^*$, I want to find a pair $(x,y)\in{\mathbb{N}^*}^2$ such that $x*y=n$ and $|y-x|$ is as small as possible.

A naive algorithm I found is :

for k = floor(sqrt(n)) to 1 step -1
  if n/k is integer then
    return (k, n/k)
  end if
end for

Although I am almost certain there is a more efficient way to do this, I cannot find one.

$\endgroup$
  • $\begingroup$ Actually, the closer pair should be the numbers as close to $\sqrt{n}$ as possible. $\endgroup$ – Ertxiem Apr 30 at 13:10
  • $\begingroup$ @Ertxiem True, but it doesn't help me to find a better solution. This is actually what my naive algorithm uses: it starts at $\sqrt{n}$ and check every integer down to 1 until it finds a divisor $\endgroup$ – Annyo Apr 30 at 13:19
  • 1
    $\begingroup$ $x$ and $y$ must be (products of) prime factors of $n$. Rather than trying every integer, you should just find all prime factors and then consider their products. At least for large numbers, that will be vastly faster than trying all numbers. $\endgroup$ – Wolfgang Bangerth Apr 30 at 14:14
  • $\begingroup$ @WolfgangBangerth Although your argument is totally valid, complexity-wise, I think that the prime factorization would already outweigh Annyo's initial algorithm. $\endgroup$ – Tolga Birdal Apr 30 at 14:18
  • $\begingroup$ @Annyo I was agreeing with you, that you should start from $\sqrt{n}$ downwards. $\endgroup$ – Ertxiem Apr 30 at 14:43
0
$\begingroup$

Note that although there could be more efficient algorithms, what you found is not a bad algorithm. I will analyze this a little bit.

Let us write down the problem formally as a constrained discrete optimization problem: $$ (x^\star, y^\star) = \arg\min_{(x,y) \in \mathbb{Z_{+}}} \Big(E \triangleq \big(y-x\big)^2 + \lambda(x*y - n)^2 \Big) $$ Note that for positive integers the $L_2$ norm will attain the same minimum as $L_1$. So I'll stick to it. $\lambda$ is a Lagrange multiplier and the right-most term is the non-linear constraint. Even if we can compute the partial derivatives and use the method of Lagrange multipliers, the problem is not easy to solve due to the parameters restricted to a discrete space. Hence we will relax the integer constraint to real numbers and solve the problem for $\mathbb{R}$. The relaxed optimum would be attained as follows: $$ x^\star = \arg\min_{x \in \mathbb{R}} \Big(\tilde{E} \triangleq \big(x-\frac{n}{x}\big)^2 \Big) $$ We achieved this by substitution the constraint : $y \gets \frac{n}{x}$. Note that this is also suggested by the Largange optimization: $$ \frac{\partial E}{\partial \lambda} = xy - n^2 = 0 \implies x=\frac{n}{y} \text{ or } y=\frac{n}{x}. $$

Now differentiating w.r.t. $x$: $$ \begin{align} \frac{d \tilde{E}}{dx} = 2\big(x-\frac{n}{x}\big) &= 0\\ x^2 &= n \\ x = \sqrt{n} \end{align} $$ gives the optimal solution for the relaxed problem. For negative numbers $x = -\sqrt{n}$ is also the optimum. This we could already detect from the sign of the input. Having solved the relaxed problem, a typical optimizer would operate by projecting the solution into the feasible set and/or applying a projected gradient descent. The initial feasible solution is $x_0 = \lfloor \sqrt{n} \rceil$. $\lfloor \cdot \rceil$ is the rounding operation or in fancy words the projection onto the integers. From here, it is possible to walk on the Euclidean discrete manifold of 1-dimensional integers by your method: taking steps of $+1$ or $-1$ depending on the direction. That would amount to a gradient descent by the step size $h=1$.

And these steps are what you are following implicitly when arriving at the algorithm you proposed. Unfortunately, the worst case complexity of this algorithm is attained when the number is prime and we have only 2 divisors: $1$ and $n$, the number itself. Therefore, the worst case complexity reaches to $O(\sqrt{n})$. As $n\rightarrow \infty$, this would resemble a linear search (it is worse than $\log$). Now, the set of integers is a totally ordered set. Using this property, instead of using a linear search, one could think of a binary search variant. But as clarified by @WolfgangBangerth, such an algorithm would not exist bounding the complexity in: $O(\log(\sqrt{n}))<C\leq O(\sqrt{n})$.

Even though this might not be the exact answer you were looking for, I thought it would give a perspective to develop better solutions. For instance, the integer programming community might have a better solution.

$\endgroup$
  • 3
    $\begingroup$ This answer uses a lot of complicated words, but it doesn't really provide anything useful. First, the formulation above is not a Lagrangian formulation for the optimization problem (in which case the constraint would appear linearly, not quadratically). Secondly, the whole formulation doesn't yield anything we don't already know: That among the real numbers, $n$ factors into $\sqrt{n}$ and $\sqrt{n}$. We don't need a complicated formulation for this. $\endgroup$ – Wolfgang Bangerth Apr 30 at 15:25
  • $\begingroup$ Third, the speculation of there being a binary search algorithm that is faster really can't be true: If there were such an algorithm, then factoring large numbers into primes would be easy. But it isn't. And so such an algorithm can't exist. With the algorithm as shown, you really can't avoid the ${\cal O}(\sqrt{n})$ complexity. The only way around it is a smarter algorithm to find the prime factors (for example, if your numbers are small enough that you can use a table of all prime numbers up to $\sqrt{n}$) and then use those (because there are far fewer prime factors than $\sqrt{n}$). $\endgroup$ – Wolfgang Bangerth Apr 30 at 15:27
  • $\begingroup$ @WolfgangBangerth, I fully agree that it doesn't say anything new. I even wrote this in my response that I would not be answering the question. But it can provide a perspective to the author of the question in seeking new possibilities. If $O(\log(n))$ is unachievable, then at least we know the complexity is bounded $O(\log(n))<C\leq O(\sqrt{n})$ up to some scalars. $\endgroup$ – Tolga Birdal Apr 30 at 16:50
  • $\begingroup$ @WolfgangBangerth, And with all due respect, I'm not a mathematician so please enlighten me on this: What makes the method of Lagrange multipliers require a linear constraint? I believed eq. 1 can describe a constrained problem. $E$ is indeed a function of $\lambda$ and both the data term and the constraints have continuous first partial derivatives. $\endgroup$ – Tolga Birdal Apr 30 at 17:01
  • $\begingroup$ If you square the constraint, you get a degenerate problem that does not satisfy the LICQ (the Linear Independence Constraint Qualification). The problem does then not, in general, have a unique Lagrange multiplier at the optimality point. $\endgroup$ – Wolfgang Bangerth May 1 at 2:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.