Talk:Damm algorithm: Difference between revisions
→Unsatisfying: new section
m (corrected two misspellings.) |
(→Unsatisfying: new section) |
||
Line 5:
--[[User:Paddy3118|Paddy3118]] ([[User talk: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 {{math|''x'' ∗ ''y''}} in Damm's doctoral dissertation page 111 by rearranging the rows and changing the entries with the permutation {{math|1=''φ'' = (1 2 9 5 4 8 6 7 3)}} and defining {{math|1=''x'' ⋅ ''y'' = ''φ''<sup>''−1''</sup>(''φ''(''x'') ∗ ''y'')}}
The problems I have here are:
# What is that permutation? (What happens with a zero digit?)
# What is that {{math|*}} operator?
For example, let's say that {{math|*}} is a table lookup operation on the 10 by 10 table on page 11 of [http://archiv.ub.uni-marburg.de/diss/z2004/0516/pdf/dhmd.pdf Damm's thesis], with x as the column index and y as the row index:
<pre>┌─┬───────────────────┐
│*│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│
└─┴───────────────────┘</pre>
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, phi inv would use x as an index into the list 0 1 2 9 5 4 7 8 6 3 and {{math|1=''x'' ⋅ ''y'' = ''φ''<sup>''−1''</sup>(''φ''(''x'') ∗ ''y'')}} would give us this table:
<pre>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</pre>
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 {{math|1=''x'' ⋅ ''y'' = ''φ''<sup>''−1''</sup>(''φ''(''x'') ∗ ''y'')}}.
That's obviously not the table specified in the wikipedia page. And, if we reverse the definition of {{math|*}} (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.) --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 17:12, 26 February 2022 (UTC)
| |||