Multiplier search to find almost-squares

mathPuzzles · 2017-09-15, 20:02

I'm working on a packing puzzle and have hit a subproblem that's fun to think about by itself.

Given a very large integer $n$, I wish to find integer multipliers $m<n$ such that the product $nm$ is a better and better approximation to any perfect square. Ideally this should be easy to compute and output a series of improved approximates as the size of $m$ increases. 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:

Code:

    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. The brute force enumeration I used for this example does not scale when $n$ becomes more than 10 digits, and I want to find values for much larger $n$. I suspect the answer has to do with a continued fraction representation of $\sqrt n$ which leads to an efficient sequence of better and better rational approximations $\sqrt n$. But I have had no luck turning that hunch into a working method.

ie, for this example $n=87654321$ there's a continued fraction representation of $\sqrt n$ of [9362; 2, 1, 1, 2, 1, 11, 1, 1, 3, 1, 15, 2, 1, 3, 22, 21, 1, 5, 1, 11, 40, 86, 1, 1, 1, ...]. Maybe there's a way to turn this approximation sequence into corresponding $m$ values?

Another solution is literally perfect but impractical. It directly computes the smallest $m$ that produces a perfect square by completely factoring $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$.

There's a slight similarity to this problem with Lehman's extension to the Fermat factoring method. He notes that the Fermat factoring method is accelerated by using a sequential set of multipliers to "sample" all the possible residuals of the Fermat method tests. Those multipliers are formed by a continued fraction expansion. However the similarity to my problem is weak, it still may provide a clue.

My latest experiments were using a monte carlo approach. I generate a few thousand distributed values of $m$ and evaluate those for closeness quality. Then I use Newton's method to refine the best ones found to zoom into a local minimum. This doesn't work very well since the goal function is not smooth.

Thanks for any ideas with this fun puzzle!

science_man_88 · 2017-09-15, 20:37

well $\sqrt{nm}-\lfloor{nm}\rfloor = \sqrt{n}\sqrt{m}-\lfloor{\sqrt{n}\sqrt{m}}\rfloor$ if you think the square root will help.

mathPuzzles · 2017-09-15, 21:06

Quote:

Originally Posted by science_man_88

well $\sqrt{nm}-\lfloor{\sqrt{nm}}\rfloor = \sqrt{n}\sqrt{m}-\lfloor{\sqrt{n}\sqrt{m}}\rfloor$ if you think the square root will help.

In my Newton experiment I use a similar fact to iterate. The $\lfloor{\sqrt{n}\sqrt{m}}\rfloor$ term remains constant for small changes of $m$ so you can treat it as a constant when iterating. Of course this breaks down when $m$ crosses a transition to the next square, but for zooming into a very local optimum it's useful. The problem is that there are are literally $\sqrt m$ local minimum that can be tested, far too many to test exhaustively.

Or perhaps you're hinting of a totally different use of this representation?

science_man_88 · 2017-09-15, 21:10

Quote:

Originally Posted by mathPuzzles

In my Newton experiment I use a similar fact to iterate. The $\lfloor{\sqrt{n}\sqrt{m}}\rfloor$ term remains constant for small changes of $m$ so you can treat it as a constant when iterating. Of course this breaks down when $m$ crosses a transition to the next square, but for zooming into a very local optimum it's useful. The problem is that there are are literally $\sqrt m$ local minimum that can be tested, far too many to test exhaustively.

Or perhaps you're hinting of a totally different use of this representation?

nope I'm just being stupid I guess. we know m=n is the upper bound to being a square.

Dr Sardonicus · 2017-09-16, 14:02

It occurred to me that all your multiples had square roots that were slightly larger than the nearest integer. By demanding square roots that get closer to the nearest integer from either side, you get a different sequence. Since the example value was so small, I used core(), which is the (unique) square-free factor with a square cofactor, which is the largest square factor of n. In this case, the largest square factor is 9.

? n = 87654321;

? core(n)
%2 = 9739369
? rmin=1.;for(i=1,%2,m=i*n;s=sqrt(m);r=s-floor(s+1/2);a=abs(r);if(a<rmin,print(i," ",r);rmin=a))
1 0.38863752194384412241391895034603023048
3 0.13280039356362448650851186545051349869
5 -0.062574729295360553801153810176638603489
25 -0.056812390280779387930405248269848943907
26 0.0023565637575840220411139173411935310521
249 0.00078856879629257341986273435394480017477
1270 -0.00035066896867802103653207407025693647250
2908 -0.00015548403072461033306300724937169442815
5751 0.000049999999998239436619842293195109643133
15967 0.000016060359904103618415886680137373152243
44374 0.000013690295101869124789581112016779627629
52773 -0.0000083691229577759246879089820753401997222
156685 0.0000048570450223756521073572380724696046510
232175 -0.00000011083466482710815117171386169774468900
2555795 -0.000000033405681130480356188059435754343033808
4328608 -0.000000025669015398688340494005072561788537700
9739369 0.E-31

