Approximation of a common divisor closest to some

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

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.

Answer 2

I believe I made a mistake, but I don't see why. Based on Phil H's answer, I decided to restrict to integer values, but multiply x1 and x2 by a power of 10. Afterwards, I'd divide the common integer divisors by that number.

Online, I found a common factors calculator. Experimenting with it made me realize it wouldn't give me any common divisors... I tried multiple cases (x1 = 878000 and x2 = 1440000 and some others), and none of them had good results.

In other words, you probably have to multiply with very high numbers to achieve results, but that would make the calculation very, very slow.

If anyone has a solution to this problem, that would be awesome. For now though, I decided to take advantage of the fact that screenWidth and screenHeight are good numbers to work with, since they are the dimension of a computer screen. 900 and 1440 have more than enough common divisors, so I can work with that...

Thank you all for your answers on this thread and on my previous thread about an optimal algorithm for this problem.

Answer 3

You want to fit the maximum amount of evenly spaced squares inside a fixed area. It's possible to find the optimal solution for your problem with some simple math.

Lets say you have a region with width = W and height = H, and you are trying to fit squares with sides of length = x. The maximum number of squares horizontaly and verticaly, that I will call max_hor and max_vert respectively, are max_hor=floor(W/x) and max_vert=floor(H/x) . If you draw all the squares side by side, without any spacement, there will be a rest in each line and each column. Lets call the horizontal/vertical rests respectively by rest_w and rest_h. This case is illustrated in the figure below:

Note that rest_w=W-max_horx and rest_h=H-max_vertx.

What you want is divide rest_w and rest_h equaly, generating small horizontal and vertical spaces of sizes space_w and space_h like the figure below:

Note that space_w=rest_w/(max_hor+1) and space_h=rest_h/(max_vert+1).

Is that the number you are looking for?

Answer 4

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.