×

The Hamming weight of the non-adjacent-form under various input statistics. (English) Zbl 1164.11009

The Hamming weight of the integer \(\sum \varepsilon_j2^j\) with \(\varepsilon_j\in \{-1,0,+1\}\) is the number of non-zero \(\varepsilon'\)s. It is known that every integer admits a unique such representation satisfying \(\varepsilon_j\varepsilon_{j+1}=0\) for all \(j\), and that this representation minimizes the Hamming weight. It is also known that the expected weight of an integer \(< 2^n\) is \(\frac 13 n+O(1)\). In the paper under review the authors study the expected Hamming weight for integers satisfying certain properties. Two typical results are: let \(a_{k,n}\) be the normalized excepted Hamming weight for a nonnegative integer \(<2^n\) written as \(\sum\varepsilon_j 2^j\) \(\varepsilon_j \varepsilon_{j+1}=0\), and whose usual binary expansion has \(k\) nonzero digits. Then 1) if \(k\) and \(n\) tend to infinity with \(0<c\leq k/n\leq d<1\), then \[ a_{k,n}\sim\frac{1-4\big(\frac k n -\frac 12\big)^2}{3+4\big(\frac kn -\frac 12\big)^2} n\quad \text{uniformly}; \]
2) if \(k\) is fixed and \(n\) goes to infinity, then \[ a_{k,n}=k-\frac{k(k-1)(k-2)}{n^2}+O\left(\frac{1}{n^3}+\frac{1}{n^{k-1}}\right). \]

MSC:

11A63 Radix representation; digital problems
68W40 Analysis of algorithms
68Q45 Formal languages and automata
05A16 Asymptotic enumeration
05A15 Exact enumeration problems, generating functions

Software:

Omega
Full Text: DOI

References:

[1] G. E. Andrews, P. Paule and A. Riese, MacMahon’s partition analysis: the Omega package, European J. Combin., 22 (2001), 887–904. · Zbl 0979.05008 · doi:10.1006/eujc.2001.0527
[2] S. Arno and F. S. Wheeler, Signed digit representations of minimal hamming weight, IEEE Trans. Comp., 42 (1993), 1007–1010. · doi:10.1109/12.238495
[3] E. A. Bender, Central and local limit theorems applied to asymptotic enumeration, J. Combinatorial Theory Ser. A, 15 (1973), 91–111. · Zbl 0242.05006 · doi:10.1016/0097-3165(73)90038-1
[4] E. A. Bender and L. B. Richmond, Central and local limit theorems applied to asymptotic enumeration. II. Multivariate generating functions, J. Combin. Theory Ser. A, 34 (1983), 255–265. · Zbl 0511.05003 · doi:10.1016/0097-3165(83)90062-6
[5] M. Drmota, Asymptotic distributions and a multivariate Darboux method in enumeration problems, J. Combin. Theory Ser. A, 67 (1994), 169–184. · Zbl 0801.60016 · doi:10.1016/0097-3165(94)90011-6
[6] Ph. Flajolet and A. Odlyzko, Singularity analysis of generating functions, SIAM J. Discrete Math., 3 (1990), 216–240. · Zbl 0712.05004 · doi:10.1137/0403019
[7] Ph. Flajolet and R. Sedgewick, Analytic combinatorics, in preparation, preprint available at http://algo.inria.fr/flajolet/Publications . · Zbl 1165.05001
[8] P. J. Grabner, C. Heuberger and H. Prodinger, Subblock occurrences in signed digit representations, Glasgow Math. J., 45 (2003), 427–440. · Zbl 1049.11084 · doi:10.1017/S0017089503001368
[9] P. J. Grabner, C. Heuberger, H. Prodinger and J. Thuswaldner, Analysis of linear combination algorithms in cryptography, ACM Trans. Algorithms, 1 (2005), 123–142. · Zbl 1321.68514 · doi:10.1145/1077464.1077473
[10] C. Heuberger, Hwang’s quasi-power-theorem in dimension two, preprint available at http://www.opt.math.tu-graz.ac.at/:_cheub/publications/quasipower.pdf . · Zbl 1135.60304
[11] C. Heuberger and H. Prodinger, On minimal expansions in redundant number systems: Algorithms and quantitative analysis, Computing, 66 (2001), 377–393. · Zbl 1030.11003 · doi:10.1007/s006070170021
[12] C. Heuberger and H. Prodinger, Analysis of alternative digit sets for nonadjacent representations, Monatsh. Math., 147 (2006), 219–248. · Zbl 1094.11007 · doi:10.1007/s00605-005-0364-6
[13] H.-K. Hwang, On convergence rates in the central limit theorems for combinatorial structures, European J. Combin., 19 (1998), 329–343. · Zbl 0906.60024 · doi:10.1006/eujc.1997.0179
[14] P. A. MacMahon, Combinatory analysis, Cambridge University Press, Cambridge, 1915–1916, (Reprinted: Chelsea, New York, 1960). · Zbl 0101.25102
[15] F. Morain and J. Olivos, Speeding up the computations on an elliptic curve using addition-subtraction chains, RAIRO Inform. Théor. Appl., 24 (1990), 531–543. · Zbl 0724.11068
[16] G. W. Reitwiesner, Binary arithmetic, Advances in computers, vol. 1, Academic Press, New York, 1960, 231–308.
[17] J. M. Thuswaldner, Summatory functions of digital sums occurring in cryptography, Period. Math. Hungar., 38 (1999), 111–130. · Zbl 0936.11009 · doi:10.1023/A:1004715619287
[18] J. H. Van Lint, Introduction to coding theory, 2nd ed., Graduate Texts in Mathematics, vol. 86, Springer, 1992.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.