mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2019-11-17, 14:37   #56
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

22·3·281 Posts
Default

You guys are making me feel better with your posts. I actually have a high of 916e6 with a poorer implementation of LaurV's concept (arrived at on my own, btw). Unfortunately, you're also encouraging me to take machines away from other projects.

Additional thoughts: I had already decided that there would be situations where swapping two elements could no longer increase the determinant, but my solution was (is currently) to start with an entirely new random matrix. Of course, the success still rests on pure luck at this point. . .

Last fiddled with by EdH on 2019-11-17 at 14:41 Reason: Add thoughts.
EdH is offline   Reply With Quote
Old 2019-11-17, 14:46   #57
SmartMersenne
 
Sep 2017

1248 Posts
Default

Quote:
Originally Posted by yae9911 View Post
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.
Been there, done that. And with lots of tuning over the last couple of days... still no result.
SmartMersenne is offline   Reply With Quote
Old 2019-11-17, 17:43   #58
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

3×641 Posts
Default

Quote:
Originally Posted by SmartMersenne View Post
Been there, done that. And with lots of tuning over the last couple of days... still no result.
Ditto. It takes much more than sacrificing the pawn (accepting few step backs) to even surpass the threshold in a few days with more than a dozen cores.

I have tried sacrificing-few/many-prawns thousands and thousands of runs with the best Latin-Square solution as well as my own highest solution and gave up on that approach. Back to random swaps with better progress than sacrificing the pawn.

Last fiddled with by a1call on 2019-11-17 at 17:56
a1call is offline   Reply With Quote
Old 2019-11-17, 18:03   #59
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

3×641 Posts
Default

I think one positive tip (as if I have progressed enough to give them out, which I haven't) is not to discard/reject negative determinants as not-high-enough. A detriment will change sign each time you swap a row or column.

Last fiddled with by a1call on 2019-11-17 at 18:04
a1call is offline   Reply With Quote
Old 2019-11-17, 18:04   #60
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

5×659 Posts
Default

Quote:
Originally Posted by yae9911 View Post
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.
I'll have to check on that, but I don't think so.

Best by my search procedure so far is now 925432245.
bsquared is offline   Reply With Quote
Old 2019-11-17, 18:28   #61
SmartMersenne
 
Sep 2017

22·3·7 Posts
Default

I guess this is not for me as it involves luck. I was never lucky. In a previous puzzle, I had to guess the last two digits due to precision, so I tried everything. I got it at 96th trial (out of possible 100).
SmartMersenne is offline   Reply With Quote
Old 2019-11-17, 20:43   #62
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

3×641 Posts
Default

In the continuing series of tips from someone who hasn't cracked the lower threshold:
* If I had the time I would rewrite the code to shuffle diagonal and parallel to diagonal sets of cells rather than just cells. The logic behind this is that swaging rows and columns does not create any new determinant trials and swapping cells would have wasted efforts equivalents to swapping rows and columns. Swapping diagonals and their parallels should be the most/more efficient brute force approach.

Last fiddled with by a1call on 2019-11-17 at 20:45
a1call is offline   Reply With Quote
Old 2019-11-17, 21:55   #63
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

1101001011002 Posts
Default

Darn it! I was prepared to call off the search due to total inactivity, which would have let me get back to other things. But, I found that the "total inactivity" was self-inflicted by my poor programming. Upon a small adjustment, I outdid my previous high with 919685927, on the initial test run. Now I guess I'll still let this run awhile. . .

Last fiddled with by EdH on 2019-11-17 at 21:58 Reason: I wanted to use a different word.
EdH is offline   Reply With Quote
Old 2019-11-18, 22:44   #64
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

329510 Posts
Default

For fun, since progress has pretty much stopped on the 9x9 problem, I thought I'd try to find maximal solutions on smaller problems (https://oeis.org/A301371). Happily, I've rediscovered both a(7) and a(8). a(7) took a couple minutes and a(8) a couple hours. But a(9) is not scaling the same :(
bsquared is offline   Reply With Quote
Old 2019-11-19, 07:57   #65
yae9911
 
yae9911's Avatar
 
"Hugo"
Jul 2019
Germany

111112 Posts
Default

If your program solves A301371(7) and A301371(8), you may also try A085000(7) and A085000(8). For both results, independent confirmations are desirable.
yae9911 is offline   Reply With Quote
Old 2019-11-20, 03:43   #66
uau
 
Jan 2017

79 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?
BTW calculating determinants for each candidate separately may not be optimal. If you calculate the inverse matrix, you can then for example calculate the effect of swapping any two entries for a much cheaper per-candidate-pair price. So at least if you test many candidate pairs before actually doing a swap, this can be a win despite the extra cost of the inverse.

Suppose you have a matrix A with determinant d and inverse matrix B. You consider swapping entries at position (r1, c1) and (r2, c2). v=A(r2,c2)-A(r1,c1). Let A' be the matrix with those entries swapped (add v to number at (r1,c1), subtract v from number at (r2,c2)).
Then det(A') = d * ( (1+v*B(c1,r1))*(1-v*(B(c2,r2)) + v*v*B(c2,r1)*B(c1,r2) )

You can derive this by considering the product of B and A'. The determinant of this product is 1/det(A) * det(A'). On the other hand, you can directly calculate the determinant cheaply, since only two rows/columns (depending on whether you multiply from right or left) change from the identity matrix result of A*B, and the remaining zeros of the identity matrix eliminate most determinant terms.
uau 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 06:51.

Thu Oct 22 06:51:11 UTC 2020 up 42 days, 4:02, 0 users, load averages: 1.37, 1.37, 1.35

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.