Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
SRT division algorithms as dynamical systems
McCann M., Pippenger N.  SIAM Journal on Computing 34 (6): 1279-1301, 2005. Type: Article
Date Reviewed: Feb 23 2006

This paper investigates a family of division algorithms (referred to as Sweeney-Robertson-Tocher (SRT)) as examples of dynamical systems. Although the main result of the paper can be understood without recourse to the dynamical systems theory literature, some preliminary familiarity with this important field of mathematics is probably needed to really appreciate the paper.

SRT can be viewed naturally as a discrete dynamical system, in that the partial remainders and quotient bits, pi+1 ,qi+1, can be expressed as polynomial functions (in fact, linear functions) of pi, qi+1. The subtlety is that one of some finite number of functions is applied according to some branching conditions. In the case of SRT, these conditions are expressible as inequalities in pi and |pi|.

The authors convert SRT into a transformation T on reals in the half-closed interval [0,1), and study orbits of T on subsets of [0,1). An orbit of S ⊆ [0,1) is the sequence of subsets Ti S, where i may be negative in case T is invertible.

The main result is that T is essentially a Bernoulli transformation. The original Bernoulli transformation is the shift xi+1 = 2xi mod 1 for x ∈ [0,1). This transformation is a bit shifting operator on the binary expansion of x. That the SRT transformation T is Bernoulli makes possible the computation of quantities that enable one to further compute such things as the expected number of shift register operations used in an SRT division, and obtain estimates on the expected SRT performance.

The authors extend their result to more complex SRT algorithms, although they know that certain restrictions on divisors need to be imposed to preserve the Bernoulli property for T. Since many arithmetic algorithms can be fairly easily expressed as dynamical systems, it should be possible to apply the methods of this paper to characterizations of their global properties.

Reviewer:  Bruce Litow Review #: CR132475 (0611-1143)
Bookmark and Share
 
Algorithms (B.2.4 ... )
 
 
Markov Processes (G.3 ... )
 
 
Number-Theoretic Computations (F.2.1 ... )
 
 
Numerical Algorithms And Problems (F.2.1 )
 
 
Probability And Statistics (G.3 )
 
Would you recommend this review?
yes
no
Other reviews under "Algorithms": Date
Fifty years of P vs. NP and the possibility of the impossible
Fortnow L.  Communications of the ACM 65(1): 76-85, 2022. Type: Article
Jun 27 2022
Efficient resource sharing algorithm for physical register file in simultaneous multi-threading processors
Zhang Y., Lin W.  Microprocessors & Microsystems 45, Part B, 270-282, 2016. Type: Article
Nov 9 2016
 New approach to design for reusability of arithmetic cores in systems-on-chip
Margala M., Wang H.  Integration, the VLSI Journal 38(2): 185-203, 2004. Type: Article
Aug 17 2005
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2022 ThinkLoud, Inc.
Terms of Use
| Privacy Policy