2

I would like to find the integer x that minimizes a function. That is:

$$ x_{min} = \min_{x \in \mathbb{Z}}{(n - e^x)^2} $$

The goal is to write a program that computes the integer $x$ such that $e^x$ is closest to $n$, preferably avoiding conditionals.

Without the integer constraint, obviously $x_{min} = \ln{n}$, but how to go about this with the integer constraint?

rityzmon
  • 179

2 Answers2

1

Notice that since this is a parabola whose min is at $0$. It therefore suffices to find that integer closest to ln $n$.

user341502
  • 513
  • $x_{min}$ should either be $\lfloor\ln n\rfloor$ or $\lceil\ln n\rceil$, but it may not be the one closer to $\ln n$. eg when $n=245$, $\ln n$ is closest to $6$, but $e^5$ is closer than $e^6$ to $n$. – stewbasic Jul 29 '16 at 02:50
  • @stewbasic Yes, that's the crux of it. I realize a solution is to find the real number solution, then test the floor and ceiling to see which is closer, but I'd like to avoid conditionals, as I said. – rityzmon Jul 29 '16 at 02:55
  • @ritzymon could you elaborate why you want to avoid conditionals? I think that would be the easiest way. – stewbasic Jul 29 '16 at 02:59
  • @stewbasic CPU pipelining, basically. The fewer conditionals, the fewer false branches in execution. – rityzmon Jul 29 '16 at 03:23
0

The fact that the minimum is squared is irrelevant, if you take the absolute value instead. Therefore $$x_{min}=\min_{x\in Z}{|n-e^x|}$$ If x werent constrained to the integers, x would equal as you pointed out ln(n), but since it is constrained to integers, to find $x_{min}$, take $\min(e^{Floor(ln(n))},e^{Ceil(ln(n))})$ The minimum between those two will be your answer.

Ninja_Coder
  • 251
  • Thanks, but $\min$ implies a conditional because it would need to test which of two values is less and return that one. I'd like to avoid conditionals. – rityzmon Jul 29 '16 at 03:25
  • Oh sorry :(, I've been thinking about it for a couple of minutes and I can't think of a way to do it without any conditionals. If you find a solution please post it! I'm interested in seeing how that would happen. – Ninja_Coder Jul 29 '16 at 03:33