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

Descripción completa

Detalles Bibliográficos
Autores principales: Heuberger, Clemens, Kropf, Sara, Prodinger, Helmut
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