# Approximate two integers of equation (fastest algorithm)

Not sure if it's a right place, though...

I have a formula $\frac{C_1}{C_2} = C = {x}{y}$, where $C_1, C_2, C, x, y \in \mathbb{N}$, more precisely $x = [1 \dots 32], y = [1 \dots 8192], C = [1 \dots 32*8192]$.What is the fastest algorithm to find $x$ and $y$ that their multiplication would have a minimum difference to $C$?

Consider two examples:

$C = 10000$, the answer is $(2, 5000)$, or $(5, 2000)$ and so on.

$C = 67811$, the answer is $(19, 3569)$.

• Presumably by your double periods (now changed to ellipses) you mean a range of numbers. What does that mean for $C$? For any given value $C$ what is wrong with rounding it and taking $x=1, y=$ the rounded value? Jun 2, 2017 at 14:25
• It looks like $C$ may not be a whole number because of the $C_2$ in the denominator. It has to be because $x$ and $y$ are. Why are we talking of $C_1,C_2?$ Jun 2, 2017 at 14:41
• Also, how "fast" do you actually need to be? Feels like you can just brute force the whole thing since $x$ only has 32 different possible values... You'll end up with a constant time method. Jun 2, 2017 at 14:48
• Ok, so $C$ is computed from two integers $C_1$ and $C_2$... do you want $xy$ to be the best approximation of $C$, or the best approximation of $C_1/C_2$? From my fuzzy memory of integer arithmetic, when computing a quotient, you round down to $0$ (so you take the floor with positive values)... Whereas an approximation of the rational quotient could be closer to the ceil value. Jun 2, 2017 at 15:28
• One more thing, if $(x,y)$ minimizes $\lvert \frac{C_1}{C_2} -xy\rvert$, then it also minimizes $\lvert C_1-xyC_2\rvert$. Assuming you can store $C_1$ in memory, you probably can also compute $xyC_2$ most of the time...? There may be some issue when the best approximation $xy$ is larger than the ratio, and $C_1$ is close to the greatest value you can store in memory... Jun 2, 2017 at 17:06

You want $x$ and $y$ to be the factors of $C$ closest to $\sqrt C$, one above and one below. For small numbers like you are talking about, you can factor $C$ and check all the factors.
Added after the comments. As $x$ is limited to $[1,32]$ I would suggest you take $\sqrt C$ and round it down to $32$ or to the next whole number if the square root is below $32$. Then just check numbers for whether they divide into $C$ exactly, progressing downward. The first one that divides $C$ exactly is the $x$ you want, then $y=\frac Cx$. It might be faster first to divide $C$ by small primes to eliminate possibilities. If you try $2$ first and it fails you don't have to try any even numbers.
• Thanks. I've got an idea (don't know if it's right one), so, $p = \sqrt{C};$, initial $x = \frac{p}{17}$, where $17 = \sqrt{\frac{8192}{32}} + 1$. It will approximate my number pretty well, so then it will be only few loops to get closest. Would it work? Jun 2, 2017 at 16:08
• I thought you needed $x,y$ to be integers and factors of $C$. So if $C=200,000=2^65^5$ you would want $x=2^25^3=500, y=2^45^2=400$ Jun 2, 2017 at 16:32
• Yes, that's correct (there is $\sqrt{}$ available for integers), except in your example $x$ is out of boundaries. So, the answer to the above $(500*16 = 8000, 400/16 = 25)$. Jun 2, 2017 at 16:34
• Then you should (almost) always take $x$ to be the largest factor of $C$ that is less than or equal to $32$. In your example of $10000$ it would appear that $x$ should be $20$ and $y$ should be $500$ as that is as close as they can get. Jun 2, 2017 at 16:36
• To the update: obviously square root will be always above 32 and thus there is the same as going forward from 1 to 32. Additionally the division is extremely slow operation, so, it would be multiplication there to compare with. I thought more and just come up with another approach: start number for the loop would be $C/8192 + 1$. It eliminates more steps on higher $C$ along with stop looping immediately iff the $C - xy = 0$. Jun 2, 2017 at 21:05