loading...
SRT Division Algorithms as Dynamical Systems
Santiago de Compostela, Spain June 15-June 18
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ARITH.2003.120765916th IEEE Symposium on Computer Arith ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Mark McCann, University of British Columbia
Nicholas Pippenger, University of British Columbia
SRT division, as it was discovered in the late 1950s represented an important improvement in the speed of division algorithms for computers at the time. A variant of SRT division is still commonly implemented in computers today. Although some bounds on the performance of the original SRT division method were obtained, a great many questions remained unanswered. In this paper, the original version of SRT division is described as a dynamical system. This enables us to bring modern dynamical systems theory, a relatively new development in mathematics, to bear on an older problem. In doing so, we are able to show that SRT division is ergodic, and is even Bernoulli, for all real divisors and dividends. With the Bernoulli property, we are able to use entropy to prove that the natural extensions of SRT division are isomorphic by way of the Kolmogorov-Ornstein Theorem. We demonstrate how our methods and results can be applied to a much larger class of division algorithms.
Citation:
Mark McCann, Nicholas Pippenger, "SRT Division Algorithms as Dynamical Systems," arith, pp.46, 16th IEEE Symposium on Computer Arithmetic (ARITH-16 '03), 2003
Usage of this product signifies your acceptance of the Terms of Use.