3
$\begingroup$

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)$.

$\endgroup$
12
  • $\begingroup$ 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? $\endgroup$ Jun 2, 2017 at 14:25
  • 1
    $\begingroup$ 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?$ $\endgroup$ Jun 2, 2017 at 14:41
  • 1
    $\begingroup$ 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. $\endgroup$
    – N.Bach
    Jun 2, 2017 at 14:48
  • 1
    $\begingroup$ 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. $\endgroup$
    – N.Bach
    Jun 2, 2017 at 15:28
  • 1
    $\begingroup$ 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... $\endgroup$
    – N.Bach
    Jun 2, 2017 at 17:06

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
14
  • $\begingroup$ 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? $\endgroup$
    – 0andriy
    Jun 2, 2017 at 16:08
  • $\begingroup$ 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$ $\endgroup$ Jun 2, 2017 at 16:32
  • $\begingroup$ 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)$. $\endgroup$
    – 0andriy
    Jun 2, 2017 at 16:34
  • $\begingroup$ 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. $\endgroup$ Jun 2, 2017 at 16:36
  • $\begingroup$ 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$. $\endgroup$
    – 0andriy
    Jun 2, 2017 at 21:05

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.