How can I minimize two integers so that their product is less than a certain value?

Question

Given two integers, how can I minimize them so that their product is less than some other value, while maintaining their relative ratio?

That's the formal problem. The practical problem is this: I have width/height pixel resolutions containing random values (anywhere from 1 to 8192 for either dimension). I want to adjust the pairs of values, such that their product doesn't exceed some total number of pixels (ex: 1000000), and I need to ensure that the aspect ratio of the adjusted resolution remains the same (ex: 1.7777).

The naive approach is to just run a loop where I subtract 1 from the width each time, adjusting the height to match the aspect ratio, until their product is under the threshold. Ex:

int wid = 1920;
int hei = 1080;
float aspect = wid / (float)hei;
int maxPixels = 1000000;
while (wid * hei > maxPixels)
{
    wid -= 1;
    hei = wid / aspect;
}

Surely there must be a more analytical approach to this problem though?

Answer 1

Edit: Misread the original question.

Another way to word your question is with a W and H what is the largest a and b such that a/b = W/H and a*b < C where C is your limit on .

To do so, find the D = gcd(W,H) or greatest common divisor of W and H. Greatest common denominator is commonly found using the Euclidean Algorithm.

Set x = W/D and y = H/D, this is minimal solution with the same ratio.

To produce the maxima under C, start with the inequality of F*x*F*y <= C where F will be our scale factor for x and y

Algebra:

F^2 <= C/(x*y)

F <= sqrt(C/(x*y))

Since we want F to be a whole number and strictly less than the above,

F = floor(sqrt(C/(x*y)))

This will give you a new solution A = x*F and B = y*F where A*B < C and A/B = W/H.