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

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.

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.