Finding multipliers to create nearly perfect squares

Question

Given a very large integer $n$, I wish to find integer multipliers $m$ such that the product is nearly a perfect square. Ideally this should be easy to compute and output a series of improved approximates. We'll define a quality measure as "nearly a perfect square" as minimizing the quantity $\sqrt{nm} - \left \lfloor\sqrt{nm}\right \rfloor$.

As an example with a small $n=87654321$ a useful series of better and better $m$ values can be brute force evaluated by exhaustively testing $m$ values starting at 1. Notice how the fractional remainder of the square root decreases monotonically as it finds better multipliers:

87654321 * 1       =      9362.3886375219 ^2
87654321 * 3       =     16216.1328003936 ^2  
87654321 * 6       =     22933.0749355598 ^2  
87654321 * 26      =     47739.0023565638 ^2
87654321 * 249     =    147736.0007885688 ^2
87654321 * 2766    =    492394.0006600405 ^2 
87654321 * 3469    =    551428.0003309589 ^2 
87654321 * 5751    =    710000.0000500000 ^2 
87654321 * 15967   =   1183037.0000160604 ^2
87654321 * 44374   =   1972200.0000136902 ^2
87654321 * 156685  =   3705957.0000048568 ^2
87654321 * 392125  =   5862717.0000030706 ^2
87654321 * 790738  =   8325359.0000010207 ^2
87654321 * 1555754 =  11677695.0000003850 ^2
87654321 * 1856354 =  12756075.0000003520 ^2

My question is how to generate this, or a similar, series of "good" $m$ values. I suspect the answer has to do with a continued fraction representation of $\sqrt n$ but I have had no luck turning that hunch into a working method.

An answer I'm not looking for is solving for the smallest $m$ that produces a perfect square. That method is to completely factor $n$, and forming $m$ as a product of all of the factors of $n$ with odd multiplicity. That's a great result but factoring $n$ is impractical for very large (hundreds of digits) values of $n$.

Thanks for help with this fun puzzle!

Answer 1

In PARI/GP you can find a good approximation to the $\sqrt{n}$. Sample code:

? r=bestappr(s=sqrt(n=87654321),10^10);
? print(r," ",frac((d=denominator(r))*s+.5)-.5," ",s*d)
11290906936405/1205985713 -6.97906177E-11  11290906936404.99999999993021