mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2019-11-15, 18:04   #45
SmartMersenne
 
Sep 2017

2·43 Posts
Default

Quote:
Originally Posted by bsquared View Post
Largest for me is now 925119207 but I have no other ideas for how to find larger values. I'm just throwing CPUs at it now.
Quote:
Originally Posted by bsquared View Post
Since the recent pseudo-hints I've looked more at matrix structure but discovered nothing useful. I'm tending to either immediately rediscover det=929587995 circulant latin squares or find nothing but singular matrices...
I thought you already found 925119207.
SmartMersenne is offline   Reply With Quote
Old 2019-11-15, 18:33   #46
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

23·419 Posts
Default

Quote:
Originally Posted by SmartMersenne View Post
I thought you already found 925119207.
That's my best pseudo-random matrix, yes. 929587995 is the determinant of the maximal circulant Latin square and re-finding it isn't valid for this challenge. What I meant was that when I started trying to generate matrices with structure (symmetric, etc.) then I tended to either find 929587995 or 0... i.e., not useful.
bsquared is offline   Reply With Quote
Old 2019-11-15, 19:49   #47
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2×3×7×137 Posts
Default

What is a good speed for calculating a 9x9 determinant? I believe I am currently taking around 5-7 microseconds. Is this reasonable or should I be putting effort into speeding this up?
henryzz is offline   Reply With Quote
Old 2019-11-15, 20:19   #48
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

23·419 Posts
Default

Quote:
Originally Posted by henryzz View Post
What is a good speed for calculating a 9x9 determinant? I believe I am currently taking around 5-7 microseconds. Is this reasonable or should I be putting effort into speeding this up?
On my machine MATLAB takes about 1.2 us per 9x9. My C code takes about half that. Depending a little on the differences between our computers, you seem to be in the right ballpark (same OOM).
bsquared is offline   Reply With Quote
Old 2019-11-15, 22:46   #49
yae9911
 
yae9911's Avatar
 
"Hugo"
Jul 2019
Germany

31 Posts
Default

To contribute something more substantial than "pseudo-hints": On my aged Windows computer one 9x9 determinant takes ~ 6.2e-7 s, using 8 byte floats and Gauss elimination from LAPACK running on one core with PARI checking ispseudoprime on a second core. I.e. 10^9 determinants in 10 minutes CPU. For comparison of machine speed: yafu-1.34 tune tells me:
Code:
SIQS on c100: ... 

elapsed time for ~10k relations of c100 = 54.6251 seconds.
extrapolated time for complete factorization = 8707.0082 seconds
... WIN64 -         Intel(R) Core(TM) i5-2400 CPU @ 3.10GHz
yae9911 is offline   Reply With Quote
Old 2019-11-16, 02:31   #50
Dieter
 
Oct 2017

32×11 Posts
Default

Quote:
Originally Posted by yae9911 View Post
To contribute something more substantial than "pseudo-hints": On my aged Windows computer one 9x9 determinant takes ~ 6.2e-7 s, using 8 byte floats and Gauss elimination from LAPACK running on one core with PARI checking ispseudoprime on a second core. I.e. 10^9 determinants in 10 minutes CPU. For comparison of machine speed: yafu-1.34 tune tells me:
Code:
SIQS on c100: ... 

elapsed time for ~10k relations of c100 = 54.6251 seconds.
extrapolated time for complete factorization = 8707.0082 seconds
... WIN64 -         Intel(R) Core(TM) i5-2400 CPU @ 3.10GHz
That‘s exactly my time. PC from 2012, Gauss elimination,, 8 Byte floats, 64-bit assembly, Linux.
Dieter is offline   Reply With Quote
Old 2019-11-17, 11:01   #51
yae9911
 
yae9911's Avatar
 
"Hugo"
Jul 2019
Germany

31 Posts
Default

Quote:
Originally Posted by bsquared View Post
That's my best pseudo-random matrix, yes. 929587995 is the determinant of the maximal circulant Latin square and re-finding it isn't valid for this challenge. What I meant was that when I started trying to generate matrices with structure (symmetric, etc.) then I tended to either find 929587995 or 0... i.e., not useful.
Among the examples of structured matrices with determinant value 929587995, were there also some that did not have the very special structure of Latin squares? That would be a justification for my somewhat strange-seeming formulation of the challenge question.
yae9911 is offline   Reply With Quote
Old 2019-11-17, 12:51   #52
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

230316 Posts
Default

