Opened 5 years ago
Closed 5 years ago
#19778 closed enhancement (fixed)
McFarland 1973 construction for difference sets
Reported by:  vdelecroix  Owned by:  

Priority:  major  Milestone:  sage7.1 
Component:  combinatorial designs  Keywords:  
Cc:  ncohen  Merged in:  
Authors:  Vincent Delecroix  Reviewers:  Nathann Cohen 
Report Upstream:  N/A  Work issues:  
Branch:  071779b (Commits)  Commit:  071779bd3a9afb31f4874b59cfeffa79624ebdbd 
Dependencies:  Stopgaps: 
Description (last modified by )
We implement McFarland 1973 construction that gives more difference sets (only for large lambda though).
Change History (40)
comment:1 Changed 5 years ago by
 Branch set to u/vdelecroix/19778
 Commit set to 14bdcab2ac7044d8554f37f084cf8c398dde02d6
 Status changed from new to needs_review
comment:2 Changed 5 years ago by
input sections would be nice. The docstring of mcfarland_1973_construction
is rather minimalistic.
You moved code around in difference_family
, and from the diff it is difficult to guess what and why. Could you be more verbose?
Nathann
comment:3 Changed 5 years ago by
 Status changed from needs_review to needs_work
comment:4 Changed 5 years ago by
 Commit changed from 14bdcab2ac7044d8554f37f084cf8c398dde02d6 to 8bd17be0e663eb02be619bf9e8feba5067e288f5
Branch pushed to git repo; I updated commit sha1. New commits:
8bd17be  Trac 19778: input blocks

comment:5 Changed 5 years ago by
 Status changed from needs_work to needs_review
Hello,
I moved the code around in difference_family
in order to have all constructions that does not need the factorisation of v
before. In other words
if does_construction1_work(v,k,l): .... elif does_construction2_work(v,k,l): ... else: v = factor(v) ...
Vincent
comment:6 followup: ↓ 7 Changed 5 years ago by
I'm not being passiveaggressive here, just asking the question: considering the following timings, do you think that we should care?
sage: %timeit [factor(i) for i in range(2,10000)] 10 loops, best of 3: 78.7 ms per loop sage: %timeit [designs.difference_family(i,3,existence=True) for i in range(10000)] 1 loops, best of 3: 1.58 s per loop
I don't know if another timing makes more sense. I merely tried the first I could think of.
Nathann
comment:7 in reply to: ↑ 6 ; followup: ↓ 8 Changed 5 years ago by
Replying to ncohen:
I'm not being passiveaggressive here, just asking the question: considering the following timings, do you think that we should care?
sage: %timeit [factor(i) for i in range(2,10000)] 10 loops, best of 3: 78.7 ms per loop sage: %timeit [designs.difference_family(i,3,existence=True) for i in range(10000)] 1 loops, best of 3: 1.58 s per loopI don't know if another timing makes more sense. I merely tried the first I could think of.
This is more about code organization rather than timings. The previous version of the code was
D = None ... # try some stuff if D is None: ... # try other stuff if D is None: ... # try another one
comment:8 in reply to: ↑ 7 Changed 5 years ago by
This is more about code organization rather than timings.
If we chose to not care about this call to 'factor', could we have something like that?
f = factor(v) if does_construction1_work(v,k,l): .... elif does_construction2_work(v,k,l): ... elif <tests involving f>: ... elif <tests involving f>: ... return False
comment:9 Changed 5 years ago by
Err: to make it clear: I did not mean that your changes should be reverted because the call to 'factor' was negligible. Quite the contrary > can we go even further?
comment:10 Changed 5 years ago by
 Commit changed from 8bd17be0e663eb02be619bf9e8feba5067e288f5 to b3dd88ae6ff747f6c67ca20948b58269dcac73cd
Branch pushed to git repo; I updated commit sha1. New commits:
b3dd88a  Trac 19778: code reorganization in difference_family

comment:11 Changed 5 years ago by
done. But there is still something annoying at the begining with the construction of the finite field K
.
comment:12 Changed 5 years ago by
Hello again,
I have been staring for a while at the parameters v,k,l, looking for a way to avoid the database. Now number theory really isn't my thing, but I wonder about that: shouldn't the gcd of 'v,l,m' be *very* close to q^s
? Actually, in the factorization of gcd(v,l,m)
into pi,si
, aren't we sure that q^s
is equal to the largest value of pi^si
.
Actually (please tell me if I am wrong) by developping k as a series I get that k=lambda+q^(2s)
, thus gcd(lambda,k)
is a power of q
greater than q^s
(because both k and l can be divided by q^s
).
I'm getting very convinced that q^s
is actually equal to gcd(lambda,k)
.
Well, what do you think? :/
Nathann
comment:13 Changed 5 years ago by
(all this, however, depends on whether I added the missing ')' where it belongs in the explicit formula for 'k' that you provide in mcfarland_1973_construction
)
comment:14 Changed 5 years ago by
Just noticed that I was an idiot. Instead of computing gcd, isn't g^s
equal to sqrt(kl)
? :P
comment:15 Changed 5 years ago by
Just another note: if one can obtain q^s
with sqrt(kl)
, then one can get the value of q
. It looks easy: k/l
is equal to (q^{s+1}1)/(q^s1)
. Thus we can compute kq^s/l
which is equal to q^{s+1}1
and so compute q^{s+1}
, which we can divide by q^s
to get q
.
comment:16 Changed 5 years ago by
 Commit changed from b3dd88ae6ff747f6c67ca20948b58269dcac73cd to 04c7acfd7ca984db36cb365bea8c760fa79ff6cf
