与纵横比匹配的最小尺寸

Question

我需要找到长宽比恰好(或在0.001以内)某个值的最小尺寸.这样做有什么快速的数学技巧或框架技巧吗？

这是我运行的当前坏主意的伪代码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

异常.你需要找到最大的公约数,并用它来划分宽度和高度.该算法由欧几里德提出,已有两千三百年的历史.细节在这里.