1000 0001 0010 0010 1000 0001 0010 1000 1000 0100 0001 0100 0001 0010 0100 0001 0100 1000 0100 0100 0001 1000 0010 0010 0100 0100 1000 0001 0100 0010 0010 0001 0100 0010 1000 0001 1000 0010 0001 1000 0010 0100 0001 1000 0010 0100 0001 1000So why would one care about Costas arrays? Because of the asymmetries imposed by the two constraints, Costas arrays make ideal waveforms for certain sensor applications, reducing ambiguity in interpreting radar and sonar returns. The mathematics are interesting in other ways. For example, according to the CRC Standard Mathematical Tables, the number C(n) of Costas arrays of order n increases as a function of n until n==16, after which it decreases, at least until n==23:
n |
C(n) |
n |
C(n) |
1 |
1 |
2 |
2 |
3 |
4 |
4 |
12 |
5 |
40 |
6 |
116 |
7 |
200 |
8 |
444 |
9 |
760 |
10 |
2160 |
11 |
4368 |
12 |
7852 |
13 |
12828 |
14 |
17252 |
15 |
19612 |
16 |
21104 |
17 |
18276 |
18 |
15096 |
19 |
10240 |
20 |
6464 |
21 |
3536 |
22 |
2052 |
23 |
872 |
24 |
>=1 |
#if defined(__cplusplus) extern "C" { #endif long /* number of arrays */ EnumerateCostas( int n, /* enumerate Costas arrays of order n */ long *costasArrays /* preallocated storage for returning your results */ /* row r of array k is in costasArrays[k*n + r], r,k are origin 0 */ ); #if defined(__cplusplus) } #endifYour EnumerateCostas routine will be asked to enumerate all Costas arrays of order n and return the results in the preallocated costasArrays. Each cell of an array is represented by one bit. The bits for row r of the k-th Costas array are to be returned in costasArrays[k*n + r], r=0..n-1, k>=0. The cell representing column c, c=0..n-1, is the bit in 1<<c. EnumerateCostas must produce all valid Costas arrays, with no duplicates, and return the number of arrays produced. The winner will be the solution that correctly enumerates the Costas arrays in the minimum time. This will be a native PowerPC Challenge, using the latest CodeWarrior environment. Solutions may be coded in C, C++, Pascal, or Java.
Test code for this Challenge is available.
You can get a head start on the Challenge by reading the Programmer's Challenge mailing list. It will be posted to the list on or before the 12th of the preceding month. To join, send an email to listserv@listmail.xplain.com with the subject "subscribe challenge-A". You can also join the discussion list by sending a message with the subject "subscribe challenge-D".