I then looked at the sequence for core(n); that is, the quotient after you divide out the largest square factor. I was surprised at the difference.

? n=%2;

? rmin=1.;for(i=1,%2,m=i*n;s=sqrt(m);r=s-floor(s+1/2);a=abs(r);if(a<rmin,print(i," ",r);rmin=a))
1 -0.20378749268538529252869368321798993120
7 -0.14932919336369084719453544650701262700
8 -0.055341739136064948695070464236473348442
14 -0.049798855867348021619528929869114555650
25 -0.018937463426926462643468416089949631920
26 0.00078552125252800734703797244706451035071
1048 -0.00063843055166137232524643516952498667835
1270 -0.00011688965622600701217735802341872203351
9181 0.00010032538866044674291975357424295326378
17554 -0.000018138768837509299063483996101877671538
42023 -0.000013286481552249112613121304003897685837
44374 0.0000045634317006230415965270373389265425430
52773 -0.0000027897076525919748959696606917800665741
156685 0.0000016190150074585507024524126908232015503
392125 0.0000010234162761051623212733455424902660305
1555754 0.00000012845000661517322133295148130140522847
1856354 0.00000011759103015621805755488582062502514284
2089575 -0.00000011083466482710815117171386169774468900
2806496 -0.000000095636215139405003714094202019198587517
3091673 0.000000091118763467352483949515847583086646399
3509993 0.000000085516805420533396268798368811707172088
9739367 -0.000000051338033432970323926238187049082828700
9739369 0.E-31

mathPuzzles · 2017-09-17, 23:54

Quote:

Originally Posted by Dr Sardonicus

It occurred to me that all your multiples had square roots that were slightly larger than the nearest integer. By demanding square roots that get closer to the nearest integer from either side, you get a different sequence.

Yes, that's a fabs() bug in my brute force search example, so it only recorded the larger values.

Interestingly, a continued fraction approximation reliably alternates too-large and too-small terms. So much elegance in that representation!

Dr Sardonicus · 2017-09-18, 13:28

Quote:

Originally Posted by mathPuzzles

Interestingly, a continued fraction approximation reliably alternates too-large and too-small terms. So much elegance in that representation!

Yes, SCF's do that. Alas, for the purpose at hand, it gives relatively poor results. If

p/q is a convergent to the SCF for sqrt(N),

then we do get a smallish value for abs(q^2 * N - p^2).

(In fact, you eventually reach a point where abs(difference) is 1.) This only gives results for square multipliers, though. There may be some way to use the information gleaned from the convergents for your purpose, but I haven't thought of one yet.

Curiously, it's much easier to see the behavior of the fractional part of sqrt(k*N) for large integer multipliers k. It becomes very regular, starting at 0 when k*N is a perfect square, then incrementing very slowly. Alas, I haven't yet figured out a way to translate this into anything useful for values of k less than N...

2017-09-15, 20:02	#1
mathPuzzles Mar 2017 2·3·5 Posts	Multiplier search to find almost-squares I'm working on a packing puzzle and have hit a subproblem that's fun to think about by itself. Given a very large integer \(n\), I wish to find integer multipliers \(m<n\) such that the product \(nm\) is a better and better approximation to any perfect square. Ideally this should be easy to compute and output a series of improved approximates as the size of \(m\) increases. 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: Code: 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. The brute force enumeration I used for this example does not scale when \(n\) becomes more than 10 digits, and I want to find values for much larger \(n\). I suspect the answer has to do with a continued fraction representation of \(\sqrt n\) which leads to an efficient sequence of better and better rational approximations \(\sqrt n\). But I have had no luck turning that hunch into a working method. ie, for this example \(n=87654321\) there's a continued fraction representation of \(\sqrt n\) of [9362; 2, 1, 1, 2, 1, 11, 1, 1, 3, 1, 15, 2, 1, 3, 22, 21, 1, 5, 1, 11, 40, 86, 1, 1, 1, ...]. Maybe there's a way to turn this approximation sequence into corresponding \(m\) values? Another solution is literally perfect but impractical. It directly computes the smallest \(m\) that produces a perfect square by completely factoring \(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\). There's a slight similarity to this problem with Lehman's extension to the Fermat factoring method. He notes that the Fermat factoring method is accelerated by using a sequential set of multipliers to "sample" all the possible residuals of the Fermat method tests. Those multipliers are formed by a continued fraction expansion. However the similarity to my problem is weak, it still may provide a clue. My latest experiments were using a monte carlo approach. I generate a few thousand distributed values of \(m\) and evaluate those for closeness quality. Then I use Newton's method to refine the best ones found to zoom into a local minimum. This doesn't work very well since the goal function is not smooth. Thanks for any ideas with this fun puzzle!

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Find the Squares	a1call	Puzzles	18	2018-03-02 16:47
Regarding Squares	a1call	Miscellaneous Math	42	2017-02-03 01:29
Where can I find a Reverse and Add program? I can't find any!	Stargate38	Programming	18	2015-07-10 06:08
Benchmarks varying FSB, Memory Latency and multiplier	S485122	Software	0	2006-11-08 20:21
VIA C7 Montgomery Multiplier?	akruppa	Hardware	1	2005-08-04 10:25

