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:
“It breedeth no small offence and scandal to see and consider upon the one part the curiosity and cost bestowed by all sorts of men upon their private houses; and on the other part the unclean and negligent order and spare keeping of the houses of prayer by permitting open decays and ruins of coverings of walls and windows, and by appointing unmeet and unseemly tables with foul cloths for the communion of the sacrament.”
—Elizabeth I (1533–1603)
“The evening falters. Couples in their coats
Are leaving gaps already, and the rest
Move tables closer.”
—Philip Larkin (1922–1986)
“Eddie Felson: Church of the Good Hustler.
Charlie: Looks more like a morgue to me. Those tables are the slabs they lay the stiffs on.
Eddie Felson: I’ll be alive when I get out, Charlie.”
—Sydney Carroll, U.S. screenwriter, and Robert Rossen. Eddie Felson (Paul Newman)