Sage: Ticket #16662: OA for n=1046,1059,2164,3992,3994
https://trac.sagemath.org/ticket/16662
<p>
As the title says ! New MOLS from another paper.
</p>
<p>
Nathann
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/16662
Trac 1.1.6ncohenWed, 16 Jul 2014 12:46:26 GMTstatus changed; branch set
https://trac.sagemath.org/ticket/16662#comment:1
https://trac.sagemath.org/ticket/16662#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>branch</strong>
set to <em>u/ncohen/16662</em>
</li>
</ul>
TicketgitWed, 16 Jul 2014 12:47:03 GMTcommit set
https://trac.sagemath.org/ticket/16662#comment:2
https://trac.sagemath.org/ticket/16662#comment:2
<ul>
<li><strong>commit</strong>
set to <em>6e47439f639b269679ee5640d4c497ec73ded499</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=00654fb8dbffe2134dc0b55ead5cea52dadf1654"><span class="icon"></span>00654fb</a></td><td><code>trac #16604: new OA for n=112,160,224,514,796</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=ba6609df5508dd25035203e9e53ce9e4d1ca1ee7"><span class="icon"></span>ba6609d</a></td><td><code>trac #16604: OA for n=640, reviewer's remarks and silly mistake</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=c218148c1f076c08ad5a448754421e82c78b5509"><span class="icon"></span>c218148</a></td><td><code>trac #16604: OA(15,896)</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=6074f4b7fcfcbb18b60726954adfa78e68716384"><span class="icon"></span>6074f4b</a></td><td><code>trac #16604: OA(16,208)</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=35cbadc1fe6d60fe52b86ec19a6ad337ddb201d2"><span class="icon"></span>35cbadc</a></td><td><code>trac #16604: OA(16,176)</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=bfcc6f5e263fa92bf04424dfabe825314c6b225d"><span class="icon"></span>bfcc6f5</a></td><td><code>trac #16604: Now without copy and paste</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=326ece4053b973beef506e427f5bc29846cfa8ed"><span class="icon"></span>326ece4</a></td><td><code>trac #16604: OA(20,352)</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=a6212204674050c40fca7a7c41d4f25c6c2c066c"><span class="icon"></span>a621220</a></td><td><code>trac #16604: OA(20,416)</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=54fc1e1fdf98c8c09142b00d1a905e0f7f2aa6a0"><span class="icon"></span>54fc1e1</a></td><td><code>trac #16604: OA(20,544)</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=6e47439f639b269679ee5640d4c497ec73ded499"><span class="icon"></span>6e47439</a></td><td><code>trac #16662: OA for n=1046,1059,2164,3992,3994</code>
</td></tr></table>
TicketgitSat, 26 Jul 2014 07:17:27 GMTcommit changed
https://trac.sagemath.org/ticket/16662#comment:3
https://trac.sagemath.org/ticket/16662#comment:3
<ul>
<li><strong>commit</strong>
changed from <em>6e47439f639b269679ee5640d4c497ec73ded499</em> to <em>355ac2a741154e5fca99ec1d5137c5be0b9d4377</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=0232b73b42b1460f05622dbfc81f8d3f51b9a50b"><span class="icon"></span>0232b73</a></td><td><code>trac #16604: OA(20,544)</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=e5f428d75ade25f0524abbb61c71a67039ed754a"><span class="icon"></span>e5f428d</a></td><td><code>trac #16604: Merged with 6.3.beta6</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=355ac2a741154e5fca99ec1d5137c5be0b9d4377"><span class="icon"></span>355ac2a</a></td><td><code>trac #16662: OA for n=1046,1059,2164,3992,3994</code>
</td></tr></table>
Ticketvbraun_spamSun, 10 Aug 2014 16:51:03 GMTmilestone changed
https://trac.sagemath.org/ticket/16662#comment:4
https://trac.sagemath.org/ticket/16662#comment:4
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.3</em> to <em>sage-6.4</em>
</li>
</ul>
TicketvdelecroixMon, 11 Aug 2014 10:19:16 GMTstatus changed
https://trac.sagemath.org/ticket/16662#comment:5
https://trac.sagemath.org/ticket/16662#comment:5
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
</ul>
<p>
Hello
</p>
<p>
1) I corrected typos in the doc, added a check, added a test, modify few sentences at u/vdelecroix/16662
</p>
<p>
2) I do not understand why he following is not valid
</p>
<pre class="wiki">sage: k=10; n=2; m=79; a=b=c=1
sage: for kk,nn in ((k,m),(k,m+1),(k,m+2),(k,a),(k,b),(k,c)):
....: assert designs.orthogonal_array(k,n,existence=True)
sage: OA=thwart_lemma_3_5(10,2,79,1,1,1)
Traceback (most recent call last):
...
913 if existence:
914 return Unknown
--> 915 raise NotImplementedError("I don't know how to build an OA({},{})!".format(k,n))
916
917 if check:
NotImplementedError: I don't know how to build an OA(10,69)!
</pre><p>
Are a,b,c allowed to be 1? In the examples of the article a,b,c are never 1 (but d might be).
</p>
<p>
3) I found two examples which yield to error I do not understand from the specifications. The first one is related to the point 2) I guess
</p>
<pre class="wiki">sage: OA=thwart_lemma_3_5(10,2,89,1,1,1)
Traceback (most recent call last):
...
456 for B in master_design:
457 # The missing entries belong to the last n_trunc columns
--> 458 assert all(x is not None for x in B[:k])
459 n_in_truncated = n_trunc-B.count(None)
460
AssertionError:
</pre><p>
For the other one, the existence of an OA(9,21) should not be necessary for the construction
</p>
<pre class="wiki">sage: OA = thwart_lemma_3_5(9,9,22,8,8,8,complement=True)
Traceback (most recent call last):
...
913 if existence:
914 return Unknown
--> 915 raise NotImplementedError("I don't know how to build an OA({},{})!".format(k,n))
916
917 if check:
NotImplementedError: I don't know how to build an OA(9,21)!
</pre><p>
4) I found several new values for which the thwart construction works. But I first would like to understand first why 3) fail.
</p>
<p>
Vincent
</p>
TicketncohenMon, 11 Aug 2014 10:59:41 GMT
https://trac.sagemath.org/ticket/16662#comment:6
https://trac.sagemath.org/ticket/16662#comment:6
<p>
Hello !
</p>
<blockquote class="citation">
<p>
1) I corrected typos in the doc, added a check, added a test, modify few sentences at u/vdelecroix/16662
</p>
</blockquote>
<p>
Is it me or is the git server slow ? It takes MINUTES to download a branch <code>O_o</code>
</p>
<blockquote class="citation">
<p>
2) I do not understand why he following is not valid
</p>
</blockquote>
<p>
How, not "valid" ? The input is valid but in order to build the new designs you need some sub-designs, and among the subdesigns there is a <code>OA(10,69)</code> that Sage does not know how to build. Soo well, the construction can't be applied because you need one of the required designs... What's wrong with that ? This is what the <code>find_</code> functions usually checks !
</p>
<blockquote class="citation">
<p>
Are a,b,c allowed to be 1? In the examples of the article a,b,c are never 1 (but d might be).
</p>
</blockquote>
<p>
I don't think that there is anything wrong with =1 values.
</p>
<blockquote class="citation">
<p>
3) I found two examples which yield to error I do not understand from the specifications. The first one is related to the point 2) I guess
</p>
</blockquote>
<p>
No, it is just that there exists no <code>OA(13,2)</code>. The code has to build an <code>OA(k+3,n)</code> (or <code>OA(k+4,n)</code> when <code>d</code> is defined) and it does not exist if k is too large. I missed that one, probably because that's the kind of thing that I filter in the <code>find_</code> function usually.
</p>
<blockquote class="citation">
<p>
For the other one, the existence of an OA(9,21) should not be necessary for the construction
</p>
</blockquote>
<p>
The exception I added for the previous one is also triggered here.
</p>
<blockquote class="citation">
<p>
4) I found several new values for which the thwart construction works. But I first would like to understand first why 3) fail.
</p>
</blockquote>
<p>
Nathann
</p>
TicketgitMon, 11 Aug 2014 11:00:18 GMTcommit changed
https://trac.sagemath.org/ticket/16662#comment:7
https://trac.sagemath.org/ticket/16662#comment:7
<ul>
<li><strong>commit</strong>
changed from <em>355ac2a741154e5fca99ec1d5137c5be0b9d4377</em> to <em>8fcaed066b7f110af10c6a471cbebcad370bd312</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=053945db4f9a536337e83837364598308769a206"><span class="icon"></span>053945d</a></td><td><code>trac #16662: merge 6.3</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=166b5253a4aea402bd37dee3af159f89b02acc23"><span class="icon"></span>166b525</a></td><td><code>trac #16662: doc + test</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=8fcaed066b7f110af10c6a471cbebcad370bd312"><span class="icon"></span>8fcaed0</a></td><td><code>trac #16662: New assertion</code>
</td></tr></table>
TicketncohenMon, 11 Aug 2014 11:01:46 GMTstatus changed
https://trac.sagemath.org/ticket/16662#comment:8
https://trac.sagemath.org/ticket/16662#comment:8
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
TicketvdelecroixMon, 11 Aug 2014 12:04:54 GMT
https://trac.sagemath.org/ticket/16662#comment:9
https://trac.sagemath.org/ticket/16662#comment:9
<p>
Hi,
</p>
<p>
You add a check at the begining but there is no associated specification in the doc...
</p>
<p>
Vincent
</p>
TicketvdelecroixMon, 11 Aug 2014 12:30:53 GMT
https://trac.sagemath.org/ticket/16662#comment:10
https://trac.sagemath.org/ticket/16662#comment:10
<p>
Very bad... I was not able to build the potentially new <code>OA(12,3362)</code>
</p>
<pre class="wiki">sage: OA=thwart_lemma_3_5(12,16,207,13,13,13,11,complement=True)
Traceback (most recent call last):
...
.../incidence_structures.pyc in blocks(self, copy)
520 if self._point_to_index is None:
521 from copy import deepcopy
--> 522 return deepcopy(self._blocks)
523 else:
524 return [[self._points[i] for i in b] for b in self._blocks]
...
MemoryError:
</pre>
TicketncohenMon, 11 Aug 2014 12:33:58 GMT
https://trac.sagemath.org/ticket/16662#comment:11
https://trac.sagemath.org/ticket/16662#comment:11
<p>
Well you can't build a <code>OA(2^300+1,2^300)</code> either... <code>:-P</code>
</p>
<p>
This deepcopy is a crime.
</p>
<p>
Nathann
</p>
TicketvdelecroixMon, 11 Aug 2014 12:39:37 GMT
https://trac.sagemath.org/ticket/16662#comment:12
https://trac.sagemath.org/ticket/16662#comment:12
<p>
I said that because this one is smaller than the largest you add to the database: an OA(12,3994).
</p>
<p>
I will create a ticket to remove all deepcopy around (and in that case I think it is more like a <code>toto.blocks(copy=False)</code> which is needed).
</p>
<p>
Vincent
</p>
TicketncohenMon, 11 Aug 2014 12:41:00 GMT
https://trac.sagemath.org/ticket/16662#comment:13
https://trac.sagemath.org/ticket/16662#comment:13
<p>
Yoooooooo !
</p>
<blockquote class="citation">
<p>
I said that because this one is smaller than the largest you add to the database: an OA(12,3994).
</p>
<p>
I will create a ticket to remove all deepcopy around (and in that case I think it is more like a <code>toto.blocks(copy=False)</code> which is needed).
</p>
</blockquote>
<p>
Please don't, I fixed that in at least two <code>needs_review</code> tickets already <code>^^;</code>
</p>
<p>
Nathann
</p>
TicketvdelecroixMon, 11 Aug 2014 12:47:01 GMT
https://trac.sagemath.org/ticket/16662#comment:14
https://trac.sagemath.org/ticket/16662#comment:14
<p>
All right...
</p>
<p>
I put constructions for OA(10,1048), OA(11,1524) and OA(12,3362) at <code>u/vdelecroix/16662</code>. And by the way, I wrote a function which compute the set of new values you get by using this construction... should I add it somewhere? It is not exactly a <code>find_XXX</code> function, it go the other way around: play with parameters m,n,a,b,c,d and see if the m*n+a+b+c+d you obtain is already available.
</p>
<p>
Vincent
</p>
TicketncohenMon, 11 Aug 2014 18:08:29 GMT
https://trac.sagemath.org/ticket/16662#comment:15
https://trac.sagemath.org/ticket/16662#comment:15
<p>
Yo !
</p>
<blockquote class="citation">
<p>
I put constructions for OA(10,1048), OA(11,1524) and OA(12,3362) at <code>u/vdelecroix/16662</code>.
</p>
</blockquote>
<p>
Oh. Are they the only other MOLS that we can build ? If there are more it may be worth writing a find function after all...
</p>
<p>
Nathann
</p>
TicketvdelecroixMon, 11 Aug 2014 19:37:47 GMT
https://trac.sagemath.org/ticket/16662#comment:16
https://trac.sagemath.org/ticket/16662#comment:16
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16662#comment:15" title="Comment 15">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Yo !
</p>
<blockquote class="citation">
<p>
I put constructions for OA(10,1048), OA(11,1524) and OA(12,3362) at <code>u/vdelecroix/16662</code>.
</p>
</blockquote>
<p>
Oh. Are they the only other MOLS that we can build ? If there are more it may be worth writing a find function after all...
</p>
</blockquote>
<p>
Seems to be the only one. If you want to write this find function that's also an option. But I am not sure you will ever get the <code>OA(10,1046)</code> in less than a minute. A possible alternative is to write a function that checks that:
</p>
<ul><li>those constructions are not useless (i.e. there are no other way to get them)
</li><li>there is nothing more to build with these thwarts (this is pretty much what I wrote)
</li></ul><p>
Vincent
</p>
TicketncohenMon, 11 Aug 2014 19:40:53 GMT
https://trac.sagemath.org/ticket/16662#comment:17
https://trac.sagemath.org/ticket/16662#comment:17
<p>
Yo !
</p>
<blockquote class="citation">
<p>
Seems to be the only one. If you want to write this find function that's also an option.
</p>
</blockquote>
<p>
I tried several times and it really was complicated. And required a lot of copy/paste.
</p>
<blockquote class="citation">
<p>
But I am not sure you will ever get the <code>OA(10,1046)</code> in less than a minute
</p>
</blockquote>
<p>
Well, you need to fill the cache at first, like for all constructions.
</p>
<blockquote class="citation">
<p>
A possible alternative is to write a function that checks that:
</p>
<ul><li>those constructions are not useless (i.e. there are no other way to get them)
</li></ul></blockquote>
<p>
Why do you care so much about not having useless constructions ? It is good to have several ways to generate the same design. Some paths may be better than others, some paths may result in designs with different properties...
</p>
<blockquote class="citation">
<ul><li>there is nothing more to build with these thwarts (this is pretty much what I wrote)
</li></ul></blockquote>
<p>
The problem with that is that it is true with the current OA that Sage can build. Wait a bit and new one will appear that may change that.
</p>
<p>
Nathann
</p>
TicketvdelecroixMon, 11 Aug 2014 19:45:38 GMT
https://trac.sagemath.org/ticket/16662#comment:18
https://trac.sagemath.org/ticket/16662#comment:18
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16662#comment:17" title="Comment 17">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Yo !
</p>
<blockquote class="citation">
<p>
Seems to be the only one. If you want to write this find function that's also an option.
</p>
</blockquote>
<p>
I tried several times and it really was complicated. And required a lot of copy/paste.
</p>
</blockquote>
<p>
So let us not do that.
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
A possible alternative is to write a function that checks that:
</p>
<ul><li>those constructions are not useless (i.e. there are no other way to get them)
</li></ul></blockquote>
<p>
Why do you care so much about not having useless constructions ? It is good to have several ways to generate the same design. Some paths may be better than others, some paths may result in designs with different properties...
</p>
</blockquote>
<p>
All right. Then there are thousands of thwarts construction that you may want to consider...
</p>
<blockquote class="citation">
<blockquote class="citation">
<ul><li>there is nothing more to build with these thwarts (this is pretty much what I wrote)
</li></ul></blockquote>
<p>
The problem with that is that it is true with the current OA that Sage can build. Wait a bit and new one will appear that may change that.
</p>
</blockquote>
<p>
This is cool. If a ticket creates new OA that allows more of this construction, then it will create an error in a doctest and the database will be automatically updated. Nevertheless, filling the cache up to 3000 is too long for a doctest. So I can keep my file under my pillow and run it from time to time.
</p>
<p>
Vincent
</p>
TicketncohenMon, 11 Aug 2014 19:48:52 GMT
https://trac.sagemath.org/ticket/16662#comment:19
https://trac.sagemath.org/ticket/16662#comment:19
<p>
Yo !
</p>
<blockquote class="citation">
<p>
So let us not do that.
</p>
</blockquote>
<p>
Hmmmmmmmmm. I know it will haunt me <code>:-P</code>
</p>
<blockquote class="citation">
<p>
All right. Then there are thousands of thwarts construction that you may want to consider...
</p>
</blockquote>
<p>
Well, for the moment I try to fill the table until we stick to the Handbook.
</p>
<blockquote class="citation">
<p>
This is cool. If a ticket creates new OA that allows more of this construction, then it will create an error in a doctest and the database will be automatically updated. Nevertheless, filling the cache up to 3000 is too long for a doctest. So I can keep my file under my pillow and run it from time to time.
</p>
</blockquote>
<p>
Under a pillow is no place to store code. You can't wash away the stains of a memory leak.
</p>
<p>
Nathann
</p>
TicketvdelecroixTue, 12 Aug 2014 08:50:23 GMT
https://trac.sagemath.org/ticket/16662#comment:20
https://trac.sagemath.org/ticket/16662#comment:20
<p>
All right, I wrote the <code>find_thwart_lemma_3_5</code>... it works at least for the parameters that were found before. It is at <code>u/vdelecroix/16662</code>.
</p>
<p>
Vincent
</p>
TicketncohenTue, 12 Aug 2014 15:46:16 GMT
https://trac.sagemath.org/ticket/16662#comment:21
https://trac.sagemath.org/ticket/16662#comment:21
<p>
Could you add some comments ? So many loops and tests, even an internal caching system and no comments is a bit tough.
</p>
<p>
Also, I don't think you should implement caching systems like that in a <code>find_</code> function. If we need such caching (and we do) it should be implemented where it belongs, with a dedicated function.
</p>
<p>
I had in mind something like that:
</p>
<pre class="wiki">designs.orthogonal_arrays.build(k,n)
designs.orthogonal_arrays.build_information(k,n)
designs.orthogonal_arrays.is_available(k,n)
designs.orthogonal_arrays.exists(k,n)
designs.orthogonal_arrays.max_k(n)
designs.orthogonal_arrays.all_n(k, min=None, max=None)
</pre><p>
Though I like this interface, it means quite some amount of copy/paste in the code. For TD and MOLS. Maybe there is a trick.
</p>
<p>
Nathann
</p>
TicketvdelecroixWed, 13 Aug 2014 06:48:57 GMT
https://trac.sagemath.org/ticket/16662#comment:22
https://trac.sagemath.org/ticket/16662#comment:22
<p>
Hello,
</p>
<p>
It is not only caching. With a more naive approach you would have
</p>
<pre class="wiki">for a in xrange(n):
if not orthogonal_arrays(k,a,existence=True):
continue
for b in xrange(a+1):
if not orthogonal_arrays(k,b,existence=True):
continue
for c in xrange(b+1):
if not orthogonal_arrays(k,c,existence=True):
continue
</pre><p>
About your caching system, what would be the difference between <code>is_available</code> and <code>exists</code>? And instead of <code>all_n</code> I would prefer <code>nrange</code> or something more pythonic.
</p>
<p>
I will write some doc but I won't change the code.
</p>
<p>
Vincent
</p>
TicketvdelecroixWed, 13 Aug 2014 07:50:13 GMT
https://trac.sagemath.org/ticket/16662#comment:23
https://trac.sagemath.org/ticket/16662#comment:23
<p>
It is at <code>u/vdelecroix/16662</code>.
</p>
<p>
Vincent
</p>
TicketncohenWed, 13 Aug 2014 13:56:11 GMT
https://trac.sagemath.org/ticket/16662#comment:24
https://trac.sagemath.org/ticket/16662#comment:24
<p>
Yo !
</p>
<blockquote class="citation">
<p>
It is not only caching. With a more naive approach you would have
</p>
</blockquote>
<p>
What you do there is the work of the "all_n" function I wound like to write. I would like to replace the
</p>
<pre class="wiki">for n in range(N-2):
if is_prime(n)
</pre><p>
with
</p>
<pre class="wiki">for n in prime_powers(N-2):
...
</pre><p>
But it is not possible because you use n to build the cache.
</p>
<blockquote class="citation">
<p>
About your caching system, what would be the difference between <code>is_available</code> and <code>exists</code>? And instead of <code>all_n</code> I would prefer <code>nrange</code> or something more pythonic.
</p>
</blockquote>
<p>
<code>is_available</code> would not trigger non-existence tests. But perhaps that is less useful since your rewrote the <code>is_sum_of_squares</code> thing.
</p>
<p>
Nathann
</p>
TicketncohenWed, 13 Aug 2014 14:17:52 GMT
https://trac.sagemath.org/ticket/16662#comment:25
https://trac.sagemath.org/ticket/16662#comment:25
<p>
With the find function
</p>
<pre class="wiki">sage: %time designs.orthogonal_array(None,1000,existence=1)
CPU times: user 24.6 s, sys: 52 ms, total: 24.6 s
Wall time: 24.6 s
9
</pre><p>
Without
</p>
<pre class="wiki">sage: %time designs.orthogonal_array(None,1000,existence=1)
CPU times: user 14.5 s, sys: 32 ms, total: 14.5 s
Wall time: 14.5 s
9
</pre>
TicketncohenWed, 13 Aug 2014 14:47:27 GMT
https://trac.sagemath.org/ticket/16662#comment:26
https://trac.sagemath.org/ticket/16662#comment:26
<p>
Yo !
</p>
<p>
It seems that the list "good" is very very often useless. I wanted to know how often it was used and added a "print n" right before the loop "for a in good"
</p>
<div class="wiki-code"><div class="code"><pre><span class="gu">@@ -999,6 +999,7 @@ def find_thwart_lemma_3_5(k,N):
</span> orthogonal_array(k,m+2,existence=True)):
continue
<span class="gi">+ print "A",n
</span> for a in good:
if a > N-n*m:
break
<span class="gu">@@ -1023,7 +1024,7 @@ def find_thwart_lemma_3_5(k,N):
</span> orthogonal_array(k,m+2,existence=True) and
orthogonal_array(k,m+3,existence=True)):
continue
<span class="gd">-
</span><span class="gi">+ print "B",n
</span> for a in good:
if a > N-n*m:
break
</pre></div></div><p>
Guess how many times they appear when you type <code>designs.orthogonal_array(None,1000,existence=1)</code>: never.
</p>
<p>
Which means that for 1000 at least computing all <code>OA(k,n,existence=True)</code> for n<N is all for naught (but takes 10s).
</p>
<p>
Nathann
</p>
TicketncohenWed, 13 Aug 2014 14:48:44 GMT
https://trac.sagemath.org/ticket/16662#comment:27
https://trac.sagemath.org/ticket/16662#comment:27
<p>
By the way, shouldn't <code>range(N-3)</code> be <code>range(N-2)</code> ? The last element is not included in the list, so m=a=b=c=1 is not tested.
</p>
<p>
Nathann
</p>
TicketvdelecroixWed, 13 Aug 2014 15:42:27 GMT
https://trac.sagemath.org/ticket/16662#comment:28
https://trac.sagemath.org/ticket/16662#comment:28
<p>
Hello,
</p>
<p>
Moving the <code>good</code> part would change nothing to the timings. You already have the following for the <code>m</code> loop which is the cost of everything
</p>
<pre class="wiki"> if not (orthogonal_array(k,m+0,existence=True) and
orthogonal_array(k,m+1,existence=True) and
orthogonal_array(k,m+2,existence=True)):
continue
</pre><p>
If you feel like this function is too costly, we can remove it from the <code>find_recursive_constructions</code> and just store the interesting values:
</p>
<pre class="wiki">if (k,n) not in ((10,1046), (10,1048), (10,1059), (11,1524),
(11,2164), (12,3362), (12,3992), (12,3994)):
return False
</pre><p>
About your question, you were right and we can even go up to <code>n=N-1</code>.
</p>
<p>
Tell me what you think about the first question and I will add a commit.
</p>
<p>
Vincent
</p>
TicketvdelecroixThu, 14 Aug 2014 18:41:55 GMT
https://trac.sagemath.org/ticket/16662#comment:29
https://trac.sagemath.org/ticket/16662#comment:29
<p>
Commit a <code>u/vdelecroix/16662</code>.
</p>
<ul><li>I removed the good
</li><li>I cut the loop as much as possible
</li></ul><p>
Vincent
</p>
TicketncohenThu, 14 Aug 2014 21:30:32 GMT
https://trac.sagemath.org/ticket/16662#comment:30
https://trac.sagemath.org/ticket/16662#comment:30
<p>
Helloooooooo Vincent !
</p>
<p>
Okay... So let's do that:
</p>
<p>
1) You saved some time since the first version, and although it is still slower than needed it's not that awful that we should keep this construction out of those that are automatically tested
</p>
<p>
2) Those triple loops are really awful things, so we will have to do something about it
</p>
<p>
3) I am thinking of a data structure that would be useful to us, and whose purpose is to store things like "all n such that there exists a OA(k,n)" or even "all m such that there exists a OA(k,m), OA(k,m+1), OA(k,m+2)".
</p>
<p>
What it stores: a set of integers defined by a boolean function
What it is meant to answer: give the list of integers between x and y such that the boolean function is satisfied.
</p>
<p>
Of course we want to minimize the number of boolean function queries. Even though it takes spaces, I am thinking of something like that:
</p>
<p>
An array which associates to (any) integer n:
</p>
<p>
a) if f(n) is computed: the smallest integer n'>=n such that f(n') is True or has not been computed yet.
</p>
<p>
b) if f(n) is not computed yet: None
</p>
<p>
This way, if you want to get all solutions to <code>f(n) is True</code> between x and y, here is what you do:
</p>
<pre class="wiki">current=x
while current<=y:
if array[current] is None:
array[current] = f(current)
elif array[current] == current:
yield current
current+=1
else:
new_current = array[current]
# if array[a]==b and array[b]==c then let's define array[a]=c
if array[new_current] is not None:
array[current] = array[new_current]
current = new_current
</pre><p>
This may be cool if we ever implement the <code>all_n</code> or <code>range_n</code> function.
</p>
<p>
And we could use it in conjunction with a real function to solve the partition problem, i.e. "try to find integers from a set S whose sum is equal or lequal to C".
</p>
<p>
Anyway.
</p>
<p>
1) I merged all your commits into one, as some were undoing the previous ones
</p>
<p>
2) I added a small commit on top of it. In particular some additional constraint on k that removes fake '+' in the n<100 area <code>:-D</code>
</p>
<p>
Your code is good otherwise.
</p>
<p>
Nathann
</p>
TicketgitThu, 14 Aug 2014 21:33:18 GMTcommit changed
https://trac.sagemath.org/ticket/16662#comment:31
https://trac.sagemath.org/ticket/16662#comment:31
<ul>
<li><strong>commit</strong>
changed from <em>8fcaed066b7f110af10c6a471cbebcad370bd312</em> to <em>2f936c57507cbd475f860a76b94ed44882d7de7b</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=adf5105279da55b5178a1d0692674fdf6984c6b0"><span class="icon"></span>adf5105</a></td><td><code>trac #16662: find_thwart_lemma_3_5</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=2f936c57507cbd475f860a76b94ed44882d7de7b"><span class="icon"></span>2f936c5</a></td><td><code>trac #16662: Review</code>
</td></tr></table>
TicketvdelecroixFri, 15 Aug 2014 08:47:45 GMTstatus changed
https://trac.sagemath.org/ticket/16662#comment:32
https://trac.sagemath.org/ticket/16662#comment:32
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
</ul>
<p>
Hello,
</p>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16662#comment:30" title="Comment 30">ncohen</a>:
</p>
<blockquote class="citation">
<p>
3) I am thinking of a data structure that would be useful to us, and whose purpose is to store things like "all n such that there exists a OA(k,n)" or even "all m such that there exists a OA(k,m), OA(k,m+1), OA(k,m+2)".
</p>
</blockquote>
<p>
+1
</p>
<blockquote class="citation">
<p>
What it stores: a set of integers defined by a boolean function
What it is meant to answer: give the list of integers between x and y such that the boolean function is satisfied.
</p>
<p>
Of course we want to minimize the number of boolean function queries. Even though it takes spaces, I am thinking of something like that:
</p>
<p>
An array which associates to (any) integer n:
</p>
<p>
a) if f(n) is computed: the smallest integer n'>=n such that f(n') is True or has not been computed yet.
</p>
<p>
b) if f(n) is not computed yet: None
</p>
<p>
[...]
</p>
<p>
This may be cool if we ever implement the <code>all_n</code> or <code>range_n</code> function.
</p>
</blockquote>
<p>
And:
</p>
<ul><li>what is the next value (like next_prime)
</li><li>what is the previous value (like previous_prime)
</li></ul><p>
The problem with your approach is that you store a lot of data. It is perhaps not as bad as what I imagine.
</p>
<p>
Questions:
</p>
<p>
1) why do you stop <code>n</code> at <code>N-3</code> in the first loop? I think that <code>n=N-1, m=1, a=1, b=0, c=0</code> is a valid input:
</p>
<pre class="wiki">sage: OA = thwart_lemma_3_5(3,13,1,1,0,0)
sage: is_orthogonal_array(OA,3,14,2)
True
</pre><p>
So the bound should be <code>N-1</code>. Perhaps the particular case of <code>m=1</code> is taken care by another construction, in that case, this must be documented (and the upper bound for n updated accordingly).
</p>
<p>
2) the check <code>d <= n</code> is not necessary because of the lower bound on <code>c</code>.
</p>
<p>
I edit my commit at <code>u/vdelecroix/16662</code> to simplify the code with respect to 2). As soon as 1) is solve, I would be happy to set this to positive review.
</p>
<p>
Vincent
</p>
TicketncohenFri, 15 Aug 2014 10:18:55 GMT
https://trac.sagemath.org/ticket/16662#comment:33
https://trac.sagemath.org/ticket/16662#comment:33
<p>
Yooooooo !
</p>
<blockquote class="citation">
<p>
And:
</p>
<ul><li>what is the next value (like next_prime)
</li></ul></blockquote>
<p>
That's easy to do. It would be the result of all_n(min=current_value,max=None).next()
</p>
<blockquote class="citation">
<ul><li>what is the previous value (like previous_prime)
</li></ul></blockquote>
<p>
This would be harder, but I'm not sure it is needed either <code>O_o</code>
</p>
<blockquote class="citation">
<p>
The problem with your approach is that you store a lot of data. It is perhaps not as bad as what I imagine.
</p>
</blockquote>
<p>
it bothered me at first but we are thinking of k lists (and k<50 usually) or size around 2000 at most. How bad can that be ? If it were stored in C it would represent 500ko <code>:-P</code>
</p>
<blockquote class="citation">
<p>
1) why do you stop <code>n</code> at <code>N-3</code> in the first loop? I think that <code>n=N-1, m=1, a=1, b=0, c=0</code> is a valid input:
</p>
</blockquote>
<p>
Argg... Because I thought we could assume <code>a,c,b>0</code>, I did some changes then removed them, but I forgot one. If d=0 and c=0 I think that what the code does is roughly equivalent to Wilson's construction wth 2 truncated columns. But well, you are right, I will undo that !
</p>
<blockquote class="citation">
<p>
2) the check <code>d <= n</code> is not necessary because of the lower bound on <code>c</code>.
</p>
<p>
I edit my commit at <code>u/vdelecroix/16662</code> to simplify the code with respect to 2). As soon as 1) is solve, I would be happy to set this to positive review.
</p>
</blockquote>
<p>
I just downloaded your branch but did not see anything new. I just merged it with the beta0 but I will add a commit in a second !
</p>
<p>
Nathann
</p>
TicketvdelecroixFri, 15 Aug 2014 12:54:10 GMT
https://trac.sagemath.org/ticket/16662#comment:34
https://trac.sagemath.org/ticket/16662#comment:34
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16662#comment:33" title="Comment 33">ncohen</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
2) the check <code>d <= n</code> is not necessary because of the lower bound on <code>c</code>.
</p>
<p>
I edit my commit at <code>u/vdelecroix/16662</code> to simplify the code with respect to 2). As soon as 1) is solve, I would be happy to set this to positive review.
</p>
</blockquote>
<p>
I just downloaded your branch but did not see anything new. I just merged it with the beta0 but I will add a commit in a second !
</p>
</blockquote>
<p>
I edited my commit. I did not add a commit. My last commit in my branch is 68a2d99 and not 2f936c5.
</p>
<p>
Vincent
</p>
TicketncohenFri, 15 Aug 2014 14:03:15 GMT
https://trac.sagemath.org/ticket/16662#comment:35
https://trac.sagemath.org/ticket/16662#comment:35
<p>
Yo !
</p>
<blockquote class="citation">
<p>
I edited my commit. I did not add a commit. My last commit in my branch is 68a2d99 and not 2f936c5.
</p>
</blockquote>
<p>
Oh, I see. I think that this N-2 is correct after all, however. If n=N-2, then it means that there are at most two points in the last 4 columns, i.e. that at most two columns are used. And because all pairs of points are equivalent, this is already handled by the wilson construction with two truncated columns.
</p>
<p>
I had written some code which I hoped would improve the performances of this function, but well... It produced no difference whatsoever. And I don't know why yet, so let's get this in.
</p>
<p>
Perhaps the cached "all_n" function will change something <code>:-/</code>
</p>
<p>
Nathann
</p>
TicketvdelecroixFri, 15 Aug 2014 16:39:33 GMT
https://trac.sagemath.org/ticket/16662#comment:36
https://trac.sagemath.org/ticket/16662#comment:36
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16662#comment:35" title="Comment 35">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Yo !
</p>
<blockquote class="citation">
<p>
I edited my commit. I did not add a commit. My last commit in my branch is 68a2d99 and not 2f936c5.
</p>
</blockquote>
<p>
Oh, I see. I think that this N-2 is correct after all, however. If n=N-2, then it means that there are at most two points in the last 4 columns, i.e. that at most two columns are used. And because all pairs of points are equivalent, this is already handled by the wilson construction with two truncated columns.
</p>
</blockquote>
<p>
I believe it but please write it in a comment!
</p>
<blockquote class="citation">
<p>
I had written some code which I hoped would improve the performances of this function, but well... It produced no difference whatsoever. And I don't know why yet, so let's get this in.
</p>
<p>
Perhaps the cached "all_n" function will change something <code>:-/</code>
</p>
</blockquote>
<p>
I hope it will.
</p>
<p>
Vincent
</p>
TicketgitFri, 15 Aug 2014 17:36:47 GMTcommit changed
https://trac.sagemath.org/ticket/16662#comment:37
https://trac.sagemath.org/ticket/16662#comment:37
<ul>
<li><strong>commit</strong>
changed from <em>2f936c57507cbd475f860a76b94ed44882d7de7b</em> to <em>a9b594f3991f67cf7d2c82a91d8c332c47c35ba7</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=2a64fa25c95997f68ae816a2fd9e1062f3cf8e60"><span class="icon"></span>2a64fa2</a></td><td><code>trac #16662: find_thwart_lemma_3_5</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=68a2d9926ea5c94e2d792b51695ff92daea578e5"><span class="icon"></span>68a2d99</a></td><td><code>trac #16662: Review</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=7e0480e40d558018c14f3f8eb3c5cb0591a036ea"><span class="icon"></span>7e0480e</a></td><td><code>trac #16662: Merged with 6.4.beta0</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=a9b594f3991f67cf7d2c82a91d8c332c47c35ba7"><span class="icon"></span>a9b594f</a></td><td><code>trac #16662: A comment about n<N-2</code>
</td></tr></table>
TicketvdelecroixSat, 16 Aug 2014 06:17:48 GMTstatus changed
https://trac.sagemath.org/ticket/16662#comment:38
https://trac.sagemath.org/ticket/16662#comment:38
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>positive_review</em>
</li>
</ul>
<p>
Great great... and of lot of rebase for the follow-up tickets!
</p>
<p>
Vincent
</p>
TicketncohenSat, 16 Aug 2014 06:24:29 GMT
https://trac.sagemath.org/ticket/16662#comment:39
https://trac.sagemath.org/ticket/16662#comment:39
<p>
Thanks !
</p>
<p>
Nathann
</p>
TicketvdelecroixSat, 16 Aug 2014 06:49:09 GMTstatus changed
https://trac.sagemath.org/ticket/16662#comment:40
https://trac.sagemath.org/ticket/16662#comment:40
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
There is a (simple) conflict with <a class="closed ticket" href="https://trac.sagemath.org/ticket/16604" title="enhancement: new OA for n=112,160,176,208,224,352,416,514,544,640,796,896 (closed: fixed)">#16604</a>.
</p>
<p>
Vincent
</p>
TicketvdelecroixSat, 16 Aug 2014 06:54:27 GMT
https://trac.sagemath.org/ticket/16662#comment:41
https://trac.sagemath.org/ticket/16662#comment:41
<p>
see at <code>u/vdelecroix/16662</code>.
</p>
<p>
Vincent
</p>
TicketgitSat, 16 Aug 2014 07:02:37 GMTcommit changed
https://trac.sagemath.org/ticket/16662#comment:42
https://trac.sagemath.org/ticket/16662#comment:42
<ul>
<li><strong>commit</strong>
changed from <em>a9b594f3991f67cf7d2c82a91d8c332c47c35ba7</em> to <em>7a73e74549a080ac7ac139241521a871d667cd45</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=3cf39835a05cafffa1406c0ace944f9f4b7e3042"><span class="icon"></span>3cf3983</a></td><td><code>trac #16604: Reviewing the review</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=d612056869f25d94835570fca45572bfd2f5ccc8"><span class="icon"></span>d612056</a></td><td><code>trac #16604: on the doc again</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=bff470ee5b4bb561cae7f01cf08ed7dfe126fa94"><span class="icon"></span>bff470e</a></td><td><code>trac #16604: small check of dimensions</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=6c21904f748561cea56fe47d1c45a8e3d222d7a1"><span class="icon"></span>6c21904</a></td><td><code>trac #16797: correct a row/column inversion</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=48b69020bbb171f4b9d1594b5e686c463c4d92b1"><span class="icon"></span>48b6902</a></td><td><code>trac #16604: merge #16797</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=579e75bd1c2a355082d5cf04b7f0ecc95d6c092a"><span class="icon"></span>579e75b</a></td><td><code>trac #16604: input check + doctest</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=e1a83d0b320496df398fb5373ffb0c1cbe1ae590"><span class="icon"></span>e1a83d0</a></td><td><code>trac #16604: Optional check flag</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=05c691500eb1131cb71303ed759ddf2cbc13b46f"><span class="icon"></span>05c6915</a></td><td><code>trac #16604: Variable rename and list->set</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=24c4f7fc4cf619fca8cceb5707b74b935de880c2"><span class="icon"></span>24c4f7f</a></td><td><code>trac #16604: Merge with updated #16797</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=7a73e74549a080ac7ac139241521a871d667cd45"><span class="icon"></span>7a73e74</a></td><td><code>trac #16662: Merge with updated #16604</code>
</td></tr></table>
TicketncohenSat, 16 Aug 2014 07:04:03 GMTstatus changed
https://trac.sagemath.org/ticket/16662#comment:43
https://trac.sagemath.org/ticket/16662#comment:43
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
</ul>
TicketvdelecroixSat, 16 Aug 2014 07:05:21 GMTreviewer set
https://trac.sagemath.org/ticket/16662#comment:44
https://trac.sagemath.org/ticket/16662#comment:44
<ul>
<li><strong>reviewer</strong>
set to <em>Vincent Delecroix</em>
</li>
</ul>
TicketvbraunSat, 16 Aug 2014 09:32:19 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/16662#comment:45
https://trac.sagemath.org/ticket/16662#comment:45
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>u/ncohen/16662</em> to <em>7a73e74549a080ac7ac139241521a871d667cd45</em>
</li>
</ul>
Ticket