How to find the closest size to but no greater than W x H by aspect ratio?

Question

Giving the size W x H and the aspect ratio X : Y, how to find the closest size within W x H that matching X : Y? For example:

Input

W = 599, H = 599, X = 1, Y = 2 

Output

W = 299, H = 598

Input

W = 757, H = 611, X = 3, Y = 2

Output

W = 756, H = 504

all of W,H,X,Y are positive integers

Answer 1

An algorithm:

1. reduce $X:Y$ to lowest terms, so for example if given $6:4$ then change this to $3:2$

2. find the smaller of $\frac W X$ and $\frac H Y$ with the reduced $X$ and $Y$ from (1), and round this down to an integer; let's call it $k$

3. use $kX$ and $kY$ with the reduced $X$ and $Y$ from (1)

So with $W = 599, H = 599, X = 1, Y = 2$, you start with $X$ and $Y$ in lowest terms. Then $k = \lfloor\min(\frac{599}{1},\frac{599}{2})\rfloor=\lfloor\min(599,299.5)\rfloor=299$ and multiplying this by $1:2$ you get $299 \times 598$

while with $W = 757, H = 611, X = 1, Y = 2$, you start with $X$ and $Y$ in lowest terms. Then $k = \lfloor\min(\frac{757}{3},\frac{611}{2})\rfloor=\lfloor\min(252.33,305.5)\rfloor=252$ and multiplying this by $3:2$ you get $756 \times 504$