Analysis of carries in signed digit expansions

DOI10.1007/S00605-016-0917-XMaRDI QIDQ509708zbMATH OpenOpenAlexWikidataFDO

Authors Clemens Heuberger, Sara Kropf, Helmut Prodinger

Publication date 17 February 2017

Published in Monatshefte für Mathematik (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1503.08816

zbMATH Keywords

central limit theoremprobabilistic automatontransducercarrysymmetric signed digit expansionvon Neumann's addition

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Central limit and other weak theorems (60F05) Analysis of algorithms (68W40) Combinatorial probability (60C05) Radix representation; digital problems (11A63)

Abstract: 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.

Recommendations

• Carry propagation in signed digit representations
• A generalization of the carries process
• Analysis of Carry Propagation in Addition: An Elementary Approach
• The carry propagation of the successor function
• Carry-free addition of recoded binary signed-digit numbers

Cites work

• scientific article; zbMATH DE number 3593676 (Why is no real title available?)
• scientific article; zbMATH DE number 3193698 (Why is no real title available?)
• A Mathematical Theory of Communication
• A generalization of carries processes and Eulerian numbers
• Analysis of carries in signed digit expansions
• Automata in SageMath -- combinatorics meet theoretical computer science
• Bootstrapping and double-exponential limit laws
• Carry propagation in signed digit representations
• Combinatorics of balanced carries
• Intrinsic Markov Chains
• Mellin transforms and asymptotics: Harmonic sums
• On minimal expansions in redundant number systems: Algorithms and quantitative analysis
• Variances and covariances in the central limit theorem for the output of a transducer

Cited in

(7)

• scientific article; zbMATH DE number 1962050 (Why is no real title available?)
• On the number of carries occurring in an addition mod \(2^k -1\)
• Carry propagation in signed digit representations
• SUBBLOCK OCCURRENCES IN SIGNED DIGIT REPRESENTATIONS
• Analysis of Carry Propagation in Addition: An Elementary Approach
• The carry propagation of the successor function
• Analysis of carries in signed digit expansions

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: Analysis of carries in signed digit expansions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q509708)