2017-09-15, 20:37	#2
science_man_88 "Forget I exist" Jul 2009 Dumbassville 8384₁₀ Posts	well $\sqrt{nm}-\lfloor{nm}\rfloor = \sqrt{n}\sqrt{m}-\lfloor{\sqrt{n}\sqrt{m}}\rfloor$ if you think the square root will help.

2017-09-16, 14:02	#5
Dr Sardonicus Feb 2017 Nowhere 4643₁₀ Posts	It occurred to me that all your multiples had square roots that were slightly larger than the nearest integer. By demanding square roots that get closer to the nearest integer from either side, you get a different sequence. Since the example value was so small, I used core(), which is the (unique) square-free factor with a square cofactor, which is the largest square factor of n. In this case, the largest square factor is 9. ? n = 87654321; ? core(n) %2 = 9739369 ? rmin=1.;for(i=1,%2,m=in;s=sqrt(m);r=s-floor(s+1/2);a=abs(r);if(a<rmin,print(i," ",r);rmin=a)) 1 0.38863752194384412241391895034603023048 3 0.13280039356362448650851186545051349869 5 -0.062574729295360553801153810176638603489 25 -0.056812390280779387930405248269848943907 26 0.0023565637575840220411139173411935310521 249 0.00078856879629257341986273435394480017477 1270 -0.00035066896867802103653207407025693647250 2908 -0.00015548403072461033306300724937169442815 5751 0.000049999999998239436619842293195109643133 15967 0.000016060359904103618415886680137373152243 44374 0.000013690295101869124789581112016779627629 52773 -0.0000083691229577759246879089820753401997222 156685 0.0000048570450223756521073572380724696046510 232175 -0.00000011083466482710815117171386169774468900 2555795 -0.000000033405681130480356188059435754343033808 4328608 -0.000000025669015398688340494005072561788537700 9739369 0.E-31 I then looked at the sequence for core(n); that is, the quotient after you divide out the largest square factor. I was surprised at the difference. ? n=%2; ? rmin=1.;for(i=1,%2,m=in;s=sqrt(m);r=s-floor(s+1/2);a=abs(r);if(a<rmin,print(i," ",r);rmin=a)) 1 -0.20378749268538529252869368321798993120 7 -0.14932919336369084719453544650701262700 8 -0.055341739136064948695070464236473348442 14 -0.049798855867348021619528929869114555650 25 -0.018937463426926462643468416089949631920 26 0.00078552125252800734703797244706451035071 1048 -0.00063843055166137232524643516952498667835 1270 -0.00011688965622600701217735802341872203351 9181 0.00010032538866044674291975357424295326378 17554 -0.000018138768837509299063483996101877671538 42023 -0.000013286481552249112613121304003897685837 44374 0.0000045634317006230415965270373389265425430 52773 -0.0000027897076525919748959696606917800665741 156685 0.0000016190150074585507024524126908232015503 392125 0.0000010234162761051623212733455424902660305 1555754 0.00000012845000661517322133295148130140522847 1856354 0.00000011759103015621805755488582062502514284 2089575 -0.00000011083466482710815117171386169774468900 2806496 -0.000000095636215139405003714094202019198587517 3091673 0.000000091118763467352483949515847583086646399 3509993 0.000000085516805420533396268798368811707172088 9739367 -0.000000051338033432970323926238187049082828700 9739369 0.E-31