Approximation of a common divisor closest to some value?

Question

Say we have two numbers (not necessarily integers) x1 and x2. Say, the user inputs a number y. What I want to find, is a number y' close to y so that x1 % y' and x2 % y' are very small (smaller than 0.02, for example, but lets call this number LIMIT). In other words, I don't need an optimal algorithm, but a good approximation.

I thank you all for your time and effort, that's really kind!

---

Let me explain what the problem is in my application : say, a screen size is given, with a width of screenWidth and a height of screenHeight (in pixels). I fill the screen with squares of a length y'. Say, the user wants the square size to be y. If y is not a divisor of screenWidth and/or screenHeight, there will be non-used space at the sides of the screen, not big enough to fit squares. If that non-used space is small (e.g. one row of pixels), it's not that bad, but if it's not, it won't look good. How can I find common divisors of screenWidth and screenHeight?

Answer 1

I don't see how you can ensure that x1%y' and x2%y' are both below some value - if x1 is prime, nothing is going to be below your limit (if the limit is below 1) except x1 (or very close) and 1.

So the only answer that always works is the trivial y'=1.

If you are permitting non-integer divisors, then just pick y'=1/(x1*x2), since the remainder is always 0.

Without restricting the common divisor to integers, it can be anything, and the whole 'greatest common divisor' concept goes out the window.

Answer 2

x1 and x2 are not very large, so a simple brute force algorithm should be good enough.

Divide x1 and x2 to y and compute floor and ceiling of the results. This gives four numbers: x1f, x1c, y1f, y1c.

Choose one of these numbers, closest to the exact value of x1/y (for x1f, x1c) or x2/y (for y1f, y1c). Let it be x1f, for example. Set y' = x1/x1f. If both x1%y' and y1%y' are not greater than limit, success (y' is the best approximation). Otherwise add x1f - 1 to the pool of four numbers (or y1f - 1, or x1c + 1, or y1c + 1), choose another closest number and repeat.