Cargando…
Analysis of carries in signed digit expansions
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 nega...
Autores principales: | , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Springer Vienna
2016
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7175708/ https://www.ncbi.nlm.nih.gov/pubmed/32355364 http://dx.doi.org/10.1007/s00605-016-0917-x |
_version_ | 1783524885046231040 |
---|---|
author | Heuberger, Clemens Kropf, Sara Prodinger, Helmut |
author_facet | Heuberger, Clemens Kropf, Sara Prodinger, Helmut |
author_sort | Heuberger, Clemens |
collection | PubMed |
description | 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. |
format | Online Article Text |
id | pubmed-7175708 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2016 |
publisher | Springer Vienna |
record_format | MEDLINE/PubMed |
spelling | pubmed-71757082020-04-28 Analysis of carries in signed digit expansions Heuberger, Clemens Kropf, Sara Prodinger, Helmut Mon Hefte Math Article 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. Springer Vienna 2016-06-10 2017 /pmc/articles/PMC7175708/ /pubmed/32355364 http://dx.doi.org/10.1007/s00605-016-0917-x Text en © The Author(s) 2016 Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. |
spellingShingle | Article Heuberger, Clemens Kropf, Sara Prodinger, Helmut Analysis of carries in signed digit expansions |
title | Analysis of carries in signed digit expansions |
title_full | Analysis of carries in signed digit expansions |
title_fullStr | Analysis of carries in signed digit expansions |
title_full_unstemmed | Analysis of carries in signed digit expansions |
title_short | Analysis of carries in signed digit expansions |
title_sort | analysis of carries in signed digit expansions |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7175708/ https://www.ncbi.nlm.nih.gov/pubmed/32355364 http://dx.doi.org/10.1007/s00605-016-0917-x |
work_keys_str_mv | AT heubergerclemens analysisofcarriesinsigneddigitexpansions AT kropfsara analysisofcarriesinsigneddigitexpansions AT prodingerhelmut analysisofcarriesinsigneddigitexpansions |