This web page is devoted to my fortran programs for finding difference triangle sets by backtrack search. I also have programs dealing with Golomb rulers. Free fortran compilers for IBM PCs are available on the web.

- dts2
- Dts2 does an exhaustive backtrack search for difference triangle sets. It is based on the Golomb ruler exhaustive search program grs2. Dts2 usage instructions.
- dts2x
- Dts2x is a modified version of dts2 for use when a complete search would take too long. It allows the user to partition a complete search into numerous independent partial searches. Dts2x usage instructions.
- dtsver
- Dtsver independently verifies difference triangle sets found by above programs are correct. For usage see the instructions for dts2 or dts2x.

Dts2 reads input variables n, k, nt (3i5 format) from the terminal (unit 5).

- n is the number of marks per ruler
- k is the maximum length allowed
- nt is the number of rulers

For example to find all golomb rulers with 13 marks and length 106 or less enter

13 106 1After a while dts2 will find a ruler

0 7 8 17 21 36 47 63 69 81 101 104 106and then a bit later complete the search

n= 13 k= 106 solutions= 1 time= 19.57 nodes= 49441242.This may take a few hundred seconds on a slow machine. The program can now be terminated by entering

0At this point disk unit 1 should contain the following

13 106 1 0 7 8 17 21 36 47 63 69 81 101 104 106 0 0If dtsver is now run it will read unit 1 and verify that this is a difference triangle set. It will write to the terminal (unit 6).

13 106 1 0 0 0 1 difference triangle sets verified

Dts2x reads input variables n, k, nt, nprune (4i5 format) from the terminal (unit 5).

- n is the number of marks per ruler
- k is the maximum ruler length allowed
- nt is the number of rulers
- nprune is the number of levels at which the search tree is pruned

- ipos is the level being pruned
- ikeep is the pruning factor, keep every ikeep'th node
- nstart determines which modulo class of nodes to keep

For example to do a partial search for golomb rulers with 13 marks and length 106 in which we do not extend half the nodes at level 3 of the search tree or half the remaining nodes at level 4 enter

13 106 1 2Then enter

3 2 1 4 2 0After a while dts2x will find a ruler (we chose the appropriate modulo classes).

0 7 8 17 21 36 47 63 69 81 101 104 106and then a bit later complete the search

n= 13 k= 106 solutions= 1 time= 5.25 nodes= 12669479. 106 0. 38. 866. 6829. 35521. 204292. 492119. 1916285. 5206931. 4234111. 571267. 1218. 2.Note the output is bit different from that of dts2. The last number in the first line (here 106) is the best (shortest) difference triangle set found. Dts2x also outputs (lines 2-4 above) the number of nodes visited on each level (1-13) of the search. The total number of nodes visited is about 1/4 that for dts2 and the search should finish in about 1/4 the time. The program can now be terminated by entering

0At this point disk unit 1 should contain the following

13 106 1 0 7 8 17 21 36 47 63 69 81 101 104 106 0 0and disk unit 2 should contain the following

13 106 1 2 3 2 1 4 2 0 n= 13 k= 106 solutions= 1 time= 5.25 nodes= 12669479. 106 0. 38. 866. 6829. 35521. 204292. 492119. 1916285. 5206931. 4234111. 571267. 1218. 2.consisting of a copy of the input data and the search summary. If dtsver is now run it will read unit 1 and verify that this is a difference triangle set. It will write to the terminal (unit 6).

13 106 1 0 0 0 1 difference triangle sets verified

**
[
IBM Research home page |
James B. Shearer's home page |
Up
]
[
IBM home page |
Order |
Search |
Contact IBM |
Legal
]
**