Talk:Damm algorithm

From Rosetta Code

task clarification of requirements

One needs to either:

  • Change the task description to require output (and for what), explicitly; or
  • Remove all the notices about missing output.

--Paddy3118 (talk) 19:22, 23 August 2018 (UTC)

Unsatisfying

Currently, the task does not document the algorithm itself -- it merely refers to the wikipedia page.

And, currently, the wikipedia page is unsatisfying -- it specifies the latin square table explicitly, which makes implementing the algorithm possible, but it states:

The following operation table will be used. It may be obtained from the totally anti-symmetric quasigroup xy in Damm's doctoral dissertation page 111 by rearranging the rows and changing the entries with the permutation φ = (1 2 9 5 4 8 6 7 3) and defining xy = φ−1(φ(x) ∗ y)

The problems I have here are:

  1. What is that permutation? (What happens with a zero digit?)
  2. What is that * operator?

For example, let's say that * is a table lookup operation on the 10 by 10 table on page 111 of Damm's thesis, with x as the column index and y as the row index:

┌─┬───────────────────┐
│*│0 1 2 3 4 5 6 7 8 9│
├─┼───────────────────┤
│0│0 1 2 3 4 5 6 7 8 9│
│1│2 3 4 0 6 7 1 8 9 7│
│2│3 0 5 9 2 4 8 6 7 1│
│3│6 5 8 4 1 7 9 0 2 3│
│4│1 7 3 8 9 0 5 4 6 2│
│5│9 4 6 2 8 1 7 3 5 0│
│6│5 8 1 6 7 2 3 9 0 4│
│7│4 6 7 5 3 9 0 2 1 8│
│8│7 2 9 1 0 8 4 5 3 6│
│9│8 9 0 7 6 3 2 1 4 6│
└─┴───────────────────┘

And, let's say that the permutation operation phi(x) uses x as an index into the list 0 1 2 9 5 4 8 6 7 3. Then, φ−1(x) would use x as an index into the list 0 1 2 9 5 4 7 8 6 3 (notice that three elements near the right hand of the list have been reordered) and xy = φ−1(φ(x) ∗ y) would give us this table:

0 1 2 9 5 4 7 8 6 3
2 9 5 0 7 8 1 6 3 8
9 0 4 3 2 5 6 7 8 1
6 3 0 8 7 9 2 1 5 7
3 5 7 2 6 1 8 9 4 0
1 8 9 6 3 0 4 5 7 2
8 2 3 1 0 6 5 4 9 7
4 6 1 7 8 2 9 3 0 5
5 7 8 4 9 3 0 2 1 6
7 4 6 5 1 8 3 0 2 9

Or, let's say that the permutation phi represents the cycles (0)(1 2 9 5 4 8 6 7 3). Then phi(x) would use x as an index into the list 0 2 9 1 8 4 7 3 6 5 and phi inv would use x as an index into the list 0 3 1 7 5 9 8 6 4 2 and we still don't get the result shown on the wikipedia page for xy = φ−1(φ(x) ∗ y).

That's obviously not the table specified in the wikipedia page. And, if we reverse the definition of * (where x is the row index and y is the column index) the result is even less satisfying.

It's not clear whether this indicates errors or omissions in the wikipedia page, but I think it's fair to say that the wikipedia page is unclear in its presentation of the concepts behind the algorithm. These are conceptually simple operations, it's great that they can be described in any of a variety of ways, but those descriptions should be complete and should be stated clearly enough that a reader who hasn't read a specific phd dissertation can understand them.

(Also, it would be better if we could adequately describe the algorithms for our tasks here on this site. I understand that we are sometimes rather incoherent here, but that's something we should strive to correct. I think if we had made the effort to do so, we would catch problems like references to murky descriptions.) --Rdm (talk) 17:12, 26 February 2022 (UTC)