Tables
The Verhoeff algorithm can be implemented using three tables: a multiplication table d, a permutation table p, and an inverse table inv.
The first table, d, is based on multiplication in the dihedral group D5.
| d(j,k) | k | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ||
| j | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 1 | 1 | 2 | 3 | 4 | 0 | 6 | 7 | 8 | 9 | 5 | |
| 2 | 2 | 3 | 4 | 0 | 1 | 7 | 8 | 9 | 5 | 6 | |
| 3 | 3 | 4 | 0 | 1 | 2 | 8 | 9 | 5 | 6 | 7 | |
| 4 | 4 | 0 | 1 | 2 | 3 | 9 | 5 | 6 | 7 | 8 | |
| 5 | 5 | 9 | 8 | 7 | 6 | 0 | 4 | 3 | 2 | 1 | |
| 6 | 6 | 5 | 9 | 8 | 7 | 1 | 0 | 4 | 3 | 2 | |
| 7 | 7 | 6 | 5 | 9 | 8 | 2 | 1 | 0 | 4 | 3 | |
| 8 | 8 | 7 | 6 | 5 | 9 | 3 | 2 | 1 | 0 | 4 | |
| 9 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | |
The second table, p, applies a permutation to each digit based on its position in the number. The positions of the digits are counted from right to left, starting with zero. The permutation repeats after eight rows (the row for pos=8 is identical to the row for pos=0, etc.). Storage space can be reduced using the fact that this is actually a single permutation (1 5 8 9 4 2 7 0)(3 6) applied iteratively; i.e. p(i+j,n) = p(i, p(j,n)).
| p(pos,num) | num | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ||
| pos (mod 8) |
0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 1 | 1 | 5 | 7 | 6 | 2 | 8 | 3 | 0 | 9 | 4 | |
| 2 | 5 | 8 | 0 | 3 | 7 | 9 | 6 | 1 | 4 | 2 | |
| 3 | 8 | 9 | 1 | 6 | 0 | 4 | 3 | 5 | 2 | 7 | |
| 4 | 9 | 4 | 5 | 3 | 1 | 2 | 6 | 8 | 7 | 0 | |
| 5 | 4 | 2 | 8 | 6 | 5 | 7 | 3 | 9 | 0 | 1 | |
| 6 | 2 | 7 | 9 | 3 | 8 | 0 | 6 | 4 | 1 | 5 | |
| 7 | 7 | 0 | 4 | 6 | 9 | 1 | 3 | 2 | 5 | 8 | |
The third table, inv, represents the multiplicative inverse of a digit in the dihedral group D5: in other words, for any j, the inv table shows the value k such that d(j,k) = 0.
| j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| inv(j) | 0 | 4 | 3 | 2 | 1 | 5 | 6 | 7 | 8 | 9 |
Read more about this topic: Verhoeff Algorithm
Famous quotes containing the word tables:
“The evening falters. Couples in their coats
Are leaving gaps already, and the rest
Move tables closer.”
—Philip Larkin (1922–1986)
“Hast thou named all the birds without a gun?
Loved the wood rose, and left it on its stalk?
At rich men’s tables eaten bread and pulse?
Unarmed, faced danger with a heart of trust?”
—Ralph Waldo Emerson (1803–1882)
“The word unto the prophet spoken
Was writ on tables yet unbroken;
The word by seers or sibyls told,
In groves of oak, or fanes of gold,
Still floats upon the morning wind,
Still whispers to the willing mind.”
—Ralph Waldo Emerson (1803–1882)