Generalized approaches to constant division

There is no file associated with this item.
Disclaimer 
Access requires a license to the Dissertations and Theses (ProQuest) database. 
Link to File 
http://libproxy.tulane.edu:2048/login?url=http://gateway.proquest.com/openurl?url_ver=Z39.882004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:9008735 
Title 
Generalized approaches to constant division 
Author 
Raghuram, Padmini Srinivasan 
School 
Tulane University 
Academic Field 
Computer Science 
Abstract 
The division process is not only the most complex but also the most timeconsuming arithmetic operation in a digital computer. There exist many types of specialpurpose systems which require rapid and repeated division by a set of known constant divisors. Even in general purpose machines, since integer division takes significantly longer than additions or subtraction, if many divisions are needed, this disparity in execution time can result in a bottleneck. It is therefore beneficial to seek ways to do specific division cases faster, in order to improve the average performance of division Numerous solutions have been proposed in response to the deficiencies of the conventional division algorithms, for applications which involve repeated divisions by known constants. The approaches in the literature are outlined and characterized with respect to timing, generality, implied redundancy, and the possibility of shared computation, parallelism,, and pipelined implementation. The applicationdependent development of the constant division approaches has left a gap in the theoretical foundations of the algorithms. Here the various methods are mathematically explained and unified through the establishment of their common theoretical basis A major intended contribution of this research is the definition of approaches to division by constants belonging to the set of integers of the form 2$\sp{n}\ \pm$ 1. Generalized algorithms for division by integers of the form 2$\sp{n}\ \pm$ 1, for an arbitrary value or values of $n$, are developed and proved correct. Implementation issues are explored in the development of design suggestions for the constant division method The algorithms presented are a good solution to the problem of division by constants of the specific form 2$\sp{n}\ \pm$ 1, for $n$ $\in$ N, $n$ $>$ 0. The consideration of such a subset of divisor values (of the form 2$\sp{n}\ \pm$ 1) is not, however, a satisfactory solution to the general problem of constant division. Dividers designed for constant divisors in this set can trivially be extended to cover divisors of the form 2$\sp{m}(2\sp{n}\pm1)$, $m$ $\in$ N. The EulerFermat theorem is used to show that, with one additional multiplication, division by any integer can be converted to a division by an integer of the for 2$\sp{n}$ $$ 1. The multiplier to be determined is established to be the value in one period of the reciprocal of the divisor. Approaches to reciprocal determination are therefore presented, specifically methods that take advantage of the special characteristics of reciprocals of integers 
Language 
eng 
Advisor(s) 
Petry, Frederick E 
Degree Date 
1989 
Degree 
Ph.D 
Publisher 
Tulane University 
Publication Date 
1989 
Source 
Source: 103 p., Dissertation Abstracts International, Volume: 5011, Section: B, page: 5176 
Identifier 
See 'reference url' on the navigation bar. 
Rights 
Copyright is in accordance with U.S. Copyright law 
Contact Information 
acase@tulane.edu 
Rating 

Add tags for Generalized approaches to constant division
you wish to report:
...