dc.identifier.uri |
http://dx.doi.org/10.15488/2694 |
|
dc.identifier.uri |
http://www.repo.uni-hannover.de/handle/123456789/2720 |
|
dc.contributor.author |
Grübel, Rudolf
|
|
dc.contributor.author |
Reimers, Anke
|
|
dc.date.accessioned |
2018-01-29T14:13:18Z |
|
dc.date.available |
2018-01-29T14:13:18Z |
|
dc.date.issued |
2001 |
|
dc.identifier.citation |
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 |
|
dc.description.abstract |
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. |
eng |
dc.language.iso |
eng |
|
dc.publisher |
Cambridge : Cambridge University Press |
|
dc.relation.ispartofseries |
RAIRO - Theoretical Informatics and Applications 35 (2001), Nr. 2 |
|
dc.rights |
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. |
|
dc.subject |
Carry propagation |
eng |
dc.subject |
Discretization |
eng |
dc.subject |
Gumbel distributions |
eng |
dc.subject |
Large deviations |
eng |
dc.subject |
Limit distributions |
eng |
dc.subject |
Logarithmic periodicity |
eng |
dc.subject |
Total variation distance |
eng |
dc.subject |
Algorithms |
eng |
dc.subject |
Boolean functions |
eng |
dc.subject |
Iterative methods |
eng |
dc.subject |
Number theory |
eng |
dc.subject |
Probability distributions |
eng |
dc.subject |
Random processes |
eng |
dc.subject |
Theorem proving |
eng |
dc.subject |
Addition algorithm |
eng |
dc.subject |
Logarithmic periodicity |
eng |
dc.subject |
Von Neumann addition |
eng |
dc.subject |
Information theory |
eng |
dc.subject.ddc |
510 | Mathematik
|
ger |
dc.title |
On the number of iterations required by von Neumann addition |
|
dc.type |
Article |
|
dc.type |
Text |
|
dc.relation.issn |
0988-3754 |
|
dc.relation.doi |
https://doi.org/10.1051/ita:2001115 |
|
dc.bibliographicCitation.issue |
2 |
|
dc.bibliographicCitation.volume |
35 |
|
dc.bibliographicCitation.firstPage |
187 |
|
dc.bibliographicCitation.lastPage |
206 |
|
dc.description.version |
publishedVersion |
|
tib.accessRights |
frei zug�nglich |
|