Errata and remarks for the fxtbook ("Matters Computational", first edition): Last change: 2023-December-31 (09:24) ------------------------------------------------------------ Page 4 (section 1.1.5): The function first_comb() should better be defined as follows. static inline ulong first_comb(ulong k) { if ( k==0 ) return 0; // shift with BITS_PER_LONG is undefined return ~0UL >> ( BITS_PER_LONG - k ); } This avoids undefined behaviour with the shift operation. [Reported by Xavier Combelle, 2016-November-21] ------------------------------------------------------------ Page 5 (section 1.1.7): Renamed average() into floor_average(). See file fxt/src/bits/average.h where assembler version for floor_average() and ceil_average() are now given. [Reported by Stefan Kanthak, 2019-March-03] ------------------------------------------------------------ Page 10 (section 1.3.3): The function lowest_block() as given does not preserve the highest bit of the block if it is the highest bit of the argument x. The following code fixes this: static inline ulong lowest_block(ulong x) { ulong l = x & -x; // lowest bit ulong y = x + l; y ^= x; return y & x; } The last two lines of code have been changed. [Reported by Mike Engber, 20-October-2010] ------------------------------------------------------------ Page 14 (section 1.5.2): The comment // multiplication by a power of 2 is a shift on line 4 of the function db_lowest_one_idx(ulong x) shall not indicate that the compiler emits just a shift. ------------------------------------------------------------ Page 18 (section 1.7): For arguments 0 and 1 (either order) ld_eq(x,y) correctly returns false whereas ld(x) == ld(y) gives true (because ld(x) returns 0 for both x==1 and x==0). ------------------------------------------------------------ Page 21 (section 1.8.2): Change the single line in function bit_block_ge2_count() to return bit_block_count( ( x & (x<<1)) | ( x & (x>>1)) ); [Reported by Tomohito Urushibara, 2023-December-24] ------------------------------------------------------------ Page 25 (section 1.11): Replace "The obvious code to test whether a point $(x,y)$ lies outside a square box of size $m$ is if ( (x<0) || (x>m) || (y<0) || (y>m) ) { ... }" by "The obvious code to test whether a point $(x,y)$ lies outside a square with both coordinates less than $m$ is if ( (x<0) || (x>=m) || (y<0) || (y>=m) ) { ... }" [Reported by Daniel Eckert, 2015-June-06] ------------------------------------------------------------ Page 46 (section 1.16.6): Replace "Then $E$ preserves the lowest bit of $X$, while $E$ preserves the highest." by "Then $E$ preserves the lowest bit of $X$, while $G$ preserves the highest." Replace "Also $E$ preserves the lowest \emph{set} bit of $X$, while $E$ preserves the highest." by "Also $E$ preserves the lowest \emph{set} bit of $X$, while $G$ preserves the highest." [Reported by Etienne Lorrain, 2016-August-02] ------------------------------------------------------------ Page 58 (section 1.22): Code for the conversion from and to the complex base (-1+i) has been added to the FXT library, (fxt/src/bits/radix-m1pi.h), the corresponding demo programs are fxt/demo/bits/radix-m1pi-demo.cc and fxt/demo/bits/radix-m1pi-to-z-demo.cc The routines use conversion from and to radix (-4), see fxt/src/bits/radix-m4.h and fxt/demo/bits/radix-m4-demo.cc Code for the conversion from and to the complex base (2*i) (the quarter-imaginary base) has been added to the FXT library, see fxt/src/bits/radix-2i.h, the corresponding demo programs are fxt/demo/bits/radix-2i-demo.cc and fxt/demo/bits/radix-2i-to-z-demo.cc ------------------------------------------------------------ Page 83 (section 1.31.1): An algorithm for the generation of n-dimensional Hilbert curves, given by Fred Lunnon, is implemented in the class in fxt/src/comb/hilbert-ndim.h The corresponding program showing usage of the class is fxt/demo/comb/hilbert-ndim-demo.cc ------------------------------------------------------------ Page 95 (section 1.31.5): For curves of this type see "Plane-filling curves on all uniform grids" http://arxiv.org/abs/1607.02433 and "Edge-covering plane-filling curves on grid colorings" https://arxiv.org/abs/2312.00654 ------------------------------------------------------------ Page 106 (section 2.3.1): The code for inverting a permutation without an extra bit-array is given in the program fxt/demo/perm/perm-invert-notag-demo.cc ------------------------------------------------------------ Page 124 (section 2.9): In the procedures rotate_left() and rotate_right(), replace the code before the calls to reverse() by if ( n<=1 ) return; // nothing to do if ( s>=n ) s %= n; if ( s==0 ) return; // nothing to do ------------------------------------------------------------ Page 141 (section 3.1.5): heap_sort_descending() was plain wrong. Replace by template void heap_sort_descending(Type *x, ulong n) // Sort x[] into descending order. { heap_sort( x, n ); reverse( x, n ); } [reported by Pedro Pereira, 2019-September-04] ------------------------------------------------------------ Page 152 (section 3.5.3): The first sentence should read "They can be computed ..." (the letter y is missing in the first word). ------------------------------------------------------------ Page 152 (section 4.1): At the end of the comment for the method ulong pop(Type &z) replace "is undefined" by "undefined". ------------------------------------------------------------ Page 165 (section 4.6): In code line 10, near top of page, the comment // (ones are at the positions of the _unused_ bits) should be // (ones are at the positions of the used bits) ------------------------------------------------------------ Page 166 (section 4.6): In the last sentence just before section 4.7 replace "out of bounds" by "out of bound accesses". ------------------------------------------------------------ Page 176 (section 6.1): Code for the binomial coefficients more carefully guarded against overflow is available at https://gist.github.com/jlaire/be48c44c59770051e467 [Reported by Johannes Laire, 21 Oct 2015] ------------------------------------------------------------ Page 197 (section 7.2): In the method next() replace if ( j==k_ ) return k_; // current composition is last by if ( j >= k_ - 1 ) return k_; // current composition is last (otherwise the sentinel is changed with the final call to next() which however does usually not matter). ------------------------------------------------------------ Page 212 (section 8.5.3): Renamed class ksubset_twoclose to ksubset_twoclose_rec and corresponding file to ksubset-twoclose-rec.h ------------------------------------------------------------ Page 217 (section 9.1): Renamed class mixedradix_lex to class mixedradix and corresponding file to mixedradix.h ------------------------------------------------------------ Page 224ff (section 9.3) See "Subset-lex: did we miss an order" https://arxiv.org/abs/1405.6503 for a more natural variant of the "gslex" order. ------------------------------------------------------------ Page 229 (section 9.6): Class mixedradix_sod_lex renamed to mixedradix_fixed_content, file mixedradix-sod-lex.h renamed to mixedradix-fixed-content.h See also new file mixedradix-fixed-content-lex.h ------------------------------------------------------------ Page 243 (section 11.3): A generator for permutations in lexicographic order that also computes the inverse permutations is given in fxt/src/comb/perm-lex-inv.h The corresponding demo program is fxt/demo/comb/perm-lex-inv-demo.cc ------------------------------------------------------------ Page 273 (section 10.12): In the list on top of the page, replace j%1 by j%2 (twice). ------------------------------------------------------------ Page 278 (section 11.1.3): File perm-restrpref.h renamed to perm1-prefix-cond-demo.cc. ------------------------------------------------------------ Page 287 (section 11.4.2): Class cyclic_perm renamed to cyclic_perm_gray, corresponding file is cyclic-perm-gray.h ------------------------------------------------------------ Page 295 (section 13.1): The demo program fxt/demo/comb/mset-ksubset-demo.cc for the generation of k-subsets of a multiset has been added to the FXT library. ------------------------------------------------------------ Page 295 (section 13.2): In the last sentence on this page ("Relation 13.2-1a is obtained ...") insert a comma after the first occurrence of the word "elements". ------------------------------------------------------------ Page 301 (section 13.2.4): A permutation generator using only prefix shifts (specialization of the multiset permutations in cool-lex order) has been added to the FXT library (fxt/src/comb/perm-pref.h), the corresponding demo program is fxt/demo/comb/perm-pref-demo.cc ------------------------------------------------------------ Page 304 (chapter 14): typo: "successsive" --> "successive" (top of page) ------------------------------------------------------------ Page 310 (section 14.4): In "We call the RLL words starting with zero as RLL(r) words." drop the word "as". ------------------------------------------------------------ Page 314 (section 14.6.2): Equation (14.6-2) needs to be p_r(n) = r * p_r(n-1) + p_r(n-2) ------------------------------------------------------------ Page 317 (section 14.8): In equation (14.8-1) all expressions on the left but the first need to have argument n-2 (not n-1 as given): D_r(n) = [ 0 . D_r(n-1) ] [ 10 . D_r(n-2) ] [ 20 . D_r(n-2) ] [ 30 . D_r(n-2) ] etc. ------------------------------------------------------------ Page 333 (section 15.5): The two algorithms for generation Dyck words by prefix shifts given in Stephane Durocher, Pak Ching Li, Debajyoti Mondal, Aaron Williams: Ranking and Loopless Generation of k-ary Dyck Words in Cool-lex Order, The 22nd International Workshop on Combinatorial Algorithms, Victoria, Canada, IWOCA, (2011). Are implemented in fxt/src/comb/dyck-pref.h and fxt/src/comb/dyck-pref2.h The corresponding demo programs are fxt/demo/comb/dyck-pref-demo.cc and fxt/demo/comb/dyck-pref2-demo.cc ------------------------------------------------------------ Page 346 (section 16.4.1): In relation (16.4-14) both products in the denominator range from 1 to n (not from 0 to n-1 as shown). ------------------------------------------------------------ Page 348 (section 16.4.2): For the number of partitions into parts >= L whose generating function obviously is G = prod(n>=L, (1+x^n) ) the following two expressions can be given: G = sum(n>=0, x^(n*(n+1)/2+n*(L-1)) / prod(k=1..n, 1-x^k) ) G = sum(n>=L-1, x^(n*(n+1)/2-L*(L-1)/2) / prod(k=1..n-(L-1), 1-x^k) ) ------------------------------------------------------------ Page 350 (section 16.4.2): Another identity for the partitions into parts r mod m (r!=0) (cf. relation (16.4-38)) can be given as follows: 1/prod(n>=0, 1-x^(m*n+r) ) = sum(n>=0, x^(r*n)/prod(k=1..n, 1-x^(m*k) ) ) In relation (16.4-39), the lower limit for the products on the right needs to be k=1 (not k=0 as given): prod(n>=0, 1+x^(m*n+r) ) = sum(n>=0, x^((m*n^2+(2*r-m)*n)/2) / prod(k=1..n, 1-x^(m*k)) ) ------------------------------------------------------------ Page 368 (section 17.3.5): In the table of numbers of F-increment RGSs n should start with 1 (not 0, as given). ------------------------------------------------------------ Page 406 (section 20.5.2): The Gray code for Lyndon words of length 41 (using comparison function 2) was computed in December 2016. Thanks to Wolfgang Bauer for doing this. [Reported by Wolfgang Bauer, 2016-December-19] ------------------------------------------------------------ Page 417 (section 21.2.3): In the first line the formula exp(i x) = sin(x) + i cos(x) should be (swap sin and cos) exp(i x) = cos(x) + i sin(x) [Reported by Mani Zandifar, 2-November-2010] A blank is missing between the words "type" and "double" near the end of the page. [Reported by Stefan Kanthak, 2019-March-03] ------------------------------------------------------------ Page 437 (section 21.9.1): In the arguments of both exponential functions in relation (21.9-4) the factor 2*Pi*i is missing. ------------------------------------------------------------ Page 446 (section 22.2.2): In relations (22.2-3) and (22.2-4) drop the subscript Tau. ------------------------------------------------------------ Page 467 (section 23.4.2): The file containing the routines void walsh_wak_matrix(Type *f, ulong ldn) and void walsh_wak_matrix_1(Type *f, ulong ldn) has been removed from the fxt library, find it under fxt/src/walsh/attic/walshwakmatrix.h ------------------------------------------------------------ Page 478 (section 23.7.2): The routine grs_negate() is defined as template void grs_negate(Type *f, ulong n) // Negate elements at indices where the Golay-Rudin-Shapiro is negative. { for (ulong k=0; k>1) ); // == grs_negative_q(k) if ( gnq ) f[k] = -f[k]; } } It is given in fxt/src/walsh/grsnegate.h ------------------------------------------------------------ Page 553 (section 28.1.3.1): Replace "f(s)=log_s(2s+1)" by "f(s)=log_s(2s-1)". [Reported by Christoph Feck, 2015-October-09] ------------------------------------------------------------ Page 562 (section 28.4): The references files fxt/src/mult/auxil.cc and fxt/src/mult/fxtmultiply.cc have been moved from the fxt library to the hfloat library (under the same file names). ------------------------------------------------------------ Page 568 (section 29.1.1): The last three lines in Figure 29.1-A are incorrect. The correct version is y_2 := 1.0000000 - d * x_2 = 0.00000044 x_2 * y 2 := 0.31830975 * 0.00000044 = 0.000000014 x_3 := x_2 + x_2 * y_2 = 0.31830975 + 0.000000014 = 0.31830989 [Reported by Guenter Rote, 2021-June-14] ------------------------------------------------------------ Page 575 (section 29.3.4): Relation (29.3-19) is incorrect and should be removed. ------------------------------------------------------------ Page 589 (section 30.2.1): In relation (30.2-12) replace f(x) by A(x). ------------------------------------------------------------ Page 603 (section 31.2.2): The last expression for E in relation (31.2-17b) must be negated. ------------------------------------------------------------ Page 608 (section 31.3.3): In relation (31.3-29h) the q in the denominator on the right side needs to be q^4. ------------------------------------------------------------ Page 647 (section 33.2.1): In the last line cos() and sin() need to be swapped: " ... the values of x and y approach cos(Pi/3)=1/2 and sin(Pi/3) ... " [Reported by Karsten Meißner, 2020-January-17] ------------------------------------------------------------ Page 650 (section 33.2.3): [Citation from the reporting email] "... there is an error in Chapter 33, page 650 when describing the hyperbolic vectoring mode used to calculate the square root. You state that z will tend to K'sqrt(w) but the result for the square root calculation appears in the x value." "It may also be worth noting that the sqrt calculation is only accurate for the range 0.5 <= w <= 2.0. The natural log calculation using the hyperbolic vectoring mode seems to be accurate in the range 0.5 <= z <= 9.0 in my implementation." [Reported by Gary Sands, 2014-July-11] ------------------------------------------------------------ Page 675 (section 35.1.6.3): In the idenity "... we have h(x) = sum_{k}{1 - r_k x_k} ..." in the last sentence of the page drop the subscript k of x. ------------------------------------------------------------ Page 707ff (section 37.1.3) See "On computing the generalized Lambert series" https://arxiv.org/abs/1202.6525 for fast computation of sum(n>=0, t^n/(1-x*q^n)). ------------------------------------------------------------ Page 709 (section 37.1.3): The power series given by relation (37.1-32) can be computed efficiently as sum(k>=1, x^(k^2) * a^k * ( 1/(1-x^k) + a*x^k/(1-a*x^k) ) ) See https://oeis.org/A079586 for an application of this method to compute the sum of the inverse Fibonacci numbers. See http://arxiv.org/abs/1202.6525 for a quite general formula. Relation (37.1-34) sum(k>=1, A(k)*x^k / (1-x^k) ) = sum(k>=1, x^(k*k) * (A(k) + sum(j>=1, (A(k) + A(k+j)) * x^(k*j)) ) ) can be generalized as sum(k>=1, A(k)*t^k / (1 - B(k)*x^k) ) = sum(k>=1, x^(k*(k-1)) * t^k * (A(k)*B(k)^(k-1) + sum(j>=1, ( A(k)*B(k)^(k+j-1)*x^j + A(k+j)*B(k+j)^(k-1)*t^j ) * x^(j*(k-1)) ) ) ) Setting t=x and B(k)=1 gives relation (37.1-34). ------------------------------------------------------------ Page 712 (section 37.2.3): In the last expression in relation (37.2-15a) replace x^k/n by x^k/k The identity, written as exp(sum(n>=1, sigma(n)/n * x^n) = 1/eta(x) where sigma(n) denotes the sum of divisors of n can be generalised as follows: exp(sum(n>=1, sigma(s*n)/n * x^n) = prod(d divides s, eta(x^d)^(-moebius(d)*sigma(s/d)) ) ------------------------------------------------------------ Page 715 (section 37.2.4): A very large collection of identities like relation (37.2-24a) is given by Michael Somos at http://eta.math.georgetown.edu/ ------------------------------------------------------------ Page 744 (section 38.8.3): The last term in the continued fraction given in equation (38.8-10) should be 2 (not 3 as given). [Reported by Kevin Ryde, 2020-July-10] ------------------------------------------------------------ Page 767 (section 39.1.4): The routines for the gcd () are now in the file fxt/src/aux0/gcd.h For alternative version for gcd() and binary_ugcd() see file fxt/src/aux0/gcd.h [Reported by Stefan Kanthak, 2019-March-03] ------------------------------------------------------------ Page 826 (section 40.1.6): In step 3 of the algorithm for exact division the last operation should be "R := R + T", not "R := T" as given. [Reported by Michael Maier, 2020-September-02] ------------------------------------------------------------ Page 850 (section 40.9.2): Clause (3) of Swan's theorem has to be n is odd, k is even and ... [Reported by Charles Greathouse, 2015-June-05] ------------------------------------------------------------ Page 855 (section 40.9.13): In the last sentence of the page, replace "primitve" by "primitive". ------------------------------------------------------------ Page 885 (section 41.9.1): The sequence of numbers n such that a length-n CLHCA of maximal period exists is A194125 of the OEIS, see https://oeis.org/A194125 ------------------------------------------------------------ Page 887 (section 42.1.3): The first sentence "The trace of an element u ..." should read "The trace of an element a ..." [Reported by Marc Delvaux, 24-December-2012] ------------------------------------------------------------ Page 907 (section 42.6.3.5): Just after relation (42.6-12), insert "for" where it belongs: "... works [for] all odd n:" ------------------------------------------------------------ Page 908 (section 42.6.4): typo: "Therfore" --> "Therefore" (end of page) ------------------------------------------------------------ Page 919 (section 42.9.2.2): In step (5.b) of the algorithm, replace F_{i-1} by F_{k-1}. ------------------------------------------------------------ Page 921 (appendix A): typo: "expecially" --> "especially" (end of page) ------------------------------------------------------------ Page 925 (appendix C): In "Logical operators are && (and), || (or), and ! (not)" The "||" (for logical or) is missing. [Reported by Lorenzo Newman, 2019-March-18] ------------------------------------------------------------ Page 928 (appendix C): In the last sentence on the page replace break(n) by next(n). ------------------------------------------------------------ Page 930 (appendix C): The rarely useful null-defaults can now be turned off using the command default(strictargs,1) before any functions are defined. ------------------------------------------------------------ Bibliography: Page 932: Item [31] by David H. Bailey et. al. is available at http://www.emis.de/journals/EM/expmath/volumes/10/10.html (the given link became invalid: as the domain expmath.org has been hijacked by a spammer.) Page 933: Item [46] by E. R. Berlekamp is available at http://www.alcatel-lucent.com/bstj/vol46-1967/bstj-vol46-issue08.html Page 935: Item [46] by Dany Breslauer and Devdatt P. Dubhashi is now available at http://www.brics.dk/LS/95/4/ Page 936: Item [106] by Mathieu Ciet et. al. is available at http://www.uclouvain.be/crypto/publications/year/2002 (the given link became invalid) Page 937: Item [111] by Henri Cohen et. al. is available at http://www.emis.de/journals/EM/expmath/volumes/9/9.html (the given link became invalid: as the domain expmath.org has been hijacked by a spammer.) Page 938: Item [134] by Peter Eades and Brendan McKay is available at http://cs.anu.edu.au/~bdm/publications.html Page 942: Item [217] by Koike and Shiga is available at http://dx.doi.org/10.1016/j.jnt.2006.08.002 The title of the final version is "Isogeny formulas for the Picard modular form and a three terms arithmetic geometric mean" Page 945: Item [248] by Igor Pak is available at http://www.combinatorics.org/issue/view/Surveys (the link given became invalid). Page 945: Item [265] by Igor Pak is now available at http://www.math.ucla.edu/~pak/papers/research.htm#par (the given link became invalid) Page 948: Item [322] by Damien Stehle and Paul Zimmermann is available at http://hal.inria.fr/LORIA/inria-00071533 Page 949: Item [338] by Vincent Vajnovszki and Timothy Walsh, and items [342] and [343] by Timothy Walsh are available at http://www.info2.uqam.ca/~walsh_t/pages/papers.html Page 950: Item [361] by Hugh C. Williams is titled "\'{E}douard Lucas and primality testing" (not "\'{E}duard ..." as given, where the letter o is missing). Page 950: Item [368] by Neal Zierler is available at http://www.ams.org/journals/proc/1958-009-02/S0002-9939-1958-0094332-2/ ------------------------------------------------------------ End of file. ------------------------------------------------------------