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: sage-7.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 dimpase)

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 vdelecroix

  • Branch set to u/vdelecroix/19778
  • Commit set to 14bdcab2ac7044d8554f37f084cf8c398dde02d6
  • Status changed from new to needs_review

New commits:

14bdcabTrac 19778: McFarland 1973 difference set construction

comment:2 Changed 5 years ago by ncohen

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 ncohen

  • Status changed from needs_review to needs_work

comment:4 Changed 5 years ago by git

  • Commit changed from 14bdcab2ac7044d8554f37f084cf8c398dde02d6 to 8bd17be0e663eb02be619bf9e8feba5067e288f5

Branch pushed to git repo; I updated commit sha1. New commits:

8bd17beTrac 19778: input blocks

comment:5 Changed 5 years ago by vdelecroix

  • 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 follow-up: Changed 5 years ago by ncohen

I'm not being passive-aggressive 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 ; follow-up: Changed 5 years ago by vdelecroix

Replying to ncohen:

I'm not being passive-aggressive 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.

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 ncohen

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 ncohen

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 git

  • Commit changed from 8bd17be0e663eb02be619bf9e8feba5067e288f5 to b3dd88ae6ff747f6c67ca20948b58269dcac73cd

Branch pushed to git repo; I updated commit sha1. New commits:

b3dd88aTrac 19778: code reorganization in difference_family

comment:11 Changed 5 years ago by vdelecroix

done. But there is still something annoying at the begining with the construction of the finite field K.

Last edited 5 years ago by vdelecroix (previous) (diff)

comment:12 Changed 5 years ago by ncohen

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 ncohen

(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 ncohen

Just noticed that I was an idiot. Instead of computing gcd, isn't g^s equal to sqrt(k-l)? :-P

comment:15 Changed 5 years ago by ncohen

Just another note: if one can obtain q^s with sqrt(k-l), then one can get the value of q. It looks easy: k/l is equal to (q^{s+1}-1)/(q^s-1). 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 git

  • Commit changed from b3dd88ae6ff747f6c67ca20948b58269dcac73cd to 04c7acfd7ca984db36cb365bea8c760fa79ff6cf

Branch pushed to git repo; I updated commit sha1. New commits:

04c7acfTrac 19778: get rid of mcfarland_1973_parameters

comment:17 Changed 5 years ago by vdelecroix

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 ncohen

Input block.

comment:19 Changed 5 years ago by git

  • Commit changed from 04c7acfd7ca984db36cb365bea8c760fa79ff6cf to 8fe3844f0894a817e8a81f959dae5dfb384bc2ba

Branch pushed to git repo; I updated commit sha1. New commits:

8fe3844Trac 19778: input block

comment:20 Changed 5 years ago by ncohen

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 (q-1) instead of using // (q-1), 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 git

  • Commit changed from 8fe3844f0894a817e8a81f959dae5dfb384bc2ba to b5820405ad208f360e94252c4a72c46545802295

Branch pushed to git repo; I updated commit sha1. New commits:

cf852fatrac #19778: Reviewer's commit
b582040trac #19778: DOI

comment:22 Changed 5 years ago by vdelecroix

Thanks for your commits. This is fine for me. (I avoided to merge with the last beta).

comment:23 Changed 5 years ago by vdelecroix

  • Reviewers set to Nathann Cohen
  • Status changed from needs_review to positive_review

comment:24 Changed 5 years ago by ncohen

You are still in 6.x?

comment:25 Changed 5 years ago by vbraun

  • Status changed from positive_review to needs_work

merge conflict

comment:26 Changed 5 years ago by vdelecroix

Do you have an idea of the conflicter?

comment:27 follow-up: Changed 5 years ago by ncohen

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

Last edited 5 years ago by ncohen (previous) (diff)

comment:28 in reply to: ↑ 27 ; follow-up: Changed 5 years ago by dimpase

Replying to ncohen:

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.

Other people might need to learn to spell, you know...

comment:29 in reply to: ↑ 28 ; follow-up: Changed 5 years ago by ncohen

Other people might need to learn to spell, you know...

I have received complaints because my posts on sage-devel 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 dimpase

Replying to ncohen:

Other people might need to learn to spell, you know...

I have received complaints because my posts on sage-devel 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 dimpase

  • 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 ncohen

AAAAAAAnd now by magic you have commits of ticket #19777 in this branch.

comment:33 Changed 5 years ago by dimpase

  • Description modified (diff)

ohh, I swear I took clean (?) develop branch with 7.0.beta2...

comment:34 Changed 5 years ago by dimpase

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 2-intersection 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 git

  • Commit changed from e8bc5ca4e90242bb6404c87cd5bcc50c83e49a61 to 071779bd3a9afb31f4874b59cfeffa79624ebdbd

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

071779bone Ring to...

comment:36 Changed 5 years ago by dimpase

OK, removed that 19777...

comment:37 Changed 5 years ago by vdelecroix

Are we good?

comment:38 Changed 5 years ago by ncohen

You can switch the status yourself I guess: Dima is the one who merged it.

Nathann

comment:39 Changed 5 years ago by vdelecroix

  • Milestone changed from sage-7.0 to sage-7.1
  • Status changed from needs_review to positive_review

comment:40 Changed 5 years ago by vbraun

  • Branch changed from public/19778beta2 to 071779bd3a9afb31f4874b59cfeffa79624ebdbd
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.