Packing squares into a 1 x Zeta[2] rectangle
The Last Danish Pastry
pi^2/6, the question arises as to whether squares with sides 1, 1/2, 1/3,
etc can be packed into a rectangle of size 1 by pi^2/6.
A picture of such a packing appears at
http://www.pisquaredoversix.force9.co.uk/Tiling.htm
I know of no proof that such a packing is possible or impossible.
A program which I wrote has recently packed the first one million such
squares into such a rectangle. I wrote the program in Mathematica and it
uses exact arithmetic throughout. The algorithm is simple:
The program maintains a list of rectangles. Each member of this list is
itself a list containing exactly two members: the short side of a rectangle
followed by the long side of the rectangle. The program does not store the
position or orientation of any rectangle. The list is stored in ascending
short side order. Initially the list contains one entry: {1, pi^2/6}.
The program inserts the squares in decreasing size order, starting with the
1x1 square. At each stage, to insert the square with side 1/n, the program
finds the rectangle with the shortest short side which will accommodate the
square. [In the case that there are two or more such rectangles with equal
short sides, the program will pick the youngest one.]
Suppose that this rectangle is a x b, where 1/n<=a<=b. The program deletes
this rectangle from the list and inserts two new rectangles (b-1/n) x a and
(a-1/n) x 1/n into the list.
- If any side of one of these new rectangles is zero, the rectangle is not
inserted.
- Each new rectangle is stored in {short side, long side} form.
Thus, the list of rectangles grows by one per inserted square, except in the
rare cases in which a rectangle of exactly the right width is found.
A trivial optimisation, which took me a long time to notice, is that if the
number of squares to be inserted is decided at the beginning, as N, say,
then any rectangles narrower than 1/N can be discarded as soon as they
appear. This has a dramatic effect on the memory requirements and running
time of the program. In the case of N=10^6 the maximum length of the
rectangle list is only 7,493 which occurs just after inserting the square
with side 1/55,205. Thereafter the length of the list slowly decreases.
After inserting the last square, with side 10^-6, there are just 7
rectangles in the list. Their dimensions are, roughly:
0.000001000264 x 0.000371508565 [1,000,000]
0.000001000289 x 0.000006561855 [ 999,736]
0.000001000332 x 0.000011950546 [ 999,710]
0.000001000424 x 0.000099911008 [ 999,668]
0.000001001705 x 0.000013366392 [ 999,575]
0.000001001771 x 0.000555285230 [ 998,297]
0.000621399972 x 0.000621402936 [ 998,232]
The number in square brackets is the square insertion step on which the
rectangle was created.
Note that each rectangle, except the last, has a short side just exceeding
10^-6. The last one is huge in comparison to the others. Also, it is almost
square, having an aspect ratio of about 1.00000477 .
The exact size of that last rectangle may be expressed as:
(pi^2/6 - ShortNumerator/ShortDenominator)
by
(LongNumerator/LongDenominator)
Where
ShortNumerator =
88148577597184641314023698687804198322622003067950
90277185502203375757868045576236778623499141581835
91095283100445795053089253938670874859361703421694
93589311823604254188777249571387340885945805010588
59158565482204748239750452173829861295626045336259
37611823762149119593932203343599960000593198902456
62151237628335467123582313067030461952701063806541
09667253352708582423851542412389977650553557102776
48867766805593783542952432276691372915179943637567
30921614687225494242879103415386639772227105415075
60643644416702161056703911777435451470868967261015
03285333687384626370723064421360623232628962182637
33785897530162588640506103091960735379749803817168
27337105343328553249474140253583305664128829433056
13496001065570446619534699711595669897241621797339
93388113729020710706312912651983440135427698863738
63455691221381048718834049233446561869585869886892
11066449759482338440176987851999633382542943944743
83052271691048660471857179765488027759900589960305
37378583137068870187987573969424873832345344118539
33368635075465276924658419905001027235726511505469
90353609271920928926254763071708700239940565565014
69168650106503612867362486635886531701170797485510
99375741498187773039269448405524049571692907463933
52292512770766034352574830725344567781634199947344
39128864912738319438009565992988317045941602472518
84296172734535520954249457165155850357846464984168
55299222999724423825677947429849212042460805178788
23214473791347512926915739195451188103089711423995
69891250713418835019305494967439261535807066257765
86799633983386818438909781178910531233498247023179
22489232680161587870238609995903489290522620579734
27913072409961919211050524749783993630732833119534
51221464170732847284504244076797981093088600479209
053071348915420741889
ShortDenominator =
53608160645434703140761211994317971700783074368336
23325975705041657962199994733358382994458318582660
77598233503372093023408990096331259105144227503324
99931830157705570560424971647310855286927378535483
51519419895212616165032657829920140448566211296935
08925318960134998789890442610040864611429495599467
55671385275409484022080990210675967224987014208598
03335236373663242927780013944648864149878730486125
39041613975393755631755935261748017063478349180906
68435262002209072815068783227098957825899390123056
87116154057047656878878907753207321889684985791605
16008019019744195226005265347943729214648741668979
90732236259531674523664568538104488968273268732774
74645971065348455713992347183400863276778739619943
89625588842652615699820699583835957017913827580111
39619239553717364061586421301662144411944880262864
13395969932087668263688142360819354641427777701996
11575083489100468980371536759296335301136691198138
39559100156995546068054947710363960181181289364408
47219039882502818687162480694856587042340603392188
93192097190331493671006154660882637398429894947140
66724834302759980279336075917538263518035481261929
09959571761983813160895335069812335369906345916646
57307263315174319702690110108769119880417800559541
00846379467033278426493445187132240090150811316237
11870955392306082427560405688265993364931620972062
42335013731582665984021398103261291575096750373611
78793366106368150944101270721191063173365978409196
32419016511795819355629216137822167151147383280072
17692953976640188298210375720290857531988737370969
01207985676688854219832216404101906724620701738590
65777947161752685898547108814129100143613045915161
23374032620084188029394058765229087587568694264890
44233796349785411756140522085279648064146173069741
478636801148014080000
LongNumerator =
86047691660315035868968439680618750650385496662337
69341618423224868557176707904056350747739644607152
19341301092244142985694427567208621603825424715808
50112490209730250303812592410205852634552809617406
54471220118615832220663814127702644186714156802514
89272173167125109946591599082250813475432136844437
68434150604827750301142594110541508119955806775639
48463821703879298880841441517861092382325647927555
17115984413353561811152746794319549286695056542231
75370181749913246697604501180515750468588947850814
96706860842334628047016110265861987131951269186913
55908484624794372227266755207694315503681976948427
59732973255837108405693520922709400140190847636749
60091554508265275883766083172672994896381234279724
35485615485280999872894822261731570552709443192476
07685741096374165452217373319152585412622236248087
75856424918727148070254116048744362672852782317829
99207549345144244124571110563211160343448412194752
79110755652853486307738886342254777707077572587992
29405091182393418319601369763056120887765700618802
27139753549245993550447831136020976532760818138519
98216552674127086312240961717818956038535226187300
43026597993187644795910836481706823332909020130603
09729716420449811214331443400182398534278484763571
27904525989212662382850630094162630962359551947273
97311922973034069310043168935737831265241199089047
46559558404697050977201086017144902884602248144108
71005578441670661613107026657746377160408235952122
70087369832576028781964223879066392055590320740847
64872057694761838719127407266757016871496087930551
58594303661605591550655979493954945142285417155556
97061447617516531128930865552526142619566789459050
16802730874016347300046435875463493515247956092289
80788952041557673741641666771939979618817508420910
11050430185421809507580791626321726210797393934779
33362836600904869583181
LongDenominator =
13847326202197605511604348541676281864027795818043
31494335574789145450920249049910013265993162156505
60831474662540178414423726822350848233301461067293
21368995360010230519749558542277057071473577106811
23548536664652068929533780687547853336157369555086
86435599910456774645119837370840414802536199558214
07527909448749766750406409444125057733978666254122
19353807926168688488715863115960118447262678159252
66974533884810419996115934738184899912380787401311
77856867483197701324817440576351765023155329523060
68640715686158929369832278778842403496825357945180
51999476544062632945516973292520225337991834072383
82846228280041100692245330583478338241014202245803
30323143236417275386997321382053499979484896390576
45426647084624716067636294896758072966317096343334
28169063530634898773783098553798071542939121086910
08006721058240228461124891602875033925435245224172
90909661066024272174911721070106393261965722571136
18608587173321485889447514408382277645342459166650
66976600733716756193252940889415454560334136529577
70915746535414564177067690689656587269581203051464
54295311030944948219808305598301111195229732416082
42817235468158091436079088616794858652804473035517
82817817155337872004025893330437425894039012377193
76447539452009335637045807403996380650616246802471
05691575600545667349590304669247493320414626833379
52612693846867728391114410877249463229225980473996
60123182871902607011087292407939606651288648107916
20645836880002779839862309998364888537462475216562
83515669632032306317521726424095159019732485843596
26389117354057755490411586373128011034072899097872
57238596906896860163242623358201011919041838989031
36072177994374094882330699298066695784371692394667
11940033790850742395135563324255474227834715815498
61014376098413906103604397447388393432391565219123
065068758213935671227536000
--
Clive Tooth
http://www.clivetooth.dk
Phil Carmody
> Since the sum of the reciprocals of the squares of the positive integers is
> pi^2/6, the question arises as to whether squares with sides 1, 1/2, 1/3,
> etc can be packed into a rectangle of size 1 by pi^2/6.
>
> A picture of such a packing appears at
> http://www.pisquaredoversix.force9.co.uk/Tiling.htm
Nice!
> I know of no proof that such a packing is possible or impossible.
>
> A program which I wrote has recently packed the first one million such
> squares into such a rectangle. I wrote the program in Mathematica and it
> uses exact arithmetic throughout. The algorithm is simple:
>
> The program maintains a list of rectangles. Each member of this list is
> itself a list containing exactly two members: the short side of a rectangle
> followed by the long side of the rectangle. The program does not store the
> position or orientation of any rectangle. The list is stored in ascending
> short side order. Initially the list contains one entry: {1, pi^2/6}.
>
> The program inserts the squares in decreasing size order, starting with the
> 1x1 square. At each stage, to insert the square with side 1/n, the program
> finds the rectangle with the shortest short side which will accommodate the
> square. [In the case that there are two or more such rectangles with equal
> short sides, the program will pick the youngest one.]
>
> Suppose that this rectangle is a x b, where 1/n<=a<=b. The program deletes
> this rectangle from the list and inserts two new rectangles (b-1/n) x a and
> (a-1/n) x 1/n into the list.
Is there any special handling of the rational vs. transcendental edges?
I'd have thought that performance-wise, trying to fit things in rational-
edged rectanges would be quicker, as you don't have to hit arbitrary
precision decimals, only integers which have no precision issues.
What kind of time are we talking about for the program --
minutes, hours or days?
Fascinating. How many exact fits did you manage during the run?
Your best-fit technique invites incredibly small slivers, and thus
discardings. Did you think about other less greedy allocation
strategies?
Phil
--
1st bug in MS win2k source code found after 20 minutes: scanline.cpp
2nd and 3rd bug found after 10 more minutes: gethost.c
Both non-exploitable. (The 2nd/3rd ones might be, depending on the CRTL)
Phil Carmody
> "The Last Danish Pastry" <TheLastDa...@yahoo.com> writes:
>
> > Since the sum of the reciprocals of the squares of the positive integers is
> > pi^2/6, the question arises as to whether squares with sides 1, 1/2, 1/3,
> > etc can be packed into a rectangle of size 1 by pi^2/6.
> >
> > A picture of such a packing appears at
> > http://www.pisquaredoversix.force9.co.uk/Tiling.htm
>
> Nice!
Why are 8 and 10 where they are?
I'd have thought that 8 would slot ringht next to 7 rather than 6?
Similarly, the 10 should fit next to 9?
The Last Danish Pastry
news:871xnvw...@nonospaz.fatphil.org...
No. Mathematica handles all that. I simply tell it that the sides of the
first rectangle are 1 and Zeta[2] and it knows that Zeta[2] is pi^2/6.
> I'd have thought that performance-wise, trying to fit things in rational-
> edged rectanges would be quicker, as you don't have to hit arbitrary
> precision decimals, only integers which have no precision issues.
>
> What kind of time are we talking about for the program --
> minutes, hours or days?
About 11 hours for the N=1,000,000 run.
I am not sure. But here is a list of all the exact fits [side of
square=short side of a rectangle] for n<10000, together with the
factorisation of n:
1/1, exact, factor[1]={}
1/6, exact, factor[6]={{2,1},{3,1}}
1/20, exact, factor[20]={{2,2},{5,1}}
1/36, exact, factor[36]={{2,2},{3,2}}
1/180, exact, factor[180]={{2,2},{3,2},{5,1}}
1/182, exact, factor[182]={{2,1},{7,1},{13,1}}
1/220, exact, factor[220]={{2,2},{5,1},{11,1}}
1/420, exact, factor[420]={{2,2},{3,1},{5,1},{7,1}}
1/468, exact, factor[468]={{2,2},{3,2},{13,1}}
1/560, exact, factor[560]={{2,4},{5,1},{7,1}}
1/588, exact, factor[588]={{2,2},{3,1},{7,2}}
1/1056, exact, factor[1056]={{2,5},{3,1},{11,1}}
1/1170, exact, factor[1170]={{2,1},{3,2},{5,1},{13,1}}
1/1190, exact, factor[1190]={{2,1},{5,1},{7,1},{17,1}}
1/1302, exact, factor[1302]={{2,1},{3,1},{7,1},{31,1}}
1/1320, exact, factor[1320]={{2,3},{3,1},{5,1},{11,1}}
1/1380, exact, factor[1380]={{2,2},{3,1},{5,1},{23,1}}
1/1476, exact, factor[1476]={{2,2},{3,2},{41,1}}
1/1640, exact, factor[1640]={{2,3},{5,1},{41,1}}
1/1664, exact, factor[1664]={{2,7},{13,1}}
1/1806, exact, factor[1806]={{2,1},{3,1},{7,1},{43,1}}
1/1989, exact, factor[1989]={{3,2},{13,1},{17,1}}
1/2100, exact, factor[2100]={{2,2},{3,1},{5,2},{7,1}}
1/2106, exact, factor[2106]={{2,1},{3,4},{13,1}}
1/2160, exact, factor[2160]={{2,4},{3,3},{5,1}}
1/2184, exact, factor[2184]={{2,3},{3,1},{7,1},{13,1}}
1/2340, exact, factor[2340]={{2,2},{3,2},{5,1},{13,1}}
1/2548, exact, factor[2548]={{2,2},{7,2},{13,1}}
1/2600, exact, factor[2600]={{2,3},{5,2},{13,1}}
1/2640, exact, factor[2640]={{2,4},{3,1},{5,1},{11,1}}
1/2730, exact, factor[2730]={{2,1},{3,1},{5,1},{7,1},{13,1}}
1/2860, exact, factor[2860]={{2,2},{5,1},{11,1},{13,1}}
1/3120, exact, factor[3120]={{2,4},{3,1},{5,1},{13,1}}
1/3220, exact, factor[3220]={{2,2},{5,1},{7,1},{23,1}}
1/3245, exact, factor[3245]={{5,1},{11,1},{59,1}}
1/3480, exact, factor[3480]={{2,3},{3,1},{5,1},{29,1}}
1/3612, exact, factor[3612]={{2,2},{3,1},{7,1},{43,1}}
1/3843, exact, factor[3843]={{3,2},{7,1},{61,1}}
1/4060, exact, factor[4060]={{2,2},{5,1},{7,1},{29,1}}
1/4224, exact, factor[4224]={{2,7},{3,1},{11,1}}
1/4340, exact, factor[4340]={{2,2},{5,1},{7,1},{31,1}}
1/4620, exact, factor[4620]={{2,2},{3,1},{5,1},{7,1},{11,1}}
1/4914, exact, factor[4914]={{2,1},{3,3},{7,1},{13,1}}
1/5040, exact, factor[5040]={{2,4},{3,2},{5,1},{7,1}}
1/5060, exact, factor[5060]={{2,2},{5,1},{11,1},{23,1}}
1/5100, exact, factor[5100]={{2,2},{3,1},{5,2},{17,1}}
1/5475, exact, factor[5475]={{3,1},{5,2},{73,1}}
1/5544, exact, factor[5544]={{2,3},{3,2},{7,1},{11,1}}
1/6162, exact, factor[6162]={{2,1},{3,1},{13,1},{79,1}}
1/6300, exact, factor[6300]={{2,2},{3,2},{5,2},{7,1}}
1/6844, exact, factor[6844]={{2,2},{29,1},{59,1}}
1/6970, exact, factor[6970]={{2,1},{5,1},{17,1},{41,1}}
1/7140, exact, factor[7140]={{2,2},{3,1},{5,1},{7,1},{17,1}}
1/7564, exact, factor[7564]={{2,2},{31,1},{61,1}}
1/8320, exact, factor[8320]={{2,7},{5,1},{13,1}}
1/8424, exact, factor[8424]={{2,3},{3,4},{13,1}}
1/8463, exact, factor[8463]={{3,1},{7,1},{13,1},{31,1}}
1/9030, exact, factor[9030]={{2,1},{3,1},{5,1},{7,1},{43,1}}
1/9940, exact, factor[9940]={{2,2},{5,1},{7,1},{71,1}}
> Your best-fit technique invites incredibly small slivers, and thus
> discardings. Did you think about other less greedy allocation
> strategies?
I have not experimented much in that direction. Choosing the _longest_ short
side every time causes the program to fail to find a fit on inserting 1/95.
Leroy Quet
> Since the sum of the reciprocals of the squares of the positive integers is
> pi^2/6, the question arises as to whether squares with sides 1, 1/2, 1/3,
> etc can be packed into a rectangle of size 1 by pi^2/6.
>
> A picture of such a packing appears at
> http://www.pisquaredoversix.force9.co.uk/Tiling.htm
>
> I know of no proof that such a packing is possible or impossible.
>
> A program which I wrote has recently packed the first one million such
> squares into such a rectangle. I wrote the program in Mathematica and it
> uses exact arithmetic throughout. The algorithm is simple:
>
I wonder if such a packing has been shown to exist for a slightly
relaxed problem, such as for a rectangle of 1 by (pi^2/6 + epsilon).
As for the picture, it reminds me visually (if not mathematically) of
the graphical representation of the continued fraction of pi^2/6,
where each term is a real itself represented by a continued fraction
of real-terms, ad infinitum.
Does anyone know about the more general problem of packing n-cubes of
side-lengths 1, 1/2, 1/3,... into an n-box of n-volume zeta(n)?
thanks,
Leroy Quet
The Last Danish Pastry
> Phil Carmody <thefatphi...@yahoo.co.uk> writes:
>
> > "The Last Danish Pastry" <TheLastDa...@yahoo.com> writes:
> >
> > > Since the sum of the reciprocals of the squares of the positive
integers is
> > > pi^2/6, the question arises as to whether squares with sides 1, 1/2,
1/3,
> > > etc can be packed into a rectangle of size 1 by pi^2/6.
> > >
> > > A picture of such a packing appears at
> > > http://www.pisquaredoversix.force9.co.uk/Tiling.htm
> >
> > Nice!
>
> Why are 8 and 10 where they are?
> I'd have thought that 8 would slot ringht next to 7 rather than 6?
> Similarly, the 10 should fit next to 9?
You are quite right. The picture at the above link is one I made about 5
years ago using an algorithm that I no longer remember. I have not made any
pictures yet of tilings produced by the current algorithm.
Timothy Murphy
> Since the sum of the reciprocals of the squares of the positive integers
> is pi^2/6, the question arises as to whether squares with sides 1, 1/2,
> 1/3, etc can be packed into a rectangle of size 1 by pi^2/6.
...
> A program which I wrote has recently packed the first one million such
> squares into such a rectangle. I wrote the program in Mathematica and it
> uses exact arithmetic throughout. The algorithm is simple:
I found your article very interesting.
But as a matter of interest,
how did you deal with pi^2 using exact arithmetic?
--
Timothy Murphy
e-mail (<80k only): tim /at/ birdsnest.maths.tcd.ie
tel: +353-86-2336090, +353-1-2842366
s-mail: School of Mathematics, Trinity College, Dublin 2, Ireland
The Last Danish Pastry
news:yCf5c.986$qP2....@news.indigo.ie...
> The Last Danish Pastry wrote:
>
> > Since the sum of the reciprocals of the squares of the positive integers
> > is pi^2/6, the question arises as to whether squares with sides 1, 1/2,
> > 1/3, etc can be packed into a rectangle of size 1 by pi^2/6.
> ...
> > A program which I wrote has recently packed the first one million such
> > squares into such a rectangle. I wrote the program in Mathematica and it
> > uses exact arithmetic throughout. The algorithm is simple:
>
> I found your article very interesting.
> But as a matter of interest,
> how did you deal with pi^2 using exact arithmetic?
Mathematica does it all for me. Mathematica can do comparisons between, for
example, rational numbers and transcendentals. Here is a short Mathematica
session in which it compares a rational, num/denom, with pi+e and prints the
result "Greater", it then compares the rational (num-1)/denom with pi+e and
prints the result "Not greater":
In[1]:= $MaxExtraPrecision = 100
Out[1]= 100
In[2]:= num = 6083355812763767537862691282377375125710417240146
Out[2]= 6083355812763767537862691282377375125710417240146
In[3]:= denom = 1038137562741240040724843633763265660486107102341
Out[3]= 1038137562741240040724843633763265660486107102341
In[4]:= If[num/denom > Pi + E, Print["Greater"], Print["Not greater"]]
From In[4]:= "Greater"
In[5]:= If[(num - 1)/denom > Pi + E, Print["Greater"], Print["Not
greater"]]
From In[5]:= "Not greater"
Jan Kristian Haugland
> Does anyone know about the more general problem of packing n-cubes of
> side-lengths 1, 1/2, 1/3,... into an n-box of n-volume zeta(n)?
You can't fit a cube of side length 1 and a cube of side
length 1/2 inside a right-angled box of volume less than 3/2.
--
J K Haugland
http://www.neutreeko.com
David W. Cantrell
> qqq...@mindspring.com (Leroy Quet) wrote in message
> news:<b4be2fdf.0403...@posting.google.com>...
>
> > Does anyone know about the more general problem of packing n-cubes of
> > side-lengths 1, 1/2, 1/3,... into an n-box of n-volume zeta(n)?
>
> You can't fit a cube of side length 1 and a cube of side
> length 1/2 inside a right-angled box of volume less than 3/2.
Exactly, noting that zeta(n) < 3/2 for n > 2.
However, interesting questions might still be obtained for dimensions
n > 2 by omitting the first few largest cubes. As an example, let's
consider n = 3:
Omitting just the cube of edge length 1 can't work [because zeta(3) - 1 is
still smaller than (1/2)^2*(1/2 + 1/3) ]. But omitting the cubes of edge
lengths 1 and 1/2 might give an interesting packing problem [because
zeta(3) - 9/8 is now larger than (1/3)^2*(1/3 + 1/4) ]. So I would guess
that cubes of edge lengths 1/3, 1/4, 1/5, ... might be packed into a box of
edge lengths 1/3, 1/3, zeta(3) - 9/8. Furthermore, if such a packing is
possible, I would suppose that a very simple algorithm could be used to
describe how such a packing could be achieved.
David Cantrell
Timothy Murphy
I'm not entirely clear what this is doing.
But I wrote a little Java program to pack squares as you did,
using exact arithmetic (the BigInteger class).
It was actually impossible to get much past 10000
as the numerators and denominators get too big.
So I wonder if Mathematica actually works with floating-point numbers
to a certain (high) precision?
One interesting point is that several other rectangles I tried
with the same area pi^2/6 could not be packed with these squares,
eg pi/2 x pi/3 and pi/sqrt(6) x pi/sqrt(6).
In fact 1 x pi^2/6 is the only "packable" rectangle of this area
that I have found, though I didn't made a serious study.
Incidentally I took pi=355/113, which I think is just good enough
for the range I was considering.
I always took the square 1/n x 1/n from the smallest "vacant" rectangle.
I don't know if another choice would be as good, or even better.
The average rectangle had been divided about 50--100 times
with 10000 squares, which I found surprising
as the number of remaining rectangles was (of course) a little under 10000.
Leroy Quet
> qqq...@mindspring.com (Leroy Quet) wrote in message news:<b4be2fdf.0403...@posting.google.com>...
>
> > Does anyone know about the more general problem of packing n-cubes of
> > side-lengths 1, 1/2, 1/3,... into an n-box of n-volume zeta(n)?
>
> You can't fit a cube of side length 1 and a cube of side
> length 1/2 inside a right-angled box of volume less than 3/2.
DOH!
I like David W Cantrell's suggestion in the other reply to Jan
Kristian Haugland's post.
thanks,
Leroy Quet
The Last Danish Pastry
It will hold a rational quantity as an exact fraction (reduced to its lowest
terms). It will hold a value such as "840/1010+pi" as "the rational number
84/101 plus the known constant pi". If it needs to compare that value with,
say, "10429/8310+e" it will subtract one from the other to give
"-355289/839310-e+pi" and then compute that quantity with sufficient
precision to determine if it is positive or negative.
> One interesting point is that several other rectangles I tried
> with the same area pi^2/6 could not be packed with these squares,
> eg pi/2 x pi/3 and pi/sqrt(6) x pi/sqrt(6).
> In fact 1 x pi^2/6 is the only "packable" rectangle of this area
> that I have found, though I didn't made a serious study.
>
> Incidentally I took pi=355/113, which I think is just good enough
> for the range I was considering.
It is difficult to say what approximation to pi is good enough for packing a
given set of squares. Since 355/133 is a little greater than pi it is
possible that a square might just get squeezed in somewhere when it really
should not have fitted.
Taking one more term in the continued fraction for pi gives the rational
approximation 103993/33102 which is about 6*10^-10 less than pi. Using my
Mathematica program I can pack 100,000 squares into a 1 by
(103993/33102)^2/6 rectangle in about 3 minutes. [As opposed to about 12
minutes when using the exact value for pi.]
> I always took the square 1/n x 1/n from the smallest "vacant" rectangle.
> I don't know if another choice would be as good, or even better.
> The average rectangle had been divided about 50--100 times
> with 10000 squares, which I found surprising
> as the number of remaining rectangles was (of course) a little under
10000.
--
Clive Tooth
http://www.clivetooth.dk
The Last Danish Pastry
> Using my
> Mathematica program I can pack 100,000 squares into a 1 by
> (103993/33102)^2/6 rectangle in about 3 minutes. [As opposed to about 12
> minutes when using the exact value for pi.]
... and I can pack 1,000,000 squares into a 1 by (103993/33102)^2/6
rectangle in about 3.5 hours. [As opposed to about 11 hours when using the
exact value for pi.]
--
Clive Tooth
http://www.clivetooth.dk
Gottfried Helms
> Since the sum of the reciprocals of the squares of the positive integers is
> pi^2/6, the question arises as to whether squares with sides 1, 1/2, 1/3,
> etc can be packed into a rectangle of size 1 by pi^2/6.
>
> A picture of such a packing appears at
> http://www.pisquaredoversix.force9.co.uk/Tiling.htm
>
> I know of no proof that such a packing is possible or impossible.
>
Nice, indeed.
Is it true, that the squares with contents 1,6,24,... (factorials)
are placed sequentially from the left at the bottom?
Gottfried Helms
Michele Dondi
<TheLastDa...@yahoo.com> wrote:
[exaple explaining how "exact calculations" are carried on]
>It will hold a rational quantity as an exact fraction (reduced to its lowest
>terms). It will hold a value such as "840/1010+pi" as "the rational number
>84/101 plus the known constant pi". If it needs to compare that value with,
>say, "10429/8310+e" it will subtract one from the other to give
>"-355289/839310-e+pi" and then compute that quantity with sufficient
>precision to determine if it is positive or negative.
[snip]
>> Incidentally I took pi=355/113, which I think is just good enough
>> for the range I was considering.
>
>It is difficult to say what approximation to pi is good enough for packing a
>given set of squares. Since 355/133 is a little greater than pi it is
>possible that a square might just get squeezed in somewhere when it really
>should not have fitted.
>
>Taking one more term in the continued fraction for pi gives the rational
>approximation 103993/33102 which is about 6*10^-10 less than pi. Using my
>Mathematica program I can pack 100,000 squares into a 1 by
>(103993/33102)^2/6 rectangle in about 3 minutes. [As opposed to about 12
>minutes when using the exact value for pi.]
Not to contradict your claim, by any means, since it sounds percfectly
reasonable... but couldn't the differences in computation times as
reported both here and in the "next" post be due to the differences in
how each single calculation is done? (Taking into account that in the
approximed situation one has to deal with rational numbers only)
Michele
--
> Comments should say _why_ something is being done.
Oh? My comments always say what _really_ should have happened. :)
- Tore Aursand on comp.lang.perl.misc
Timothy Murphy
> A program which I wrote has recently packed the first one million such
> squares into such a rectangle. I wrote the program in Mathematica and it
> uses exact arithmetic throughout. The algorithm is simple:
>
> The program maintains a list of rectangles. Each member of this list is
> itself a list containing exactly two members: the short side of a
> rectangle followed by the long side of the rectangle. The program does not
> store the position or orientation of any rectangle. The list is stored in
> ascending short side order. Initially the list contains one entry: {1,
> pi^2/6}.
>
> The program inserts the squares in decreasing size order, starting with
> the 1x1 square. At each stage, to insert the square with side 1/n, the
> program finds the rectangle with the shortest short side which will
> accommodate the square. [In the case that there are two or more such
> rectangles with equal short sides, the program will pick the youngest
> one.]
I'm afraid my Java program which I think follows your algorithm exactly
is failing at n = 13045, when I take pi=355/113.
(When I take the next convergent to pi it fails a little earlier.)
Just to be sure it is the same algorithm, when I reach the square 1/n x 1/n
I split the smallest available rectangle w x h, say, where w <= h,
into (w - 1/n) x 1/n and w x (h - 1/n).
I work with absolute precision numbers,
but the following table uses floats for clarity.
I give the beginning and end of my list of rectangles
at the moment of failure.
I discard rectangles with h < 0.999/maxSquare
where maxSquare = 20000 in this case.
======================================================================
square list length max split(average split) vacant space
1024 384 81(26) 9.4584335E-4
2048 445 81(31) 4.5075334E-4
3072 597 178(52) 2.643397E-4
4096 589 178(54) 1.8133453E-4
5120 559 178(57) 1.3159524E-4
6144 548 178(59) 9.8638506E-5
7168 511 178(61) 7.501608E-5
8192 486 180(64) 5.707449E-5
9216 369 180(61) 4.3071297E-5
10240 304 180(59) 3.1902335E-5
11264 234 180(56) 2.2748189E-5
12288 202 180(62) 1.5224153E-5
No room for square of side 1/13045 = 7.665772E-5
(7.6643475E-5,9.582216E-5) 0 151
(7.6573655E-5,1.3778909E-4) 1 177
(7.634314E-5,0.004405286) 2 13
...
(6.2616855E-5,7.942812E-4) 163 59
(6.248239E-5,4.0048058E-4) 164 61
13045 165 180(61) 8.838793E-6
========================================================================
I'll try splitting the rectangle the other way,
but I think you suggested the split I have used?
The Last Danish Pastry
Yes, that is the split I use. I trust that you determine the short side for
each rectangle.
I tried packing exactly 13045 squares, and using pi=355/113 .
I just had two rectangles left at the end:
1/12866
by
16232591006362229703724146227780269001333002563197
28034323386882235665492600992941053807869830766216
87119812194456193154205377450412769314324584702767
16827037641832636172033472533619158562399601877386
55444762636478232474339202527103963792426364335718
77/
78189291000354038269556447202164782976904023500483
10092564063058442445805467854340876556927918088531
09578213052782793267107787429552683744667564000535
17951531205361336704025421882989249312887295412772
11679894276021843794076002197567844076594638744552
48000
and
28443502916123601842684397124442400211002384050116
12542673830292398054440847082650327921218138593635
14137741/
60488150462501955023573115046382201603516945063189
74787374711058123255712428026828489819582859887494
3976755840
by
37884221669787720459381958869300116365928198500041
78151170591800710240083446185826548393407239998828
753258261/
80559998239970211262949437076425874136128912911709
67182790408758109035719138842349025428291088889252
43346257200
or about:
0.0000777242344162909995 by 0.0002076063204907271652
and
0.0047023264389206951654 by 0.0047026095453650706211
[having discarded all rectangles with a short side less than 1/13045]
The Last Danish Pastry
news:c3akva$26lk9r$1...@ID-11651.news.uni-berlin.de...
a few questions...
> > I work with absolute precision numbers,
I assume that means you keep the sides as full precision rationals. Do you
keep them in their lowest terms?
> > I discard rectangles with h < 0.999/maxSquare
Why not "with h < 1/maxSquare"?
> > where maxSquare = 20000 in this case.
> > ======================================================================
> > square list length max split(average split) vacant space
> > 1024 384 81(26) 9.4584335E-4
> > 2048 445 81(31) 4.5075334E-4
> > 3072 597 178(52) 2.643397E-4
> > 4096 589 178(54) 1.8133453E-4
> > 5120 559 178(57) 1.3159524E-4
> > 6144 548 178(59) 9.8638506E-5
> > 7168 511 178(61) 7.501608E-5
> > 8192 486 180(64) 5.707449E-5
> > 9216 369 180(61) 4.3071297E-5
> > 10240 304 180(59) 3.1902335E-5
> > 11264 234 180(56) 2.2748189E-5
> > 12288 202 180(62) 1.5224153E-5
I assume that you do not keep the vacant space to full precision.
Timothy Murphy
> a few questions...
>
>> > I work with absolute precision numbers,
>
> I assume that means you keep the sides as full precision rationals. Do you
> keep them in their lowest terms?
Yes, I store each rectangle as three BigIntegers w,h,n,
where the sides are w/n and h/n ,
and check whenever a rectangle is created that gcd(w,h,n) = 1.
(I don't check eg that gcd(w,n) = 1,
but I don't see that that should matter.)
I also check the orientation of each rectangle as it is created.
>> > I discard rectangles with h < 0.999/maxSquare
>
> Why not "with h < 1/maxSquare"?
I actually keep floats x = w/n and y = h/n with each rectangle,
and use them for comparison for keeping the rectangles in order.
(I did this because I thought this might be the cause of the slowness
of my program, but I found the actual reason was that I made an error
in discarding rectangles with w < 1/n^2 rather than w < 1/n .
When I corrected this the program ran quite fast,
and could easily have reached 10^6, if it hadn't bombed out!)
> I assume that you do not keep the vacant space to full precision.
No, I just keep the area of each rectangle as a float, for interest..
Here's the main routine of my program, to see my approach.
I don't set myself up as a great programmer,
and it is all too likely that I've made a mistake.
=======================================================
public void removeSquare(int i) {
int index = findIndex(1.0/(double)i) - 1;
if (index < 0) {
System.err.println("No room for square side 1/" + i);
System.out.println("No room for square of side 1/" + i
+ " = " +1/(float)i);
printList(true);
System.exit(1);
}
Rectangle r = (Rectangle)rectangles.get(index);
// System.out.println("Removing " + r);
rectangles.remove(index);
currentIndex = index;
BigInteger m = BigInteger.valueOf((long)i);
BigInteger w = r.w.multiply(m);
BigInteger h = r.h.multiply(m);
BigInteger n = r.n.multiply(m);
// First we construct the rectangle s = r.x x (r.y - 1/i)
// ie [w,h,n] = [r.w*i,r.h*i-r.n,r.n*i]
Rectangle s = new Rectangle(w,h.subtract(r.n),n);
s.count = r.count + 1;
// System.out.println("New " + s);
s.check();
// Next we construct the rectangle t = (r.x - 1/i) x 1/i
// ie [w,h,n] = [r.w*i-r.n,r.n,r.n*i]
Rectangle t = new Rectangle(w.subtract(r.n),r.n,n);
t.count = r.count + 1;
// System.out.println("New " + t);
t.check();
// checkOrder();
// We determine which of the new rectangles is larger
if (s.x >= t.x) {
addRectangle(s);
addRectangle(t);
} else {
addRectangle(t);
addRectangle(s);
}
}
=======================================================
I think you mentioned that you had 2 rectangles in your list
when n = 13045 if you discarded rectangles with w < 1/13045.
Of course I would have 0 rectangles if I did that,
since none of the rectangles in my list was large enough
to contain a square of side 1/13045 .
The Last Danish Pastry
news:r3oe5090821v26f4c...@4ax.com...
Certainly. I expect it is faster for Mathematica to compare two rationals
than a rational and an irrational.
The Last Danish Pastry
news:c395du$892$05$1...@news.t-online.com...
That packing was done by a program that I wrote back in 1999:
http://tinylink.com/?0g6QpfQTMZ
It does not use the same method as I am now using. I dug out the old program
but it now does not produce the picture at
http://www.pisquaredoversix.force9.co.uk/Tiling.htm
the 24 and 25 are interchanged, and possibly other changes.
So, I am afraid I cannot answer your question at the moment.
~~~~
See the thread at
http://tinylink.com/?N4zBhRwvDE
for two interesting posts by David W. Cantrell.
The Last Danish Pastry
I cannot see anything wrong with the code that you have posted, but I am
making assumptions about "findIndex", "check", "new Rectangle",
"addRectangle", "remove" etc.
I am particularly curious about why it matters in which order the two calls
of addRectangle are made, since you are keeping the rectangles in order.
Finding the best fit by comparing floating point numbers is not guaranteed
to find the theoretical best fit. In particular, it may cause you to miss
some exact fits which might be vital to the packing process.
It would probably be helpful if you would post the entire source code.
Timothy Murphy
>> // We determine which of the new rectangles is larger
>> if (s.x >= t.x) {
>> addRectangle(s);
>> addRectangle(t);
>> } else {
>> addRectangle(t);
>> addRectangle(s);
>> }
> I am particularly curious about why it matters in which order the two
> calls of addRectangle are made, since you are keeping the rectangles in
> order.
It is unimportant.
It was meant to speed up the search for the correct position
to insert the new rectangle.
But now I come to think of it, it doesn't even do that.
I keep a record of the last position from which a rectangle was removed
(currentIndex) and start the search for the position to put a new rectangle
at currentIndex - 1,moving "right" from there.
It's really quite likely I've made a logical error here.
(I would imagine the probability of my having made an error,
as opposed to you, is 0.9.)
> Finding the best fit by comparing floating point numbers is not guaranteed
> to find the theoretical best fit. In particular, it may cause you to miss
> some exact fits which might be vital to the packing process.
True, though improbable I think with squares of order 10000.
I did look through a couple of lists, and there did not appear to be
any near repetitions of floats.
But I'll try using exact comparison instead
> It would probably be helpful if you would post the entire source code.
I'll do that.
But first I'll make the change above.
Also I have a debug module to check that the list is in correct order
which I'll run after inserting a rectangle.
On the other hand, I was thinking that you were sailing pretty near the wind
to have only two rectangles in your list, admittedly with maximum cut-off,
and even though one of them was very large.
This made me think that it could conceivably be possible to prove the result
by showing that the largest recangle left was always more than
a given multiple of the next square to be removed.
(In my earlier experiments I thought this ratio
was fairly steadily increasing.)
I was just wondering too -- suppose one could prove that
it was always possible to insert n rectangles,
would that show that one could insert them all at once?
Timothy Murphy
> That packing was done by a program that I wrote back in 1999:
> http://tinylink.com/?0g6QpfQTMZ
> It does not use the same method as I am now using. I dug out the old
> program but it now does not produce the picture at
> http://www.pisquaredoversix.force9.co.uk/Tiling.htm
> the 24 and 25 are interchanged, and possibly other changes.
So you've been doing this for years ...
I said in my last posting that the probability of my being right,
and you wrong, was 0.1.
Make that 0.01!
Timothy Murphy
> Certainly. I expect it is faster for Mathematica to compare two rationals
> than a rational and an irrational.
As a matter of interest, is there any way of determining
if a rational function f(theta)/g(theta) is >0 or <0
knowing the continued fraction for theta?
Or does mathematica in this case know the continued fraction for pi^2?
(Is there a simple continued fraction for pi^2?)
I know there is an exact generalised continued fraction for pi,
with numerators != 1.
I wonder if mathematica uses this, or if it "remembers" the first n integers
in the standard continued fraction?
I don't use mathematica -- does it give you information like that,
or is it secret?
David W. Cantrell
> is pi^2/6, the question arises as to whether squares with sides 1, 1/2,
> 1/3, etc can be packed into a rectangle of size 1 by pi^2/6.
>
> A picture of such a packing appears at
> http://www.pisquaredoversix.force9.co.uk/Tiling.htm
>
> I know of no proof that such a packing is possible or impossible.
It would be good if people interested in this thread were aware of some of
the history of this problem. To that end:
_Unsolved Problems in Geometry_ by Croft, Falconer and Guy (Springer-Verlag,
1991) "D5. Packing unequal rectangles and squares in a square." (pp. 112-113)
mentions a question similar to the one considered in this thread.
D5 caused me, in 1996, to consider several packing problems of this sort.
I found simple algorithms, which I implemented in Mathematica, which seemed
to pack rectangles of decreasing size "perfectly". The algorithms worked
for classic problems, such as packing the rectangles 1/n by 1/(n+1) into
the unit square, as well as for interesting new packing problems. I did not
publish my results then, hoping first to prove that the algorithms were
adequate for packing all of the rectangles. In November 1999, spurred by
Clive Tooth, I posted to sci.math a brief description of what I had done.
See both parts of "Packing Rectangles of Decreasing Size" at
<http://mathforum.org/discuss/sci.math/a/t/241167>. (Readers may also be
interested in looking at the packing algorithm which Clive had used back
then.)
Unbeknownst to me in 1999, an algorithm for such packings had appeared
previously in the literature: An Algorithm for Packing Squares, Marc M.
Paulhus, _J. Combin. Theory Ser. A_ 82 (1997) 147-157. His algorithm is
somewhat different from any of the algorithms which I had used (but I
wonder if perhaps it is the same as Clive's current algorithm). For packing
squares of side lengths 1/2, 1/3, 1/4,... into a rectangle 1/2 by
2(pi^2/6 - 1), Paulhus gives two rules:
"Rule 1. Always place the next square in the corner of the smallest width
rectangle into which it will fit."
"Rule 2. After placing a square into the corner of a rectangle, always cut
the remaining area into two rectangular pieces by cutting from the free
corner of the square tot the longer side of the original rectangle."
For older references, see those cited by Paulhus. The most recent articles
known to me concerning such packings -- but again, I may not be up-to-date
with the literature -- are the following:
Perfect Square Packings, Adam Chalcraft,
_J. Combin. Theory Ser. A_ 92 (2000) 158-172.
Compactness Theorems for Geometric Packings, Greg Martin,
<http://arxiv.org/PS_cache/math/pdf/0005/0005054.pdf>.
Perfect Packings of Squares Using the Stack-Pack Strategy, Johan Wastlund,
<www.mai.liu.se/~jowas/dcg.ps>.
Thoughtful comments are welcome.
Regards,
David W. Cantrell
The Last Danish Pastry
> The Last Danish Pastry wrote:
>
> > Certainly. I expect it is faster for Mathematica to compare two
rationals
> > than a rational and an irrational.
>
> As a matter of interest, is there any way of determining
> if a rational function f(theta)/g(theta) is >0 or <0
> knowing the continued fraction for theta?
I am sorry, I do not know.
> Or does mathematica in this case know the continued fraction for pi^2?
I doubt that it does.
In my program I specify the dimensions of the starting rectangle as "1" and
"Zeta[2]". I imagine that Mathematica knows the formula for Zeta[n], where n
is even, in terms of the n'th Bernoulli number. It can tell me the value of
Zeta[1000] (as an exact rational multiple of pi^1000) in 10.0 seconds. But
it can then tell me what Zeta[1002] is in 0.07 seconds. I imagine that it
had computed, and remembered, the values of all the Bernoulli numbers up to
B_1000.
> (Is there a simple continued fraction for pi^2?)
I do not know of one.
> I know there is an exact generalised continued fraction for pi,
> with numerators != 1.
... you may be referring to one discovered by William Brouncker ...
> I wonder if mathematica uses this, or if it "remembers" the first n
integers
> in the standard continued fraction?
It computes the numerical value of pi using equation (63) at
http://mathworld.wolfram.com/PiFormulas.html
I imagine that it then computes the continued fraction from the numerical
value.
> I don't use mathematica -- does it give you information like that,
> or is it secret?
There is an Implementation section in the Help. It gives, in general terms,
the methods used. For example, under "Number-theoretical functions" we read
"To find a requested number of terms ContinuedFraction uses a modification
of Lehmer's indirect method, with a self-restarting divide-and-conquer
algorithm to reduce the numerical precision required at each step." Here is
another quotation: "Pi uses the Chudnovsky formula for computations up to
ten million digits."
Tyler Neylon
>
> As a matter of interest, is there any way of determining
> if a rational function f(theta)/g(theta) is >0 or <0
> knowing the continued fraction for theta?
>
I believe this is undecidable.
If you restrict the form of the continued fraction,
theta, you could probably make that weaker version
decidable.
Let me try to demonstrate the undecidability of
the general problem: if we have a Turing machine
theta which never loops and always outputs the
nth continued fraction digit of our number, can
we always decide the sign of f(theta), where
f is some polynomial?
I'll reduce the halting problem to this. Suppose
we have a machine m, and we want to see if it halts
on the empty input or not. Create machine theta=theta(m)
which works in the following way: it internally simulates
m running on the empty input. When theta is supposed
to output the nth digit of its continued fraction, it
simulates m for n steps. If m halts within that time, it
ouputs a 2. Otherwise, it outputs a 1.
The important thing to notice is that: machine theta
outputs all 1's iff m never halts.
Let f(theta) = theta - phi, where phi is the golden
ratio (whose continued fraction expansion is all 1's).
If we could decide the sign of f(theta), then we could
decide the halting problem. Last time I checked, this
was a contradiction.
-Tyler
Timothy Murphy
>> It would probably be helpful if you would post the entire source code.
Here's my Java program.
I changed the program to use exact arithmetic to compare two rectangles.
I should say again that I do not claim to be a programmer,
certainly not a Java programmer.
I actually wrote the program in Knuth's cweb format.
Anyone interested can find the code at
http://www.maths.tcd.ie/pub/Maths/PackingSquares/SquarePack.w
However, since the program presumably doesn't work properly
this is probably not a good idea!
I'm reasonably sure I've made a simple logical error somewhere.
I'd be very grateful if someone could point it out.
In principle the program should be compiled with something like
javac SquarePack.java
Then it might be run with
java SquarePack 20000 > out
===========================================================
import java.math.*;
import java.io.*;
import java.util.*;
public class SquarePack{
int currentIndex = 0;
int lastIndex = 0;
LinkedList rectangles;
static int maxCount = 0;
static int sumCount = 0;
static float vacantArea = 0;
public SquarePack() {
rectangles = new LinkedList();
}
public SquarePack(long w,long h,long n) {
rectangles = new LinkedList();
Rectangle r = new Rectangle(w,h,n);
addRectangle(r);
}
public SquarePack(double x,double y) {
rectangles = new LinkedList();
long w = (long)(x*1000000);
long h = (long)(y*1000000);
long n = 1000000;
Rectangle r = new Rectangle(w,h,n);
addRectangle(r);
}
public int findIndex(Rectangle r) {
Rectangle s;
int index;
int size = rectangles.size();
for(index = currentIndex; index < size; index++)
if(((Rectangle)rectangles.get(index)).compareTo(r) < 0)
break;
return index;
}
public void checkOrder() {
float lastx = (float)10.0;
for(int index = 0; index <rectangles.size(); index++)
if(((Rectangle)rectangles.get(index)).x > lastx)
System.out.println("List out of order at index " + index);
}
public void printList(boolean verbose) {
int maxCount = 0;
int sumCount = 0;
double vacantArea = 0;
for(int index = 0; index < rectangles.size(); index++) {
Rectangle r = (Rectangle)rectangles.get(index);
if(verbose)
System.out.println(r + " " + index + " " + r.count);
sumCount += r.count;
vacantArea += r.area;
if(r.count > maxCount)
maxCount = r.count;
}
if(first) {
System.out.println(
"square\t list length\t max split(average split)\t vacant space");
first = false;
}
System.out.println(square + "\t " + rectangles.size() + "\t\t\t"
+ maxCount + "(" +sumCount/rectangles.size() + ")\t\t\t "
+ (float)vacantArea);
}
public void addRectangle(Rectangle r) {
int index = findIndex(r);
if(r.x > epsilon)
rectangles.add(index,r);
}
public void removeSquare(int i) {
Rectangle square = new Rectangle(BigInteger.ONE,BigInteger.ONE,
BigInteger.valueOf((long)i));
int index = findIndex(square)-1;
if(index < 0) {
System.err.println("No room for square side 1/" + i);
System.out.println("No room for square of side 1/" + i
+ " = " + 1/(float)i);
printList(true);
System.exit(1);
}
Rectangle r = (Rectangle)rectangles.get(index);
rectangles.remove(index);
currentIndex = index;
BigInteger m = BigInteger.valueOf((long)i);
BigInteger w = r.w.multiply(m);
BigInteger h = r.h.multiply(m);
BigInteger n = r.n.multiply(m);
Rectangle s = new Rectangle(w,h.subtract(r.n),n);
s.count = r.count + 1;
s.check();
addRectangle(s);
Rectangle t = new Rectangle(w.subtract(r.n),r.n,n);
t.count = r.count + 1;
addRectangle(t);
t.check();
checkOrder();
}
static int square = 0;
static float epsilon;
static boolean first = true;
public static void main(String[]args) {
int count = 1000;
if(args.length> 0) {
count = Integer.parseInt(args[0]);
}
epsilon = (float)0.999/(float)count;
SquarePack squarePack = new SquarePack(
6L*33102L*33102L,103993L*103993L,6L*33102L*33102L);
for(square = 1; square <= count; square++) {
squarePack.removeSquare(square);
if(square%16 == 0)
System.err.print(".");
if(square%1024 == 0)
squarePack.printList(false);
}
squarePack.printList(true);
}
class Rectangle{
BigInteger w,h,n;
double x,y;
double area;
int count = 0;
Rectangle(BigInteger w,BigInteger h,BigInteger n) {
this.w = w;
this.h = h;
this.n = n;
x = w.doubleValue()/n.doubleValue();
y = h.doubleValue()/n.doubleValue();
area = x*y;
}
Rectangle(long w,long h,long n) {
this.w = BigInteger.valueOf(w);
this.h = BigInteger.valueOf(h);
this.n = BigInteger.valueOf(n);
x = (double)w/(double)n;
y = (double)h/(double)n;
area = x*y;
}
public void check() {
BigInteger d = w.gcd(n);
d = d.gcd(h);
if(d.compareTo(BigInteger.ONE)> 0) {
w = w.divide(d);
h = h.divide(d);
n = n.divide(d);
}
if(w.compareTo(h)> 0) {
w = w.divide(d);
h = h.divide(d);
n = n.divide(d);
}
if(w.compareTo(h)> 0) {
BigInteger t = w;
w = h;
h = t;
double z = x;
x = y;
y = z;
}
}
public String toString() {
return("(" + (float)x + "," + (float)y + ")");
}
public int compareTo(Rectangle s) {
return this.w.multiply(s.n).compareTo(s.w.multiply(this.n));
}
}
}
===========================================================
Timothy Murphy
> Here's my Java program.
> I changed the program to use exact arithmetic to compare two rectangles.
Apologies .. my news program screwed up slightly.
Lines 177-181 in the routine check() should be omitted,
ie the lines between ========= below.
> public void check() {
>
> BigInteger d = w.gcd(n);
> d = d.gcd(h);
> if(d.compareTo(BigInteger.ONE)> 0) {
> w = w.divide(d);
> h = h.divide(d);
> n = n.divide(d);
> }
========================================
> if(w.compareTo(h)> 0) {
> w = w.divide(d);
> h = h.divide(d);
> n = n.divide(d);
> }
========================================
> if(w.compareTo(h)> 0) {
> BigInteger t = w;
> w = h;
> h = t;
> double z = x;
> x = y;
> y = z;
> }
> }
Glen
Why not retain the advantages of both the rational approximations and
the exact computation by using them as bounding functions, in the
following way -
lets say you had written pseudocode something like this:
if(f <= g)then
{do what you do when it fits}
else
{do what you do when it doesn't}
but you also had fast-to-compare bounds b1 < g < b2
if(f <= b1)then !fast comparison
{it definitely fits - do what you do when it fits}
else
if(f >= b2)then !fast comparison
{it definitely doesn't fit - do what you do when it doesn't}
else
if(f < g)then !slow comparison, but you rarely get to here
{do what you do when it fits}
else
{do what you do when it doesn't}
(of course, if the original test was the other way around, you
make the appropriate changes in the above).
So fast comparisons are made almost always, but the exact comparison
is there precisely when the fast comparisons are inadequate.
Instead of running in say 28% of the time, this might take more like
42% of the time, but it will always fit something when it should fit
and never fit something it shouldn't.
Glen
The Last Danish Pastry
> addRectangle(t);
> t.check();
Calling check after addRectangle does not seem right, as the short side only
gets determined inside check. I would be surprised if this program could
pack many squares.
The Last Danish Pastry
> addRectangle(t);
> t.check();
Calling check after addRectangle does not seem right.
Timothy Murphy
> "Timothy Murphy" <t...@birdsnest.maths.tcd.ie> wrote in message
> news:Jwq6c.1505$qP2....@news.indigo.ie...
>
>> addRectangle(t);
>> t.check();
>
> Calling check after addRectangle does not seem right.
You're quite right.
But amazingly, correcting this does not have any effect.
I guess that adding the rectangle to the list
just uses a pointer to the rectangle,
so correcting its orientation with t.check() still works.
In any case, my program still fails
when adding square 12867 (with pi = 103993/33102)
or square 12909 (with pi = 355/113).
I wonder if it would be difficult for your program
to print out where in the list the new rectangles are installed?
That might be the simplest way to see where we diverge.
The Last Danish Pastry
> The Last Danish Pastry wrote:
>
> > "Timothy Murphy" <t...@birdsnest.maths.tcd.ie> wrote in message
> > news:Jwq6c.1505$qP2....@news.indigo.ie...
> >
> >> addRectangle(t);
> >> t.check();
> >
> > Calling check after addRectangle does not seem right.
>
> You're quite right.
> But amazingly, correcting this does not have any effect.
> I guess that adding the rectangle to the list
> just uses a pointer to the rectangle,
> so correcting its orientation with t.check() still works.
>
> In any case, my program still fails
> when adding square 12867 (with pi = 103993/33102)
> or square 12909 (with pi = 355/113).
>
> I wonder if it would be difficult for your program
> to print out where in the list the new rectangles are installed?
> That might be the simplest way to see where we diverge.
Timothy,
I have seen your program failing on square 12,867 and I have figured out
what is happening.
I got my program and your program to each create a file of the rectangles
created and consumed. I set epsilon to zero in both programs so as not to
muddy the water.
It turns out that the programs diverge on handling the square 1/2838. And
this is because the denominator "n" in your rectangle has reached about 308
(decimal) digits, and 10^308 is about the limit for the Java double type.
So, java considers that the denominator to be infinite and your "x" gets set
to zero, and two rectangles are lost. A few thousand squares later we run
out of room! Here is the relevant part of my trace of your program... (A_B
is the fraction A/B)
2838: [using rectangle with sides...] 16094981_32872272120
[and...]17199753038456098318187292531900352265760260051995881452549956470022
1967241722679887629709877653379316842024689191762371826756590393041246582442
7469710022557460923148099559771185928421132696303874018966516734455356313078
6559427304931265819031157675338313324148233154477206028502065520802182152821
51849_3744094144236083543773638314843627715269318571696205008333867738535687
3438651808765402373556663652296780488565334487764404570018857195645982496201
8732031251163631772196993506082072776028652605002147960661805426860523410214
6511024316739600723313138397689684917743692119985740327094530187614124574990
4000
[candidate new rectangle...]
w=17594760312207317545454046488102800901766390527932126321806039194814701672
1889576913353792630535832136881097253014797498559115155949287200944743381428
5230856983054838340606186940917005918303858000658105306888413389535550875671
1675439618801045521115341012926797570814201791703534074739244013172458745052
7069600
h=16381514555418646064176716055341561673620598327406738398941060515726543978
9110291630889091803773640326818289535917065769825276657160146158122364581820
4049395655252191598708116776792016172663603992121534070046889170699764595234
7289859021192751512176934203901930577226304863128942485410210319985028795726
222050502
n=35935410477903335220427777150656196100948872080332080997214150813308482087
9760251527319947329234156623993313007656667240509978937706183423856711947524
9685105423099342261728412284389411884495850541449684018368958336506528886189
2354606213567884082038412824689021216487264648368962378428458365007447250596
0887392000
x=0.0, y=NaN
Discarding 0.0
[other candidate new rectangle...]
w=49325296998382776510115598247285246153150613946227249838165568786383513945
3708131616554320494103364977009305836502213038762473132057412446879738438932
9809960164941116803777118583273611387070114391888720375547423759673588791280
9655713264938277332230179598298908701492036774086213268786173870246619689441
485600
h=12662230612369039894442486663374276286451329133309401337989482316176350277
6518763751698360581125495639180166669364576194682867842743545956256769537535
2249860966560726660228475082589644779596846561469233269333671013568191996543
0709868292307217787892323053096906700664998114294912747860626626147796776108
5584000
n=35935410477903335220427777150656196100948872080332080997214150813308482087
9760251527319947329234156623993313007656667240509978937706183423856711947524
9685105423099342261728412284389411884495850541449684018368958336506528886189
2354606213567884082038412824689021216487264648368962378428458365007447250596
0887392000
x=0.0, y=0.0
Discarding 0.0
You could try this program fragment:
=====================================
BigInteger i=new
BigInteger("1759476031220731754545404648810280090176639052793212632180603919
4814701672188957691335379263053583213688109725301479749855911515594928720094
4743381428523085698305483834060618694091700591830385800065810530688841338953
5550875671167543961880104552111534101292679757081420179170353407473924401317
24587450527069600");
BigInteger j=new
BigInteger("3593541047790333522042777715065619610094887208033208099721415081
3308482087976025152731994732923415662399331300765666724050997893770618342385
6711947524968510542309934226172841228438941188449585054144968401836895833650
6528886189235460621356788408203841282468902121648726464836896237842845836500
74472505960887392000");
double di = i.doubleValue();
double dj = j.doubleValue();
double dk = di/dj;
System.err.println("i=<"+i+">");
System.err.println("j=<"+j+">");
System.err.println("di="+di);
System.err.println("dj="+dj);
System.err.println("i/j="+dk);
=====================================
One other thing about your program that I noticed is that the method
"checkOrder" does not update lastx each time around the loop so it will
probably never find any mis-ordering.
Timothy Murphy
> I have seen your program failing on square 12,867 and I have figured out
> what is happening.
> It turns out that the programs diverge on handling the square 1/2838. And
> this is because the denominator "n" in your rectangle has reached about
> 308 (decimal) digits, and 10^308 is about the limit for the Java double
> type. So, java considers that the denominator to be infinite and your "x"
> gets set to zero, and two rectangles are lost. A few thousand squares
> later we run out of room! Here is the relevant part of my trace of your
> program... (A_B is the fraction A/B)
Dear Clive,
Thanks very much for your correction.
I should have thought of that.
I'll go back to my homework ...
Actually, I think the use of floating point arithmetic is unnecessary,
as using BigIntegers throughout only increased the time marginally
(45secs instead of 44secs with 10.000 squares).
Or I could use the BigDecimal class to get around the problem.
> One other thing about your program that I noticed is that the method
> "checkOrder" does not update lastx each time around the loop so it will
> probably never find any mis-ordering.
So my feeling of satisfaction that the order was always correct
was misplaced ...
I re-wrote the program to remove arbitrary rectangles (rather than squares),
as I think I read somewhere that there was a similar problem
for 1/n x 1/n+1 rectangles fitting into a 1 x 1 container.
I wonder if your work has led you to any ideas
about how one might prove the result (for squares)?
I thought when I'd got the Java right
I'd see how critical it is to remove the square
from the smallest possible rectangle at each point.
I wondered too how the length of the list of rectangles
varies as a function of the number of squares
and the cut-off (epsilon) chosen?
Can one predict from that that the algorithm
is likely to work indefinitely?
I had the impression from my mistaken figures
that the descent was too steep to avoid a crash
unless there was divine intervention.
Tim
The Last Danish Pastry
David W. Cantrell has mentioned this classic problem.
> I wonder if your work has led you to any ideas
> about how one might prove the result (for squares)?
Sadly, no.
> I thought when I'd got the Java right
> I'd see how critical it is to remove the square
> from the smallest possible rectangle at each point.
>
> I wondered too how the length of the list of rectangles
> varies as a function of the number of squares
> and the cut-off (epsilon) chosen?
> Can one predict from that that the algorithm
> is likely to work indefinitely?
> I had the impression from my mistaken figures
> that the descent was too steep to avoid a crash
> unless there was divine intervention.
--
Clive Tooth
http://www.clivetooth.dk
Timothy Murphy
>> Dear Clive,
>>
>> Thanks very much for your correction.
...
>> I wonder if your work has led you to any ideas
>> about how one might prove the result (for squares)?
>
> Sadly, no.
>
>> I thought when I'd got the Java right
>> I'd see how critical it is to remove the square
>> from the smallest possible rectangle at each point.
It struck me after that there is really no need
to use exact arithmetic here,
since ordinary arithmetic is exact for addition and subtraction.
So I'm just storing each rectangle as two longs, (w,h)
where w = 2^{60}x, h = 2^{60}y (say).
Now the only imprecision occurs when choosing the original container,
and when entering each square.
If one ensures that the container chosen is slightly smaller than the truth
and the squares are slightly larger,
then the result will prove that the squares _can_ actually be packed
up to say the 10^6th square.
What I found interesting was that
the ratio of the size of the first (largest) rectangle in the list
to the size of the square currently being added
seems to be steadily increasing
(from something like 10 at 10000 to 50 at 100000)
suggesting that it is actually getting easier to pack the squares
as the number of squares increases.
This is independent of the cutoff chosen,
and seems (to me) strong experimental evidence
that the process can continue indefinitely.
The Last Danish Pastry
Hmmm... reminds me of the experimental evidence for Goldbach's conjecture...
:)
David W. Cantrell
[snip]
> What I found interesting was that
> the ratio of the size of the first (largest) rectangle in the list
> to the size of the square currently being added
> seems to be steadily increasing
> (from something like 10 at 10000 to 50 at 100000)
> suggesting that it is actually getting easier to pack the squares
> as the number of squares increases.
>
> This is independent of the cutoff chosen,
> and seems (to me) strong experimental evidence
> that the process can continue indefinitely.
I completely agree. It does indeed seem that the process can continue
indefinitely, whether one uses my packing algorithm, or Clive's, or the one
given by Marc Paulhus. (BTW, for all I know, the latter two algorithms may
actually be the same.)
In 1996, when I discovered the efficacy of such a simple packing algorithm,
I very much wanted to prove that the algorithm could pack all of the
squares. It was "clear" to me that the algorithm could do so; as more and
more squares were packed, the "leeway" got greater and greater. If you
looked at my articles (to which I gave a link earlier in this thread), you
noticed that I actually considered several different related packing
problems, and that the same algorithm did not work for them all. From my
experience, it seems that, if an algorithm is reasonably promising for a
certain packing problem, there will often be times toward the beginning of
the packing process (when the larger objects are being packed) that the
leeway will be small and fluctuating, sometime dropping to zero (meaning
that the object to be packed could go in essentially only one spot). And
sometimes, although the algorithm had seemed promising, the leeway would
become negative (meaning that the algorithm failed, there being no place
that the object would fit). But if the algorithm succeeding in getting past
this perilous initial phase, the leeway then grew and grew. So my idea for
a proof that a certain algorithm worked (i.e., could be continued
indefinitely) for a given packing problem was to define leeway,
quantitatively, and prove that it never became negative... I never
succeeded in doing that for any of the classic packing problems. But, in
looking quickly at some of the recent work (to which I gave links earlier),
I was happy to see that similar ideas seem to have been used successfully
for some related, albeit non-classic, packing problems.
Regards,
David W. Cantrell