Coding done... halfway (in Off-topic)

Yeah, truly off topic, but I finally worked the logical bugs out of my program. To the uninitiated, a logical bug is not the "error" messages your compiler throws at you, but the program being "correct" but not doing what you want.

The program's a prune tree for finding Costas arrays, checking conditions on placing a candidate. Very esoteric topic and highly mathematical.

Basically, a Costas array is n dots placed on a n by n grid such that each row and column contains exactly one dot, and the distance between each pair of dots is distinct. So
X---
-X--
---X
--X-
is valid, but
X---
--X-
-X--
---X
is not since the "distance" from the dots in row 1-2 is the same as from row 3-4.

Finding them is a major pain in (wherever you hurt most). They have a mathematical construction using finite fields for prime powers and I think up to 5 less than them. Except, that is spotty coverage and they haven't proved the existence of Costas arrays of size 32 and 33 (the smallest holes).

Now, 32 sounds small, except ignoring the distance condition, then there are exactly the number of permutations of 32 points of candidates or 32! = 263130836933693530167218012160000000. Yes, it's horrendous.

Using a row and column mask that is to be evolved, but that's to be coded, and another field entirely (evolutionary computation).

And by the way, somehow people have come up with ways to use these arrays in sonar and radar. So stone-hard math, used in... the military?

That was after 10 hours and 3 resets. The evolutionary code is going to be a breeze after that...

W00t, all the coding done, now heading over to cluster and hurling code at it for the next ~2 weeks...

as funny as it sounds you actually got my mouth watering :p

What language are you writing in? Also, have you tested your program on small orders of N? For instance, you should be able to brute force N=15 in about 1 second on any modern computer.

Yes, and the plan here is, since doing it for n=32 straight is going to... kill, I'm going a different route.

The ordinary prune tree would search each column from left to right and each row top to bottom (well, the simplest coding). I'm putting a row mask and column mask to change the order presented to the tree. Obviously that can change what limbs are chopped off, and having bigger limbs chopped off earlier helps with it.

So now, I can't make up a "perfect" mask without already solving the problem, so I'm using the evolutionary algorithm on the masks to minimize time-to-solution, for small n.

Then a prayer to the god of scaling, and test that solution for progressively higher n. The contents of the prayer, is, of course that there will be some sort of useful pattern that emerges out of that mess, that still works in higher n.

