Analysis of carries in signed digit expansions. (English) Zbl 1419.60009
Summary: The number of positive and negative carries in the addition of two independent random signed digit expansions of given length is analyzed asymptotically for the \((q,d)\)-system and the symmetric signed digit expansion. The results include expectation, variance, covariance between the positive and negative carries and a central limit theorem. Dependencies between the digits require determining suitable transition probabilities to obtain equidistribution on all expansions of given length. A general procedure is described to obtain such transition probabilities for arbitrary regular languages. The number of iterations in von Neumann’s parallel addition method for the symmetric signed digit expansion is also analyzed, again including expectation, variance and convergence to a double exponential limiting distribution. This analysis is carried out in a general framework for sequences of generating functions.
MSC:
| 60C05 | Combinatorial probability |
| 11A63 | Radix representation; digital problems |
| 60F05 | Central limit and other weak theorems |
| 68Q45 | Formal languages and automata |
| 68W40 | Analysis of algorithms |
Keywords:
carry; central limit theorem; transducer; probabilistic automaton; symmetric signed digit expansion; von Neumann’s additionSoftware:
SageMathReferences:
| [1] | Diaconis, P., Fulman, J.: Combinatorics of balanced carries. Adv. Appl. Math. 59, 8-25 (2014) · Zbl 1308.60018 · doi:10.1016/j.aam.2014.05.005 |
| [2] | Flajolet, P., Gourdon, X., Dumas, P.: Mellin transforms and asymptotics: Harmonic sums. Theoret. Comput. Sci. 144, 3-58 (1995) · Zbl 0869.68057 · doi:10.1016/0304-3975(95)00002-E |
| [3] | Heuberger, C., Krenn, D., Kropf, S.: Automata in SageMath-combinatorics meets theoretical computer science. Discrete Math. Theor. Comput. Sci. 18(3), 1-21 (2016) · Zbl 1401.68369 |
| [4] | Heuberger, C., Kropf, S., Prodinger, H.: Analysis of carries in signed digit expansions—ancillary files, http://arxiv.org/src/1503.08816/anc (2015) · Zbl 1419.60009 |
| [5] | Heuberger, C., Kropf, S., Wagner, S.: Variances and covariances in the central limit theorem for the output of a transducer. European J. Combin. 49, 167-187 (2015) · Zbl 1329.68161 · doi:10.1016/j.ejc.2015.03.004 |
| [6] | Heuberger, C., Prodinger, H.: On minimal expansions in redundant number systems: Algorithms and quantitative analysis. Computing 66, 377-393 (2001) · Zbl 1030.11003 · doi:10.1007/s006070170021 |
| [7] | Heuberger, C., Prodinger, H.: Carry propagation in signed digit representations. European J. Combin. 24, 293-320 (2003) · Zbl 1026.11015 · doi:10.1016/S0195-6698(03)00008-8 |
| [8] | Knuth, D.E.: The average time for carry propagation. Nederl. Akad. Wetensch. Indag. Math. 40, 238-242 (1978) · Zbl 0382.10035 · doi:10.1016/S1385-7258(78)80014-6 |
| [9] | Nakano, F., Sadahiro, T.: A generalization of carries processes and Eulerian numbers. Adv. in Appl. Math. 53, 28-43 (2014) · Zbl 1285.60007 · doi:10.1016/j.aam.2013.09.005 |
| [10] | Parry, W.: Intrinsic Markov chains. Trans. Amer. Math. Soc. 112, 55-66 (1964) · Zbl 0127.35301 · doi:10.1090/S0002-9947-1964-0161372-1 |
| [11] | Prodinger, H., Wagner, S.: Bootstrapping and double-exponential limit laws. Discrete Math. Theor. Comput. Sci. 17(1), 123-144 (2015) · Zbl 1311.05015 |
| [12] | Reitwiesner, G.W.: Binary arithmetic, Advances in Computers, vol. 1, pp. 231-308. Academic Press, New York (1960) · Zbl 0119.00403 |
| [13] | The SageMath Developers: SageMath Mathematics Software (Version 7.0), 2016, http://www.sagemath.org · Zbl 0869.68057 |
| [14] | Shannon, C.E.: A mathematical theory of communication. Bell System Tech. J. 27, 379-423 (1948) · Zbl 1154.94303 · doi:10.1002/j.1538-7305.1948.tb01338.x |
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.
