Open Collections

S-R-T division algorithms as dynamical systems

University of British Columbia

S-R-T division, as it was discovered in the late 1950s [4, 19, 23], represented an important improvement in the speed of division algorithms for computers at the time. A variant of S-R-T division is still commonly implemented in computers today. Although some bounds on the performance of the original S-R-T division method were obtained, a great many questions remained unanswered. In this thesis, S-R-T 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 S-R-T division is ergodic, and is even Bernoulli, for all real divisors and dividends.

Thesis/Dissertation

application/pdf

2009-08-13

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

http://hdl.handle.net/2429/12179

Computer Science

University of British Columbia

UBCV

DSpace