That problem is notorious for NOT scaling though, and my eh, supervisor, who is I think the 2nd out of 5 people in the world working on that problem, has all these earlier difficulty estimates (he's working on a classification of problems). And there are enormous jumps at n=12, 20 and so on. By enormous I mean above and beyond the expected factorial difficulty.

So, code's running and I already see bugs. That can't have been exposed by running dummy tests. The very evolved ones have a time-to-exhaustion of the entire search space (n^n) of... 1's and 2's. Probably sent the wrong data back after evaluation.

And interestingly, the data required for the masks is (n!)^(n+1), even more than the n! for the original problem. Another case of let's make the problem harder and backsolve into even harder versions of the original problem.

Ah, straight C code. The fastest (and I don't write assembly). FORTRAN doesn't have all these pointy things, and I need them for hand-optimization.

I can brute force 20 on the identity mask (= no mask) by a couple of minutes.

If ya don't mind me asking, what is all this for? :P

Kicks, fun, a final project, and a 3% shot at a paper?

Weirdest error I have seen to date: if I *slow* down the program by adding useless sleep()s, the answer is correct. If I don't, then the program runs in about a millisecond (which is wrong, since my 2.0G runs it for 10 seconds, and those Itaniums are 1.6G), and all the counts are <10.

Don't drink and drive, boys. I guess the sleeps stop the somehow-rampant parallelization? Problem is, that evaluation is not only not embarrassingly parallel, it's completely serial. Well almost, you can spread along limbs and come back.

Cool, 5 years of playing CB and I've found myself confused when reading quite a few threads. This one takes the biscuit !

Can anyone tell me if this guy is breaking PG rules and needs a fine? I have no idea what the hell he's talking about...

I'm with Levon, totally drooling.

From the initial look, it looks like this can be done in the order of O(n). Interesting problem though. I'll have to think it over.

"Weirdest error I have seen to date: if I *slow* down the program by adding useless sleep()s, the answer is correct."

I ran across similar issues a good number of times during my programming career. Those are hardest one to figure out, the reason is never the same, and the problem is sometimes completely un-related to the code itself.

Good luck.

Ah, but the permutation matrix condition makes it at least n! even when injecting that knowledge, and you have n(n-1)/2 extra binary exclusions (that overlap excessively). Finding one is at most O(n!)>O(e^n) by exhaustive trying. Prune tree search goes for the full n^n space, but chopping off limbs should make it somewhere near exponential, hopefully less.

G_Beee: chill and listen to codemonkey or similar :), and ignorance is totally work-safe.

And icc is to blame, waste of money eh? gcc works fine, so I'll have to skip Intel's cool optimizations I guess. -O3 for the win. And it's not the optimizations on icc, just left in -lpthread (since I parallelize), and still shot.

Ah, found the finite field construction.

Take (Zp*, *), the group of nonzero integers modulo prime p under multiplication. If g is a primitive root over Zp*, then the permutation {g^i}_i=1^p-1 is a Costas array.

g is primitive iff g^p = 1 and g^k != 1 for all k < p.

Note that this construction always puts a point at the lower-right corner, since by definition g^p = 1, so removing that point makes a Costas array of order p-2.

Et cetera, forgot the p-3 construction.

Somebody give me a crash course math and programming...
This sounds familiar, but it's going so out of my league...
If only I was still a student, this would have made alot more sense.

GB, I say ban him just to be safe ;P

I think he's communicating with his multi counterpart in a form we cannot hope to understand.

Burn the multi!

;P

Preliminary results~ W00t!

n / best-found length-to-complete-traversal
5:43
6:60
7:90
8:110
9:141
10:167
11:192
12:214
13:260
14:317
15:371

Evolved using population size 20, inverse number of moves-proportional selection and replacement with stillborn-able children, no crossover, n-point mutation for size n arrays, 1 million generations.

If anything, these numbers look... linear to me. Intercept goes somewhere ~3, but that's where there's even any meaning to the arrays.

what is the definition of distance for this exercise? in the top diagram, the length between the first 2 dots and last 2 is the game, except on a different direction.

Take them as vectors, so for:

X000
00X0
0X00
000X

so the difference for 1st and 2nd row is considered different from the 1st and 3rd. However 1st and 2nd row difference is exactly equal to that from the 3rd and 4th row, so that's not a Costas array.

i.e. (1,2) is different from (2,1).

Results back for n=16, 2 runs, 413 and 417: still linear to me.

can I be your friend?

Shure, go ahead :)

And another run for size 16: 399. No ascending slope, not exponential.

17: 450
18: 516 - from 18^18 = 39346408075296537575424

slope's higher, but not even

seems like fun if that's what you're in to ^_^
I'm sufficient enough to "code" a html link. :P But this seems like a lot of stuff... what kind of computer are you using that can handle such a task?

It's an ALTIX350 cluster.

 **********************************************************************
 *                        _      ___                                  *
 *                       / \  |   |  | \/                             *
 *                      /---\ |_  |  | /\                             *
 *                                                                    *
 *       Welcome to the SGI Altix 350 at the U of Guelph              *
 *                                                                    *
 *                                                                    *
 **********************************************************************
 ***
         This is an SGI Altix 350 system which consists of:
          32 Itanium2 Processors with clock speed 1.6GHz 
              Main memory size: 64 GB  Cache Size: 9 MB
                 SuSE Linux Enterprise Server 9 
                      Kernel 2.6.5-7.286-rtgfx
                         SGI Propack 4 SP3

 Type "helpme | more" for usage instructions ...
 ======================================================================
 **** NOTE: BACKUPS ARE RUN NIGHTLY AND KEPT FOR ONE WEEK ONLY! ****
 ======================================================================

1+1= 2 I am with you BGGG