7

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?

Ian Medeiros
  • 1,746
  • 9
  • 24
Fatso
  • 1,278
  • 16
  • 46
  • 1
    Do you realize that % returning values are exclusively integers? Your approach to solve the squares fitting to the screen is fundamentally wrong. Are you trying to draw squares of a fixed size evenly spaced given a defined drawing area? – Ian Medeiros Feb 09 '12 at 14:21
  • Exactly what I am trying, Ian... – Fatso Feb 09 '12 at 16:50
  • that 0.02 are absolute or relative? – Gangnus Feb 09 '12 at 22:38
  • The 0.02 is absolute, Gangnus. – Fatso Feb 10 '12 at 07:16
  • Seriously, am I missing a point here? It's IMPOSSIBLE to get 0.02 from a % operation. You can't get any non integer value! That makes absolutely no sense! Whats the difference between relative or absolute error if that's a invalid point? – Ian Medeiros Feb 10 '12 at 13:59
  • I actually didn't know that : I meant the remainder after division. I believe I should think more about my questions before I write them. I often confuse maths and computer science. – Fatso Feb 10 '12 at 17:40
  • Did you solved your problem? – Ian Medeiros Feb 21 '13 at 19:16

4 Answers4

2

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.

Phil H
  • 19,928
  • 7
  • 68
  • 105
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.

Evgeny Kluev
  • 24,287
  • 7
  • 55
  • 98
1

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:

Squares side by side

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:

Evenly spaced squares

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?

Ian Medeiros
  • 1,746
  • 9
  • 24
  • No, Ian. It has to be squares. Your solution only solves the problem one direction at a time, but it doesn't make sure `space_w` = `space_h` Thanks a lot for the effort, though! – Fatso Feb 09 '12 at 18:49
  • In this case, do you realize that the optimal solution will be the smallest between space_w and space_h? – Ian Medeiros Feb 09 '12 at 19:02
  • space_w or space_h will not be the optimal solution only if you don't need to use the max numbers of squares. – Ian Medeiros Feb 10 '12 at 06:31
  • It's worth a try... At the moment I was just using common divisors which works great but if the screen doesn't have handy dimensions to work with, it won't work well. – Fatso Feb 10 '12 at 08:06
  • Are you trying to find a perfect size of square to fit on the screen or the square must be of fixed size? – Ian Medeiros Feb 10 '12 at 13:57
  • What's the difference man? You're talking nonsense... The square should have a fixed size and if you fill the screen with squares of that size, it should fit. – Fatso Feb 11 '12 at 17:18
  • I'm trying to understand why my answer is not the right one for your question. By your own answer to your question, looks like you are trying to change the resolution of the screen or the square size can be of any size to fit better, since you simple picked a 1440x900 resolution from nowhere. I REALLY DONT GET what are the constrains of your problem. – Ian Medeiros Feb 11 '12 at 18:53
  • My own answer is not really an answer to this thread. I just wanted to let people know what I decided to do. You answer could work, I'll have to test that, but I haven't had time to implement it yet (I have exams). – Fatso Feb 11 '12 at 18:55
  • 1440x900 is my own computer screen's size. I use it to create examples. – Fatso Feb 11 '12 at 18:55
  • I'll try to rephrase the issue : *I want to fill my screen with squares. I want an algorithm so that I can decide how big those squares have to be so that they can fill the screen. If there are multiple possible sizes, I want the size that is closest to some value `y`*. – Fatso Feb 11 '12 at 18:56
-1

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.

Community
  • 1
  • 1
Fatso
  • 1,278
  • 16
  • 46
  • You really don't know how to explain what you are trying to do. – Ian Medeiros Feb 10 '12 at 14:21
  • It's always the same kind of thing on this website : when someone doesn't understand, they down-vote and say things like "you can't explain things well, you're stupid, ...". I don't see how the hell I can explain my problem better. I learned english at school, so give me a break. – Fatso Feb 10 '12 at 17:37
  • The english is not your problem here, but your basic math assumptions. Your answer makes absolutely no sense in terms of the problem described at the end of your question, that's the mistake you are making. Your answer here were: "I decided to change the screen height and width for a pre defined magic number that don't cause me trouble". While this seens to work, it's NOT the solution to your question. In fact, your first question makes absolute no sense and I tried to solve your second one on my answer. I recommend you to EXPLAIN IN DETAIL what you are trying to do. – Ian Medeiros Feb 10 '12 at 21:03
  • Wait, can you please tell me what you don't understand? What sentence in particular? You're putting words in my mouth. – Fatso Feb 11 '12 at 17:13
  • When you mean "I tried multiple cases (x1 = 878000 and x2 = 1440000 and some others), and none of them had good results." What you call by good results? – Ian Medeiros Feb 11 '12 at 18:39
  • Common divisors. No common divisors were found. The common integer divisors of 878000 and 1440000 are 1, 2, 4, 5, 8, 10, 16, 20, 25, 40, 50, 80, 100, 125, 200, 250, 400, 500, 1000, 2000. You will notice that that are the same common integer divisors as those of 878 and 1440. – Fatso Feb 11 '12 at 18:42
  • What you mena by "I decided to take advantage of the fact that screenWidth and screenHeight are good numbers to work with" ? – Ian Medeiros Feb 11 '12 at 18:46
  • The common divisors of 878000 and 1440000 are COMPLETELY different. 10, 20, 40, 100, 125, 200, 250, 400, 500, 1000, 2000 are NOT common divisors of 878 and 1440. I'm really missing your point here. – Ian Medeiros Feb 11 '12 at 18:51
  • Those numbers are the width and the height of a screen, so they probably have a lot of common divisors since screens use particular dimensions. For example, my laptop screen is 1440x900, and those numbers have lots of common divisors compared to, for example, 1440x878. – Fatso Feb 11 '12 at 18:51