On the number of iterations required by von Neumann addition

Originalpublikation

Grübel, R.; Reimers, A.: On the number of iterations required by von Neumann addition. In: RAIRO - Theoretical Informatics and Applications 35 (2001), Nr. 2, S. 187-206. DOI: https://doi.org/10.1051/ita:2001115

Version im Repositorium

Zum Zitieren der Version im Repositorium verwenden Sie bitte diesen DOI: https://doi.org/10.15488/2694

Thumbnail
Name: ita0021.pdf
Größe: 208.7Kb
Format: PDF
Öffnen
Zusammenfassung:
We investigate the number of iterations needed by an addition algorithm due to Burks et al. if the input is random. Several authors have obtained results on the average case behaviour, mainly using analytic techniques based on generating functions. Here we take a more probabilistic view which leads to a limit theorem for the distribution of the random number of steps required by the algorithm and also helps to explain the limiting logarithmic periodicity as a simple discretization phenomenon.
Lizenzbestimmungen: Es gilt deutsches Urheberrecht. Das Dokument darf zum eigenen Gebrauch kostenfrei genutzt, aber nicht im Internet bereitgestellt oder an Außenstehende weitergegeben werden. Dieser Beitrag ist aufgrund einer (DFG-geförderten) Allianz- bzw. Nationallizenz frei zugänglich.
Publikationstyp: Article
Publikationsstatus: publishedVersion
Erstveröffentlichung: 2001
Schlagwörter (englisch): Carry propagation, Discretization, Gumbel distributions, Large deviations, Limit distributions, Logarithmic periodicity, Total variation distance, Algorithms, Boolean functions, Iterative methods, Number theory, Probability distributions, Random processes, Theorem proving, Addition algorithm, Logarithmic periodicity, Von Neumann addition, Information theory
Fachliche Zuordnung (DDC): 510 | Mathematik

Downloadstatistik

Zur Langanzeige

Die Publikation erscheint in Sammlung(en):

 

Suche im Repositorium


Durchblättern

Mein Nutzer/innenkonto

Nutzungsstatistiken