Minimum size that matches aspect ratio

Question

I need to find the minimum size that has an aspect ratio of exactly (or within 0.001) some value. Are there any quick math tricks or framework tricks for doing this?

Here's the pseudo code for the current bad idea I had running in O(n^2):

epsilon = 0.001;

from x = 1 to MAX_X
{
  from y = 1 to MAX_Y
  {
    if(Abs(x / y - aspectRatio) <= epsilon)
    {
      return new Size(x, y);
    }
  }
}
return Size.Empty;

Answer 1

The aspect ratio is the ratio between x and y. You can define the aspect ratio as x / y or y / x.

The minimum aspect ratio is 0 / 0.

Some other minimum has to be defined, either a minimum x or a minimum y.

min x = (min y * x) / y

min y = (min x * y) / x

Answer 2

You can write aspectRatio as a fraction (if you want it up to a presicion of 0.001, than you can use round(aspectRatio,3)/1000 )

Then, simplify this fraction. The resulting fraction is the x/y you're looking for.

Answer 3

A quicker way, but still not formulaic would be to only look at possible y values instead of iterating up to MAX_Y. e.g.:

    static Size FindMinSize(double requiredRatio, double epsilon)
    {
        int x = 1;
        do
        {
            int y = (int)(x * requiredRatio);
            if (Test(x, y, requiredRatio, epsilon))
            {
                return new Size(x, y);
            }

            y = (int)((x + 1) * requiredRatio);
            if (Test(x, y, requiredRatio, epsilon))
            {
                return new Size(x, y);
            }
            x++;
        } while (x != int.MaxValue);

        return new Size(0, 0);
    }

    static bool Test(int x, int y, double requiredRatio, double epsilon)
    {
        double aspectRatio = ((double)y)/x;
        return Math.Abs(aspectRatio - requiredRatio) < epsilon;
    }

Answer 4

Instead of testing all possible combinations, just increase the side that gets you closer to the aspect ratio:

public static Size GetSizeFromAspectRatio(double aspectRatio) {
  double epsilon = 0.001;
  int x = 1;
  int y = 1;
  while (true) {
    double a = (double)x / (double)y;
    if (Math.Abs(aspectRatio - a) < epsilon) break;
    if (a < aspectRatio) {
      x++;
    } else {
      y++;
    }
  }
  return new Size(x, y);
}

Answer 5

Unusual. You need to find the greatest common divisor and divide width and height by it. The algorithm is by Euclid and is two thousand three hundred years old. Details are here.