Branch pushed to git repo; I updated commit sha1. New commits:
04c7acf  Trac 19778: get rid of mcfarland_1973_parameters

comment:17 Changed 5 years ago by
You are right. The only problem is actually to compute s
from qs
and q
... I used is_prime_power
twice and opened #19792 to implement a better solution.
Vincent
comment:18 Changed 5 years ago by
Input block.
comment:19 Changed 5 years ago by
 Commit changed from 04c7acfd7ca984db36cb365bea8c760fa79ff6cf to 8fe3844f0894a817e8a81f959dae5dfb384bc2ba
Branch pushed to git repo; I updated commit sha1. New commits:
8fe3844  Trac 19778: input block

comment:20 Changed 5 years ago by
Hello again,
I pushed a couple of modifications at public/19778
. [A typo here/a comment there], though I also added a couple of checks in a test, and multiplied by (q1) instead of using // (q1)
, just in case the integer division may make equal two values which should not be. I also used 'izip' in a loop somewhere: you are welcome to revert it if you do not like it, and to change the ticket's status when you are satisfied with the code.
Thanks for this addition! I will not get a look at the ticket above this one.
Nathann
comment:21 Changed 5 years ago by
 Commit changed from 8fe3844f0894a817e8a81f959dae5dfb384bc2ba to b5820405ad208f360e94252c4a72c46545802295
comment:22 Changed 5 years ago by
Thanks for your commits. This is fine for me. (I avoided to merge with the last beta).
comment:23 Changed 5 years ago by
 Reviewers set to Nathann Cohen
 Status changed from needs_review to positive_review
comment:24 Changed 5 years ago by
You are still in 6.x?
comment:26 Changed 5 years ago by
Do you have an idea of the conflicter?
comment:27 followup: ↓ 28 Changed 5 years ago by
Beta2 is out, and the "conflicter" is this f*******
"upper case" ticket #19789.
It seems that others are on the way, for Eulerian, Hamiltonian, Abelian, ...
People have time to waste.
Nathann
comment:28 in reply to: ↑ 27 ; followup: ↓ 29 Changed 5 years ago by
comment:29 in reply to: ↑ 28 ; followup: ↓ 30 Changed 5 years ago by
Other people might need to learn to spell, you know...
I have received complaints because my posts on sagedevel had a space before "!?;:", and that while it is the rule in french it is not so in english.
You and I are both right.
Nathann
comment:30 in reply to: ↑ 29 Changed 5 years ago by
Replying to ncohen:
Other people might need to learn to spell, you know...
I have received complaints because my posts on sagedevel had a space before "!?;:", and that while it is the rule in french it is not so in english.
You and I are both right.
depending on the language: e.g. "Def blah():" is wrong in Python...
comment:31 Changed 5 years ago by
 Branch changed from u/vdelecroix/19778 to public/19778beta2
 Commit changed from b5820405ad208f360e94252c4a72c46545802295 to e8bc5ca4e90242bb6404c87cd5bcc50c83e49a61
 Status changed from needs_work to needs_review
rebased...
comment:32 Changed 5 years ago by
AAAAAAAnd now by magic you have commits of ticket #19777 in this branch.
comment:33 Changed 5 years ago by
 Description modified (diff)
ohh, I swear I took clean (?) develop branch with 7.0.beta2...
comment:34 Changed 5 years ago by
OK, mea culpa, I have had these #19777 commits merged. However, I cannot seem to be able to rebase to get rid of them  even if I check out clean develop, get this public/19778beta2 branch, and try
git rebase develop i
, I see
pick 4d2c2f4 trac #19777: Three new SRGs and db update pick 93bd357 trac #19777: Convert the other 2intersection set pick 14bdcab Trac 19778: McFarland 1973 difference set construction pick 8bd17be Trac 19778: input blocks pick b3dd88a Trac 19778: code reorganization in difference_family pick 04c7acf Trac 19778: get rid of mcfarland_1973_parameters pick 8fe3844 Trac 19778: input block pick cf852fa trac #19778: Reviewer's commit pick b582040 trac #19778: DOI # Rebase 036455f..e8bc5ca onto 036455f ...
now I delete the top two lines (the 19777 commits) and proceed, and get
$ git rebase develop i error: could not apply 14bdcab... Trac 19778: McFarland 1973 difference set construction ...
which makes no freaking sense to me. Note that for some reason I don't even see my last commit from public/19778beta2 (commit e8bc5ca4... "it is now one Ring to rule them all") in this list, even though it is duly in the branch.
comment:35 Changed 5 years ago by
 Commit changed from e8bc5ca4e90242bb6404c87cd5bcc50c83e49a61 to 071779bd3a9afb31f4874b59cfeffa79624ebdbd
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
071779b  one Ring to...

comment:36 Changed 5 years ago by
OK, removed that 19777...
comment:37 Changed 5 years ago by
Are we good?
comment:38 Changed 5 years ago by
You can switch the status yourself I guess: Dima is the one who merged it.
Nathann
comment:39 Changed 5 years ago by
 Milestone changed from sage7.0 to sage7.1
 Status changed from needs_review to positive_review
comment:40 Changed 5 years ago by
 Branch changed from public/19778beta2 to 071779bd3a9afb31f4874b59cfeffa79624ebdbd
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
Trac 19778: McFarland 1973 difference set construction