902 Chapter 20.Less-Numerical Algorithms used for account numbers(including.e.g.,MasterCard).Here,the check equation is 2#d1+d2+2#dg+d4+·.·=0(mod10) (20.3.2) where 2#d means,"multiply d by two and add the resulting decimal digits."United States banks code checks with a 9-digit processing number whose check equation is 3a1+7a2+ag+3a4+7a5+a6+3a7+7a8+ag=0(mod10)(20.3.3) The bar code put on many envelopes by the U.S.Postal Service is decoded by removing the single tall marker bars at each end,and breaking the remaining bars into 6 or 10 groups of five.In each group the five bars signify (from left to right) the values 7,4,2,1,0.Exactly two of them will be tall.Their sum is the represented digit,except that zero is represented as 7+4.The 5-or 9-digit Zip Code is followed by a check digit,with the check equation ERICAL ∑d=0(mod10) (20.3.4) 令 None of these schemes is close to optimal.An elegant scheme due to Verhoeff is described in [71.The underlying idea is to use the ten-element dihedral group Ds, 尚、希 Press. which corresponds to the symmetries of a pentagon,instead of the cyclic group of the integers modulo 10.The check equation is a1*f(a2)*f2(a3)*..*fn-1(an)=0 (20.3.5) SCIENTIFIC where is(noncommutative)multiplication in D5,and fi denotes the ith iteration of a certain fixed permutation.Verhoeff"'s method finds all single errors in a string, 6 and all adjacent transpositions.It also finds about 95%of twin errors (aa-bb), jump transpositions(acb-bca),and jump twin errors (aca-bcb).Here is an implementation: int decchk(char string[],int n,char *ch) Decimal check digit computation or verification.Returns as ch a check digit for appending Fuurggoglrion Numerical Recipes 10621 to string[1..n],that is,for storing into string[n+1].In this mode,ignore the returned boolean (integer)value.If string[1..n]already ends with a check digit (string [n]),re- turns the function value true (1)if the check digit is valid,otherwise false(0).In this mode, 43106 ignore the returned value of ch.Note that string and ch contain ASCll characters corre- sponding to the digits 0-9,not byte values in that range.Other ASCll characters are allowed in string,and are ignored in calculating the check digit. (outside Software. char ci 1ntj,k=0,m=0; static1ntip[10][8]={0,1,5,8,9,4,2,7,1,5,8,9,4,2,7,0,2,7,0,1, 5,8,9,4,3,6,3,6,3,6,3,6,4,2,7,0,1,5,8,9,5,8,9,4,2,7,0,1,6,3 6,3,6,3,6,3,7,0,1,5,8,9,4,2,8,9,4,2,7,0,1,5,9,4,2,7,0,1,5,8); stat1c1nt1j[10][10]=[0,1,2,3,4,5,6,7,8,9,1,2,3,4,0,6,7,8,9,5, 2,3,4,0,1,7,8,9,5,6,3,4,0,1,2,8,9,5,6,7,4,0,1,2,3,9,5,6,7,8, 5,9,8,7,6,0,4,3,2,1,6,5,9,8,7,1,0,4,3,2,7,6,5,9,8,2,1,0,4,3 8,7,6,5,9,3,2,1,0,4,9,8,7,6,5,4,3,2,1,0] Group multiplication and permutation tables. for (j=0;j<n;j++){ Look at successive characters. c=stringlj」； 1f(c>=4822c<a57) Ignore everything except digits.902 Chapter 20. Less-Numerical Algorithms Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machine￾readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). used for account numbers (including, e.g., MasterCard). Here, the check equation is 2#d1 + d2 + 2#d3 + d4 + ··· = 0 (mod 10) (20.3.2) where 2#d means, “multiply d by two and add the resulting decimal digits.” United States banks code checks with a 9-digit processing number whose check equation is 3a1 + 7a2 + a3 + 3a4 + 7a5 + a6 + 3a7 + 7a8 + a9 = 0 (mod 10) (20.3.3) The bar code put on many envelopes by the U.S. Postal Service is decoded by removing the single tall marker bars at each end, and breaking the remaining bars into 6 or 10 groups of five. In each group the five bars signify (from left to right) the values 7,4,2,1,0. Exactly two of them will be tall. Their sum is the represented digit, except that zero is represented as 7+4. The 5- or 9-digit Zip Code is followed by a check digit, with the check equation
di = 0 (mod 10) (20.3.4) None of these schemes is close to optimal. An elegant scheme due to Verhoeff is described in [7]. The underlying idea is to use the ten-element dihedral group D 5, which corresponds to the symmetries of a pentagon, instead of the cyclic group of the integers modulo 10. The check equation is a1*f(a2)*f 2(a3)* ··· *f n−1(an)=0 (20.3.5) where * is (noncommutative) multiplication in D5, and f i denotes the ith iteration of a certain fixed permutation. Verhoeff’s method finds all single errors in a string, and all adjacent transpositions. It also finds about 95% of twin errors (aa → bb), jump transpositions (acb → bca), and jump twin errors (aca → bcb). Here is an implementation: int decchk(char string[], int n, char *ch) Decimal check digit computation or verification. Returns as ch a check digit for appending to string[1..n], that is, for storing into string[n+1]. In this mode, ignore the returned boolean (integer) value. If string[1..n] already ends with a check digit (string[n]), re￾turns the function value true (1) if the check digit is valid, otherwise false (0). In this mode, ignore the returned value of ch. Note that string and ch contain ASCII characters corre￾sponding to the digits 0-9, not byte values in that range. Other ASCII characters are allowed in string, and are ignored in calculating the check digit. { char c; int j,k=0,m=0; static int ip[10][8]={0,1,5,8,9,4,2,7,1,5, 8,9,4,2,7,0,2,7,0,1, 5,8,9,4,3,6,3,6,3,6, 3,6,4,2,7,0,1,5,8,9, 5,8,9,4,2,7,0,1,6,3, 6,3,6,3,6,3,7,0,1,5, 8,9,4,2,8,9,4,2,7,0, 1,5,9,4,2,7,0,1,5,8}; static int ij[10][10]={0,1,2,3,4,5,6,7,8,9, 1,2,3,4,0,6,7,8,9,5, 2,3,4,0,1,7,8,9,5,6, 3,4,0,1,2,8,9,5,6,7, 4,0,1,2,3,9,5,6,7,8, 5,9,8,7,6,0,4,3,2,1, 6,5,9,8,7,1,0,4,3,2, 7,6,5,9,8,2,1,0,4,3, 8,7,6,5,9,3,2,1,0,4, 9,8,7,6,5,4,3,2,1,0}; Group multiplication and permutation tables. for (j=0;j<n;j++) { Look at successive characters. c=string[j]; if (c >= 48 && c <= 57) Ignore everything except digits