You guys are quite good. I actually have no idea how to solve this, beside of "random" or "brute force". The "random" brings you quite fast close to 900M (in just few hours, or less then an hour, depending on your luck), but to advance more, you really need a "clever" way to "improve" the arrangement. By random I mean what I described in my first post, change two elements, and keep the matrix with the highest det, like in the code below (which can be launched with parameters 0 to 3, we played together for half a day, but gave up after being stuck for some long time without any progress. My "best score" is just barely under 900M. I will post the code, some of you may have enough patience, or a lot of more luck... (this is not easy, it is hard, you really need a lot of patience or a lot of luck, that is why I do not consider it spoiler, the code is just some shitty stuff that anybody could put together).

Code:
\\value to beat (loophole) = 923062279
ponder1911(initial=0)=
{
  my(m,x,l,c,d);
  if(initial==0,        \\start from det=0, fast growing for small values till about 500M
        m=[1, 2, 3, 4, 5, 6, 7, 8, 9;
           1, 2, 3, 4, 5, 6, 7, 8, 9;
           1, 2, 3, 4, 5, 6, 7, 8, 9;
           1, 2, 3, 4, 5, 6, 7, 8, 9;
           1, 2, 3, 4, 5, 6, 7, 8, 9;
           1, 2, 3, 4, 5, 6, 7, 8, 9;
           1, 2, 3, 4, 5, 6, 7, 8, 9;
           1, 2, 3, 4, 5, 6, 7, 8, 9;
           1, 2, 3, 4, 5, 6, 7, 8, 9],
  /*else*/
    if(initial==1,      \\det=215233605, but moving fast to over 700M
        m=[1, 2, 3, 4, 5, 6, 7, 8, 9;
           9, 1, 2, 3, 4, 5, 6, 7, 8;
           8, 9, 1, 2, 3, 4, 5, 6, 7;
           7, 8, 9, 1, 2, 3, 4, 5, 6;
           6, 7, 8, 9, 1, 2, 3, 4, 5;
           5, 6, 7, 8, 9, 1, 2, 3, 4;
           4, 5, 6, 7, 8, 9, 1, 2, 3;
           3, 4, 5, 6, 7, 8, 9, 1, 2;
           2, 3, 4, 5, 6, 7, 8, 9, 1],
    /*else*/
      if(initial==2,    \\det=215233605, difficult to move
        m=[1, 2, 3, 4, 5, 6, 7, 8, 9;
           2, 3, 4, 5, 6, 7, 8, 9, 1;
           3, 4, 5, 6, 7, 8, 9, 1, 2;
           4, 5, 6, 7, 8, 9, 1, 2, 3;
           5, 6, 7, 8, 9, 1, 2, 3, 4;
           6, 7, 8, 9, 1, 2, 3, 4, 5;
           7, 8, 9, 1, 2, 3, 4, 5, 6;
           8, 9, 1, 2, 3, 4, 5, 6, 7;
           9, 1, 2, 3, 4, 5, 6, 7, 8],
      /*else*/          \\det=929587995 this is the record for Latin squares, to beat to get two stars
        m=[1, 2, 4, 8, 6, 7, 5, 3, 9;
           9, 1, 2, 4, 8, 6, 7, 5, 3;
           3, 9, 1, 2, 4, 8, 6, 7, 5;
           5, 3, 9, 1, 2, 4, 8, 6, 7;
           7, 5, 3, 9, 1, 2, 4, 8, 6;
           6, 7, 5, 3, 9, 1, 2, 4, 8;
           8, 6, 7, 5, 3, 9, 1, 2, 4;
           4, 8, 6, 7, 5, 3, 9, 1, 2;
           2, 4, 8, 6, 7, 5, 3, 9, 1]
      )
    )
  );
  x=matdet(m);
  print(x";\n "m[1,]"\n "m[2,]"\n "m[3,]"\n "m[4,]"\n "m[5,]"\n "m[6,]"\n "m[7,]"\n "m[8,]"\n "m[9,]);
  while(1,
    l=random(9)+1;
    c=random(9)+1;
    d=m[l,c];
    m[l,c]=m[c,l];
    m[c,l]=d;
    d=matdet(m);
    if(d>x,
      x=d;
      print(x";\n "m[1,]"\n "m[2,]"\n "m[3,]"\n "m[4,]"\n "m[5,]"\n "m[6,]"\n "m[7,]"\n "m[8,]"\n "m[9,]),
    )
  );
}
LaurV is offline   Reply With Quote
Old 2019-11-17, 13:05   #53
SmartMersenne
 
Sep 2017

2×43 Posts
Default

Quote:
Originally Posted by LaurV View Post
... we played together for half a day, but gave up after being stuck for some long time without any progress
I have been running it on two laptops non-stop for more than a week with many different approaches and still no luck!
SmartMersenne is offline   Reply With Quote
Old 2019-11-17, 14:05   #54
yae9911
 
yae9911's Avatar
 
"Hugo"
Jul 2019
Germany

31 Posts
Default

I am really happy that you have a little fun with the problem. I can give you a simple tip on random exchanges of matrix entries: Instead of just greedily looking for improvements to the determinants, it's worth accepting also reductions of the determinant value at the beginning. The acceptance probability of moves in the "wrong" direction is governed by a decaying threshold similar to the cooling down of a melt in a furnace. One can embed this in a framework program that performs a temperature control. The keyword to look for is simulated annealing.


If implemented properly (not more than 5 lines of code ) it will give you a dramatic increase in search progress and much more fun than just watching the awful performance of pure random swaps.
yae9911 is offline   Reply With Quote
Old 2019-11-17, 14:07   #55
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·3·7·137 Posts
Default

I have also tried two random swaps(4 cells changing). This takes a lot of solutions a bit further but slows it down massively. Currently, my best is 917e6. I should probably only run the double swap if single swaps take it past a threshold.
henryzz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
November 2018 Batalov Puzzles 5 2018-12-03 13:31
November 2017 Batalov Puzzles 3 2017-12-08 14:55
November 2016 Xyzzy Puzzles 1 2016-12-06 16:41
November 2015 R. Gerbicz Puzzles 3 2015-12-01 17:48
November 2014 Xyzzy Puzzles 1 2014-12-02 17:40

All times are UTC. The time now is 14:36.

Fri Dec 4 14:36:17 UTC 2020 up 1 day, 10:47, 0 users, load averages: 2.31, 2.38, 2.14

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.