S-R-T Division Algorithms As Dynamical Systems by Mark A. McCann B.Sc, University of British Columbia, 1999 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF Master of Science in THE FACULTY OF GRADUATE STUDIES (Department of Computer Science) We accept this thesis as conforming to the required standard The University of British Columbia April 2002 © Mark A. McCann, 2002 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of Compter Sciintt The University of British Columbia Vancouver, Canada Date DE-6 (2/88) Abstract 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 unan swered. 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. ii Contents Abstract ii Contents iiList of Figures v Acknowledgements vi 1 Introduction and Background 1 1.1 Introduction to S-R-T Division1.2 S-R-T Division as a Dynamical System 5 1.3 Shift Average for D € [|, 1) 2 2 Bernoulli Property 5 2.1 Proof of Bernoulliness 16 2.2 Entropy oi TD • 19 3 Extensions to Multi-Divisor S-R-T Division 23 3.1 Multi-Divisor S-R-T Division 23.2 Proof of Bernoulliness 7 3.3 Some Restrictions on a 32 3.4 Entropy of Multi-Divisor S-R-T Division 37 iii 4 Future Work Bibliography List of Figures 1.1 A pseudo state-machine for converting to binary 4 1.2 S-R-T division where p0 = 0.67, and D = 0.75 5 1.3 Following partial remainder magnitudes graphically for D = 0.75 and p0 = 0.67 7 1.4 Applying T4/5 to x = j one hundred times 8 1.5 Applying T4/5 to x = f + 0.00001 one hundred times ' 8 1.6 Applying P associated with T3/5 to f{x) = 1 six times 11 1.7 Applying P associated with T3/5 to f(x) — ^~ f^2 ^ six times 12 3.1 S-R-T division where p0 = 0.67, D = 0.75, and a = (0.75,1,1.25) 27 3.2 Combined plot of the regions where oti(e, D) < | and a2(e, D) > 1 for proof of Theorem 15 34 3.3 An example of a non-ergodic system for TD)Q G 9Tt„>4 34 3.4 An example of a non-ergodic system for To,a £ 9^3 35 3.5 An example of a non-ergodic system for To;a G WI2 37 v Acknowledgements I would like to thank my thesis supervisor, Nick Pippenger, for his patient guidance and for the inspiration for this thesis. I would like to thank Mark Greenstreet for the many excellent comments and suggestions that he provided as my second reader. I would like to thank my good friends Ellen Gethner, Wesley Wong, and Michael Forbes for many good conversations relating to my thesis, and for their numerous helpful suggestions. I would especially like to thank my wife Karen for being a constant support and encouragement to me throughout my Master's degree. Finally, I would like to thank my parents for all the support and en couragement they have given me through numerous years of schooling. MARK A. MCCANN The University of British Columbia April 2002 vi Chapter 1 Introduction and Background 1.1 Introduction to S-R-T Division "S-R-T division" roughly refers to a class of non-restoring, binary division algorithms that have been designed for floating-point computers [3, 5, 6, 7, 14, 22]. The term "non-restoring" refers to the fact that partial remainders are allowed to range freely through the interval (—1,1), rather than being restored to the positive realm before proceeding to the next step. This feature reduces uses of the adder by about fifty percent. An equally important feature of this algorithm is the "S-R-T" optimization from whence the algorithm gets its name. In the late 1950's, Sweeney [4], Robertson [19], and Tocher [23] independently made the observation that whenever a partial remainder is in the range (—|, |), there will be one or more leading zeros that can be shifted through in a very short amount of time (usually one cycle). The more leading zeros in a given step, the more the algorithm can avoid costly uses of the adder. A further development of this original algorithm, which is still called S-R-T division, is the algorithm most often implemented in modern floating point units. In modern S-R-T division, a fixed number of quotient digits are produced every cycle as opposed to a variable number [5, pp. 37-62]. 1 An example of modern S-R-T division in use is Intel's first release of the Pentium™ CPU with its infamous "Pentium Bug," which was really just a small error in its S-R-T division implementation. This thesis will restrict its attention to the original version of S-R-T division. To present the simplest type of S-R-T division, we begin with a few definitions for an algorithm similar to that presented by Shively [22, pp. 3-4]: (a) n represents the number of iterations performed in the algorithm. (b) po is the dividend (or initial partial remainder) normalized so that po G [\, !)• (c) Pi G (—1,1), i G N, is the partial remainder after the ith step. (d) D is the divisor normalized to 1). (e) qi G {—1,0,1} (i G {0,..., n — 1}) is the quotient digit generated by the ith step. 71-1 (f) Qn = ^2 % is the "rounded off" quotient generated after n steps of the i=0 algorithm. Given the above definitions, after n steps of the division algorithm, we would like it to be true that po = DQn + s{n) where e(n) is a term that goes to zero as n goes to infinity. A recurrence relation for the S-R-T division algorithm can be stated as Pi+i = < 2pi 2(pi - D) 2(pi + D) \Pi\ < \ \pi\ > \ and pi > 0 \pi\ > \ and pi < 0, 2 and Qi = < 0 : \Pi\ < i 1 : \Pi I > 5 and Pi > 0 -1 : > 5 and pi < 0. By observing that (2{Pi-{Q)D) 2(Pi - (1)D) 2{Pi-{-l)D) we can rewrite the definition of pi+i as Pi+i = \ \Pi\ < 5 \Pi\ > \ and pi > 0 |pi| > 5 and pi < 0, After n steps have been completed, we have pn = 2nPo - 2nq0D - 2n-lqiD 2lqn-lD.. and then after dividing by 2n and solving for PQ we find that PO = 7T + Pn , qoD q\D 2° 71-1 + +... + Qn-lD Jn—1 Pn i=0 Now let e(n) = pn/2n and let Q* = lim^oo Qn- Since |pn| < 1, in the limit as n goes to infinity Po = DQ*. The quotient bits being generated are not in a standard binary representa tion, but it is a simple matter to convert the answer back to standard binary without using any expensive operations. Figure 1.1 shows a simple pseudo state-machine (re ally a push-down automaton) that converts positive floating-point numbers in the {—1,0,1} representation into binary. Figure 1.1: A pseudo state-machine for converting sequences of { — 1,0,1} into sequences of {0,1} (binary). We assume that the input sequence corresponds to a positive number. The letter 'Z' is used to indicate that the end of the sequence has been reached, and the symbol e represents the null string. We represent a run of m zeros as 0 • • • 0 and a run of m ones as 1 • • • 1. Sequences of symbols should be read m from left to right. For example, the expression 1/10 ••• 0 means: if a 1 is encountered in the input sequence, write a 1 followed by m zeros. The above conversion automaton implies that conversion happens after the calculation is completed. In reality, the conversion from the generated quotient bits to standard binary is done in hardware on-the-fiy, using registers to convert runs of zeros into runs of zeros or ones in parallel, or by performing a single subtraction. Figure 1.2 shows an example of using the S-R-T division algorithm to divide 0.67 by 0.75. The steps that produce non-zero quotient bits have been shown. In this example, after six uses of the adder, the quotient (0.893) has been determined to four digits of precision. 4 Po = 0.67 0.67 Pi = 2(0.67 - D) -0.16 go = 1 Qo = 1 Pi = 2(22(-0.16) + £>) = 0.22 Qz = -1 Qz = 0.875 Pi = 2(22(0.22) — D) = 0.26 1 Qe = 0.890625 P9 = 2(21(0.26) - D) = -0.46 qs = 1 Qs = 0.89453125 Pn = 2(21(-0.46) + D) = -0.34 Qw = -1 Qw = 0.8935546875 Pl3 = 2(21(-0.34) + D) = 0.14 912 = -1 Ql2 = 0.8933105469 Figure 1.2: An example of S-R-T division when the dividend po = 0.67, and the divisor D = 0.75. The quotient Q* is 0.893. Now, with this simple system of division in hand, we might want to ask certain questions about its performance. For example, we could ask "How many bits of precision are generated per iteration of the algorithm on average?" To answer this question, we must look at the magnitude of \Q* — Qn\ = \Pn/2n\. The number of bits of precision on the nth step is then n — log2 Pn. In the worst case, pn is close to 1, and therefore we get at least one bit of precision per iteration of the algorithm, regardless of the values of D or PQ. Of course, a designer of actual floating-point hardware probably wants to know the expected performance based on the expected values of pn. To answer the many variants of this type of question, it is clear that we must know something about the distribution of partial remainders over time. The remainder of this thesis is devoted to extending what is known about the answer to this type of question as it relates to S-R-T division and its variants. 1.2 S-R-T Division as a Dynamical System The example in figure 1.2 makes it clear that keeping track of the signs of successive partial remainders is irrelevant in determining how many times the adder will be 5 used for a particular calculation. For this reason, we only need to consider the magnitudes of successive partial remainders. We now give a reformulation of S-R-T division that will allow us to look at division as a dynamical system. Definition 1 (S-R-T Division Transformation). For D G [5,1), we define the function TD : [0,1) ->• [0,1) as TD(X) = { 2x 2(D - x) 2(x - D) 0 < x < \ \<x<D D < x < 1 This transformation of the unit interval represents the successive partial remainders that arise as S-R-T division is carried out by a divisor Dona dividend x. D is normalized to 1). The dividend x is normalized to 1) initially, while each of the successive partial remainders Tjj(x) (n G N) subsequently ranges through [0,1). By using the characteristic function for a set A defined as 1A(*) = J 1 : ieA 0 : x g" A , we can rewrite as TD(x) = 2x • l^ij(1) + 2(D - x) • lri,o)0r) + 2(x - D) • lm)(x) . (1.1) If we plot equation 1.1 on the unit interval, we obtain a very useful visual ization of our transformation. Figure 1.3 shows the plot of To.75(0;) combined with a plot of the successive partial remainders that arise while dividing 0.67 by 0.75. This is the same system that was presented earlier in figure 1.2. Notice that a vertical line in the interval [\,D) corresponds to a subsequent flip in the sign of the next partial remainder. 6 0 0.25 0.5 0.75 1 X Figure 1.3: An example of following partial remainder magnitudes graphically for D — 0.75 and po = 0.67. The heavy solid lines represent the trans formation To.75, while the abscissa of the thin vertical lines represent successive partial remainder magnitudes. Figure 1.3 shows an example of following the trajectory of a single partial remainder for a particular divisor. After ten applications of the To.75, there is not any obvious regular pattern, although we expect to see one eventually since the quotient is rational in this case. Of course, most numbers are not rational and we can deduce that for most numbers, the transformation will never exhibit a repeating pattern. In figures 1.4 and 1.5, we see that a very small change in the value of the initial partial remainder quickly produces large differences in the observed behaviour of the subsequent partial remainders. Our system appears to be chaotic (it certainly has sensitive dependence on initial conditions and is topologically transitive), and, if this the case, we will gain little understanding by studying the trajectories of 7 individual partial remainders. The logical next step is to study the behaviour of distributions of points over the whole interval. lr 0.75 0.5 0.25 100 Figure 1.4: The result of applying T4/5 to x = j one hundred times. ST 0.75 0.5 0.25 J0 20 40 60 80 100 n Figure 1.5: The result of applying T4/5 to x = j + 0.00001 one hundred times. The area of understanding the behaviour of ensembles of points under re peated transformation is the realm of dynamical systems theory. For the remainder of this thesis, we assume a certain amount of familiarity with the fundamentals of 8 dynamical systems theory (or ergodic theory), which requires some basic under standing of measure theory. We will include a few helpful background material definitions as they are needed, but mostly we will provide references. A very good introduction to the study of chaotic systems is Lasota and Mackey's book Chaos, Fractals, and Noise [11]. For a more detailed introduction to ergodic theory (along with the necessary measure theory needed to understand this thesis), Peter Wal-ters's book An Introduction to Ergodic Theory [24] and Karl Petersen's book Ergodic Theory [18] are highly recommended. Definition 2 (Probability Space). If B is a cr-algebra on subsets of a set X and if m is a measure on B where m(X) = 1, then the triple (X, B, m) is called a probability space. (See [24, pp. 3-9] and [11, pp. 19-31] for a good overview of basic measure theory and Lebesgue integration.) Definition 3 (Stationary Distribution). Let (X, B, m) be a probability space, let P be the Perron-Frobenius operator associated with a non-singular transformation T : X —>• X, and let L1 denote the Ll space of (X,B,m)^. If / € L1 is such that Pf = ft then / is called a stationary distribution of T. Definition 4 (Perron-Frobenius operator). For a probability space (X,B,m), the Perron-Frobenius operator associated with a non-singular transformation T : X —)• X is defined by f Pf(x) dm = [ f{x) dm, for B e B . JB JT-^B) For a piecewise C2§ transformation T with n pieces, we can give an explicit formula for the Perron-Frobenius operator. Let A = {Ai,A2,... ,An} be the parti tion of X which separates T into n pieces. For i € {1,..., n}, let ti(x) represent the *For a probability space (X,B,m), the L1 space of (X,B,m) is the set of / : X -> E satisfying Jx \f(x) \ dm < co. *The o symbol will be used to indicate that a given relation holds except possibly on a set of measure zero. §C2 denotes the set of all functions with two continuous derivatives. 9 natural extension of the ith. C2 function T(x)|^i. The Perron-Probenius operator for T is then In particular, for To (as in equation 1.1), Pf{x) = \f{\x)-lm{x) + \f{D - \x) • l(0,2D-i](aj) + \f{D + \x) • l[0l2-2D)(^ • (1-2) With equation 1.2 we can show precisely what happens to an initial dis tribution of points (described by an integrable function) after they are repeatedly transformed under Try. Figures 1.6 and 1.7 show what happens to two different initial distribution of points after five applications of the Perron-Frobenius operator associated with T3/5(z). By the fifth application, the distributions look remarkably similar. One might guess that they are both approaching the same final distribution. This situation is in marked contrast to chaotic behaviour observed in figures 1.4 and 1.5. tll{x) dx f(t-\x))-lu[Ai){x) 10 2 1.5 1 0.5 0 2 1.5 1 0.5 0 2 1.5 1 0 . 5 0 0 0.25 0.5 0.75 1 X CO 0 0.25 0.5 0.75 1 X lO 0. 0 0.25 0.5 0.75 1 a: 2 1.5 1 0. 5 0 2 1. 5 1 0 . 5 0 2 1.5 1 0.5 0 0 0.25 0.5 0.75 1 X 0 0.25 0.5 0.75 1 X 0 0.25 0.5 0.75 1 X ure 1.6: The result of applying the Perron-Frobenius operator P associated with T3/5 to f(x) = 1 six times. 11 2.5 2 ^ 1 0.5 0 2 1. 5 1 0.5 0 0 0.25 0.5 0.75 1 X CN 0 0.25 0.5 0.75 1 x 2 1.5 1 0.5 0 2.5 ^ 2 ^ 1.5 a, i 0.5 0 2 ^- 1.5 0.5 0 2 1.5 0 0.25 0.5 0.75 1 X 0 0.25 0.5 0.75 1 1 lO a, 0.5 0 0.25 0.5 0.75 1 X 0 0.25 0.5 0.75 1 Figure 1.7: The result of applying the Perron-Frobenius operator P associated 1 f1 • • with T3/5 to fix) = -—- / — six times. !og2 J1/2 x 1.3 Shift Average for D G [§, 1) An exact equation for the stationary distribution when D € [|, 1) was first given by Freiman [6] and is restated by Shively [22] as 1 1 /(z) = -Q\O,2D-\){?) + 2^1[2£>-i,i)(») • (1-3) To verify that this is a stationary distribution function, we begin by applying the Perron-Frobenius operator as given in equation 1.2 to equation 1.3 and verifying 12 that Pf(x) = f(x). So then, applying P to / we get Pf(x) = ^^l[o,2D-i)(H + 2^1[2i>-i,i)(5a;))1[o,i)(a;) + \ ^l[o,2i>-i)(-D - hx) + -fijL[2D-\,\){D ~ k)) l(0,2£»-i](a;) + \ ^l[0,2X?-l)(-D + \x) + 2^1[2D-l,l)P + \x)^j l[Q,2-2D){x) • Assuming that D € [5,1), and observing that a; € [0,1), Pf(x) = \ ^l[o,4D-2)(aj) + ^1[4D-2,i)(a;)) l[o,i)(a:) + £ ^1(2-2D,l)(a;) + ^1(0,2-2£>](2;)) l(0,2D-l](a;) + £ (^1[0,2D-1)(^ l[0,2-2O)(a;) • Finally, assuming that D € [|, 1), we have Pf(x) = 2^1[0,l)(a;) + 2^1(2-2D,2i3-l](^) + ^l(o,2-2D](a;) + 42jl[o,2-2D)(a:) 3 1 = ^1[0,2-2D)(^) + ^ 1(0,2-20] (*) + -^l[2-2D,2D-l){x) + ^T51(2-2D,2£)-l](a;) + 2^1[22>-i,i)(a0 = ^l[o,2D-i)(a;) + 2^1[2D-i,i)(a:) = /(») • One of the primary uses of having a formula for the distribution of partial remainders is for calculating the shift average for a given divisor. The shift average is the average number uses of the shift register (single shift or multiplication by two) between uses of the adder. Under the assumption that a register shift is a much faster operation than using the adder, the shift average gives a useful characterization of the expected performance of our algorithm for a given divisor. With equation 1.3, we know the fraction of bits that require the use of the adder. To calculate the average number of zero bits generated between non-zero bits (bits requiring use of 13 the adder), we take the reciprocal of the fraction of bits that require the adder. We calculate the shift average for a divisor D e [f, 1) to be •<">-I4 = *£T- (L4) Since have not proven that the stationary distributions from S-R-T division are unique, we have no way of knowing whether or not a shift average calculation in equation 1.4 is correct. To prove that all stationary distributions are unique, we need to show that TD is ergodic for all D G [^,1)- Freiman [6] shows that To is ergodic for rational D, but we extend this result for real D. In the next section we show that all are Bernoulli and it is known that having the Bernoulli property implies ergodicity. Before concluding this chapter with a definition for ergodicity, we will briefly comment on the derivation of stationary distributions for D G [|, f). For D G [|, |), the stationary distribution functions have been derived, and their associated shift average functions have been shown to be constantly three [6, 22]. The layout of stationary distribution functions in the region D G [j, §) has several surprising properties and is far from being fully understood. We discuss the calculation of shift averages as an interesting area for future investigation in Chapter 4. Definition 5 (Ergodic [11]). Let (X, B,m) be a probability space and let a non-singular transformation T : X —> X be given. Then T is ergodic if for every set B G B such that T~L{B) = B, either m(B) = 0 or m(X \B) = 0. 14 Chapter 2 Bernoulli Property In this chapter, we will prove that the class of transformations of the interval that characterizes the S-R-T division for all real divisors D has the property that each transformation TD is Bernoulli. Although the basic concept of a Bernoulli shift (the things to which transformations having a Bernoulli property are isomorphic to) is not difficult, a complete definition requires enough auxiliary concepts from measure theory (concepts not used anywhere else in this thesis) that we chose to refer the interested reader to [17, 18, 21, 24] and other selections listed in the Bibliography. Neither an understanding of Bernoulli shifts, nor a formal definition of what it means to be Bernoulli is required to follow the proofs in this chapter. Having said this, we should mention informally the connection between Bernoulli shifts and transformations having the Bernoulli property. The transformation TD is an non-invertible endomorphism of the unit inter val. This means that from a given partial remainder we can predict all future partial remainders, but we cannot uniquely predict past partial remainders. There is a nat ural way (called the natural extension) to make our transformation invertible (an automorphism) on a larger space. Specifically, each non-invertible transformation TD having the Bernoulli property has an extension to an automorphic transforma tion, isomorphic to a two-sided Bernoulli shift [18, pp. 13,276]. From the way that 15 entropy for a transformation is denned, the entropy for an automorphic Bernoulli transformation associated with a non-invertible Bernoulli transformation is the same as the entropy for the non-invertible Bernoulli transformation. By proving that all transformations Tp are Bernoulli, and by proving that entropy of each To is the same, we will be able to conclude that the natural extensions of S-R-T division algorithms are isomorphic to each other for all divisors. 2.1 Proof of Bernoulliness Definition 6 (of Bowen [1], Expanding). We will say that a transformation T on an interval is expanding if it has the property that supn>0 u-(TnU) = 1 for all open intervals U with p{U) > 0, where /i is any normalized measure that is absolutely continuous with respect to Lebesgue measure. Definition 7 (Straddle). Let U be an interval of reals (either open, closed, or half open) and let p G K+. If p G U°J then we say that U straddles p. Theorem 1. The S-R-T division transformation is expanding for all real divisors. Proof. Let (X,B,m) be a probability space where X = [0,1), B is the Borel o-algebra on X and m is the Lebesgue measure on H*. Let TD : X ->• X be the S-R-T division transformation for a given normalized divisor D as defined in equation 1.1. *The symbol o as the exponent of an interval denotes an open version of the interval. *For an interval [a, b], the Lebesgue measure is defined as m([a, b]) = b — a. 16 Let us define an infinite sequence of intervals U = {C/jjieN as Ui = U and C/°C[0,i) ort/?C[±,l) U° g [0, i) and (7° g [i, 1) and TD(C7in[0,i)) n[±,i)) m(C7i D [0, i)) >m(<7in[i,l)) tf?g[0,±)andtf?g[±,l) and n[o,i)) <m((7in[i,l)). Property 1. For all Ui such that \ U° and D g U°, m{Ui+i) = 2m{Ui). Proof. If a U° is a subset of either [0, [5,-D), or [D, 1), then we are in the first case of the U definition and we apply directly. Since each of the three cases of the TD expand an interval by a factor of two, it is clear that m(T£>(Ui)) = m(Ui+\) = 2m(Ui). Property 2. For all Ui where D 0 Ui, m(Ui+i) > m(Ui). Proof. Assume that D $ Ui. If j £ Ui, then according to Property 1, U{+\ doubles. Otherwise, \ 6 U{ and therefore, to find E/i+i, we must consider the second and third cases of the U sequence. In the worst case, m(Ui D [0, ^)) = m(Ui n [^,D)), and regardless of which half we choose, m(Ui fl [0, ^)) = m(Ui fl [5, D)) = ^m(Ui). By applying Trj to this truncated interval, we double what we halved so that m(Ui) = m{Ui+i). By way of contradiction, let us assume that there exists a sequence of U that never expands to fill X. Such a sequence can never include the point D and the following Property will hold: Property 3. There exists N such that for all i > N (a) m([/;n[0, ^)),m(Uif][^, 1)) > 0 (in other words, all subsequent intervals must straddle \), and 17 (b) m{Ui PI [0, \)) < m(Ui n 1)) (in other words, all subsequent Ui must be such that the right half of Ui is not discarded by the definition ofU). Proof of Property 3(a) Property 1 says that the only way not to double is to straddle ^. Therefore, at a minimum, it must be the case that ^ is eventually included every time or else the interval will double a sufficient number of times to include D which would be a contradiction. Proof of Property 3(b) If m{Ui n [0, |)) > m(Ui n [£, 1)), then we have Ui = {\ -e,\ + e') where e > e'. Now Ui+1 = TD{Ui) = TD(\ - e, \) = (1 - 2e, 1). But, since D is not in C/j+i, \ cannot be in t/i+i and Property 3(a) fails, resulting in a contradiction. By Property 3, we will eventually be in a situation where U{ = ( \ — e', \ +e), e' < e, and Property 3 will hold for every subsequent interval. So then Ui+i =TD{\-e',\+e) =TD[\,\ + e) = (2Z> - 1 - 2e, 2D - 1] by Property 3(b). But again by Property 3, Ul+2 = TD{2D - 1 - 2e,2D - 1] = TD[\,2D - 1] = [2 - 2D,2D - 1]. It is now clear that ^ is at the midpoint of Ui+2 and that we must now pick the left half of the interval which contradicts Property 3(b). Therefore, D will eventually be included in an interval and the sequence will expand to fill all of X. • We can now prove that the S-R-T division process is weak-mixing, and there fore Bernoulli, by two theorems of Bowen [1]. Theorem 2 (of Bowen [1]). Let T be a piece-wise C2 map of [0,1], [i be a smooth T-invariant probability measure, and A = infn<x<i |/'0c)| > 1- U dynamical system (T, /j,) is weak-mixing, then the natural extension of (T, p) is Bernoulli. 18 We mention here that the natural extensions of (T, n) is the associated au-tomorphic transformation that we alluded to at the beginning of this chapter. See Petersen [18, p. 13] for an exact definition. Theorem 3 (of Bowen [1]). With T and /i as in Theorem 2, (T,n) will be weak-mixing ifT is expanding. Theorem 4 (of Lasota and Yorke [10]). Let (X,B,m) be a probability space and let T : X —>• X be a piecewise C2 function such that inf \T'\ > 1. If P is the Perron-Frobenius operator associated with T, then for any f G L1, the sequence (n Sfc=o -ffc/)n^=i ?s convergent in norm to a function f* € L\. The limit function f* has the property that Pf* = f* and consequently, the measure d/Lt* = /* dm is invariant under T. Having established that TD is expanding, we now use the above three theo rems to prove the central result of this thesis. Theorem 5. TD is Bernoulli. Proof. From the definition of To, we see that TD is C2 and that info<x<i |TD'(:E)| = 2 > 1 since \TD'(X)\ = 2 for all x for which the derivative is defined. Since infn<x<i \TD'(X)\ > 1, by Theorem 4 there exists at least one \x such that fi is a smooth To-invariant probability measure. By Theorem 1, we see that Theorem 3 holds. Hence, (TD,U-) is weak-mixing and, by Theorem 2 (To,^) is Bernoulli. • 2.2 Entropy of TD Knowing that all To are Bernoulli is a very useful property because we can use en tropy as a complete invariant to show isomorphism amongst the two-sided Bernoulli shifts associated with To that have the same entropy. This comes from the contri bution of Ornstein to the Kolmogorov-Ornstein Theorem. 19 Theorem 6 (of Kolmogorov [8, 9] and Ornstein [16]). Two Bernoulli shifts are isomorphic if and only if they have the same entropy. The purpose of this section is to calculate the entropy of Tp. We begin with a multi-part definition of entropy along with some supporting definitions that follow the development presented by Walters [24, pp. 75-87]. Definition 8 (Partition). A partition of (X,B,m) is a disjoint collection of ele ments of B whose union is X. Definition 9 (Join). Let V and Q be finite partitions of (X, B, m). Then ?VQ = {PnQ : P G V, and Q 6 Q} is called the join of V and Q. Note that V V Q is also a finite partition of (X, B, m). Definition 10 (Entropy of a partition). Let (X,B,m) be a probability space and let V = {Pi,...,Pk} be a finite partition of (X,B,m). The entropy of the partition is defined as Definition 11 (Entropy of a transformation with respect to a partition). Suppose T : X —> X is a measure-preserving transformation of the probability space (X, B, m). If V is a finite partition of (X, B, m), then is called the entropy ofT with respect to partition V. Definition 12 (Entropy of a transformation). Let T : X —> X be a measure-preserving transformation of the probability space (X, B,m) and suppose h(T) = sup/i(T, V), where the supremum is taken over all finite partitions V of (X,B,m). Then h(T) is called the entropy ofT. k H(V) = -^miPi) log m(Pi). 20 The following definitions and theorems involving C-maps and PC-maps are taken from a paper of Ledrappier [12] and have been streamlined for our argument. Definition 13 (of Ledrappier [12], C-map). A real function / defined on an interval [a, b] is said to be a C-map if / is continuously differentiable and its derivative /' has the following properties: (a) /' satisfies a Holder condition^ of order e > 0. (b) There are only a finite number of points x G [a, 6] where f'(x) = 0. We denote them by a < a\ < a2 •.. < an < b with /'(a;) = 0 for 0 < i < n. (c) There exist positive numbers k~ (kf) such that a left (right) neighborhood of a;. Definition 14 (of Ledrappier [12], PC-map). A map / : [0,1) —> [0,1) is called a PC-map if there exists a finite partition 0 < b\ < b2 .. • < bm < 1 such that / is a C-map from [bj,bj+i] into [0,1), for any j. Theorem 7 (of Ledrappier [12]). Let f be a PC-map. If \i is an a.c.i.m. (abso lutely continuous invariant measure), then Rohlin's formula [20] is true: Hf) = j log|/'|d/i. Theorem 8. The entropy h{TD), ofTD for D e [^,1) is equal to /log|To'| d/z = log 2. Proof. We begin by showing that To is a PC-map. By the definition of a PC-map, Tp is a PC-map if each of the three functions Tu\^Q ij ,T!D|[1 Dy and To\yD ^ is a C-map. Trivially, each Try restricted to any of the three domains [0, |), or [D,l) satisfies a Holder condition of order e = 1 because each piece of To is just a §A function f(x) defined on an interval [a, b] satisfies a Holder condition of order e E K+ if there exists c 6 R+ such that for any two points pi,P2 G [a,b], \f{pi) — f(p2)\ < c\pi - P2\e• 21 log 1 ,k |x—a| -(+) is bounded in line of slope two. Thus condition (a) of Definition 13 is satisfied. Condition (b) is satisfied because there are no points for which the derivative is equal to zero within a given line segment. Therefore, condition (c) is trivially satisfied. Thus each of the three segments of TD are C-maps and by Definition 14, To is a PC-map. Now, since each TD is Bernoulli, there exists a unique a.c.i.m., call it /z, for each To- By Theorem 7, we can use Rohlin's formula to calculate the entropy: With the proof of Theorem 8 we have established isomorphism amongst the automorphic transformations (or natural extension) associated with simple S-R-T division transformations by an application of the Kolmogorov-Ornstein Theorem. The key to obtaining this result was being able to show that TD has Bowen's ex panding property. In Chapter 3, we extend the results of this chapter to a more general type of S-R-T division. • 22 Chapter 3 Extensions to Multi-Divisor S-R-T Division 3.1 Multi-Divisor S-R-T Division A common optimization to the S-R-T division algorithm is the inclusion of additional divisors to increase the shift average. In this section, we prove that all such division algorithms with reasonable assumptions on the separation of the divisor multiples have the expanding property. It will be useful to define precisely a class of multi-divisor S-R-T division transformations. Definition 15. Let a G W1 be such that (a) 0 < ai < a2 < • • • < an, and (b) For all x,D e [|, 1), there exists i G {1,..., n) such that \c<iD — x\<\. We define 2l„ to be the set of all a G Rn, satisfying conditions (a) and (b). Also, Definition 16 (Peaks and Valleys). Given an a G 2lN>2, the point of intersection between two lines f(x) = 2(x - ctiD) and g(x) = 2(ai+iD - x) will be called a peak 23 and is denoted by ipi = (^D(cti+i + ati), D(a{+i — a;)). For convenience, we will refer to the abscissa as ipf = ^D(oti+i + aj), and to the ordinate as ipf = D{a.i+\ — aj). The point of intersection of the two lines f(x) = 2{aiD — x) and g(x) = 2(x — otiD) is (cxiD,0) and will be called a valley. Definition 17. For aDe and Q 6 21, define the transformation Tr),a(x) : [0,1) —* [0,1). For a S 2ti, we get the familiar transformation TDAX) = 2x \2(D-x)\ 0 < X < i < X < 1 . For a € 2l2, 2x \2{aiD-x)\ \2{a2D-x)\ For a € 2ln>3, 2x \2(aiD-x)\ \2(aiD-x)\ \2{anD-x)\ Q<x<\ i < x < ipf \ < x and ipf < x < 1. 0 < x < \ \ < x < ipf \<x and ipf < x < tpf+1 \ < x and ipn-i <x<l. Definition 18. Define Wln = {TDi(X : D <E (±,1], a € 2tn} and define iW = UneN^n- We can *ne set °^ an n-divisor S-R-T division transformations and we call iVd the set of multi-divisor S-R-T division transformations. Condition (b) in Definition 15 guarantees that the division algorithm gener ates a new quotient bit every step. Although the condition makes intuitive sense, it is not immediately obvious if an a satisfies the condition just by inspection. Lemma 10 below provides an easier way to check. 24 Lemma 9. If a = (ai), then condition (b) of Definition 15 is satisfied if and only if ai = 1. Proof. If a\ = 1, then maxjr>]Xe[i/2,i) \a\D — x\ < |. Now consider the cases when «i ^ 1 and e G M+. If ct\ = 1 + e, then when D = and x = \, \OL\D — x\ = 1 — i = i ^ i. On the other hand, if ct\ = 1 — e, then when D = \ and a; = 1 — |, |ai£> -x| = 1 - | - (1 -e)± = i ^ \. • Lemma 10. An a G 2ln satisfies condition (a) of Definition 15 also satisfies condition (b) if and only if for some i,j G {1,... ,n} (possibly i = j), either (i) a{ € (0,7?] and otj € [1,1 + a*], or (MJ a» € [^,1] a^c? € [l,3«i]. Proof (Sketch). Lemma 9 has shown that a single component a of a with a = 1 is sufficient to ensure that the range of f(x) = 2 \aD — x\ is equal to [0,1) as x and D range over [5,1). It is easy, to see based on the proof of Lemma 9 that if there does not exist i 6 {1,... ,n} such that ai = 1, then there must exist i,j 6 {1,... ,n} (i < j) where OJJ < 1 and a3 > 1. Let us assume that i is the largest value where CKJ < 1, and let us assume that j is the smallest value where ctj > 1 (therefore j = i + 1). We make this assumption because no other scalars of D will have an influence on whether or not condition (b) is satisfied. Consider the case where c*j G (0, ^]. In this case where ai 6 (0, |], when D is close enough to 1, some of the line f(x) = 2(x — aiD) appears in the region (denoted R) where \ < x < 1, 0 < Ta(x) < 1. When a portion of the line f(x) appears in region R, we must put restrictions on aj in terms of ai so that the peak ?/>! is always in R. ipf is greatest when D = 1. We find the maximum allowable value of aj by setting D = 1 and solving ipf = 1 for aj: ipf = I => D(aj - ai) = 1 aj = a; + 1. Therefore, if a; G (0, then G [1,1 + aj]. 25 In the case where aj € [^, 1], for large enough values of D, the line f(x) = 2(x — Dai) crosses the line x = 1 in the range [0,1). Because of this, we must loosen the restriction that ctj G [1,1 + ctj]. It is straightforward to calculate that f(x) begins to cross the line x = 1 in the range [0,1) when D = We can ensure that as D becomes smaller, the peak ipi will always be in region R by solving tpf = 1 for ctj when D = tp\ = 1 D(aj - on) = 1 => 7f—((Xj - on) = 1 =4> ctj = 3at. Therefore, if ai € [^, 1], then ctj £ [1, 3aj]. • Definition 19 (Separation). For a € 2ln, we define the separation in a as separation(a) = max 1+1 . i€{l,...,n-l} ttj Limiting the separation is a convenient way to restrict the subset of 21 being consid ered. If separation(a) = r, we say that "the divisor multiples in a are separated by at most a factor of r." Figure 3.1 shows an example of multi-divisor S-R-T division. This example is performing the same calculation as in figure 1.2, but it has computed the dividend with twice as many digits of precision with the same effective number of uses of the adders. We say "effective" because in multi-divisor S-R-T division, there are several adders working in parallel. In a real implementation of multi-divisor S-R-T division, the values for a must be carefully chosen so that not too much overhead is required to select a good partial remainder. There is also a tradeoff between the amount of overhead in choosing a good partial remainder and the precision to with which a good partial remainder is selected. 26 Po = 0.67 0.67 Pi = 2(0.67 - a2D) -0.16 Qo = Qo = 1 P4 = 2(22(-0.16) + anD) = -0.155 Q3 = -ax Qz = 0.90625 P7 = 2(22(-0.155) + axD) = -0.115 <76 = Q6 = 0.89453125 Pll = 2(23(-0.115) + a3D) = 0.035 9io = -«3 Qw = 0.8933105469 Pl6 = 2(24(0.035) - axD) = -0.005 Qis = Ql5 = 0.8933334351 P24 = 2(27 (0.005) + axD) = -0.155 923 = Q2S = 0.8933333456 Figure 3.1: An example of S-R-T division where three multiples of the divisor are used. In this example the dividend po — 0.67, and the divisor D = 0.75 with divisor multiples a = (0.75,1,1.25). The quotient Q* is 0.893. 3.2 Proof of Bernoulliness In this section, we will show that all multi-divisor S-R-T division transformations are Bernoulli, given a necessary restriction on the multiples of the divisor. As in the case for a single divisor, it will be useful to define a sequence of intervals that are subsets of the sequence of sets that would arise from repeatedly applying TD,Q. to an initial open interval. Unless otherwise noted, assume that the function m denotes the Lebesgue measure. Definition 20. Given an initial open interval U C [0,1) and To^a G 9DT, we define 27 the infinite sequence of intervals U = {Ui}^ as Ui = U and TD,a(Ui) TD,a(Ui n [0, i)) C/°C[0,i) orC7?C[i,l) t/° £ [0, and t/? g [i, 1) and T^a^i n[i,i)) m(f/<h[0,i)) >m{Uif\{\,\)) U°%%\) and C7? g[±,l) and m(f7in[0,i)) <m(f/in[i)l)). Definition 21 (Critical Points). For a given Tu,a where a € 2ln, define the set where 5 = {& : i < & < 1 and b G {ai-D, • • •, an-D} U Of, • • •, V>n-i}} and ci < C2 < ... < 1. C is called the set of critical points for To)a. Lemma 11 (Doubling). GivenTr),a £ ^ ^e sequence of intervals U be defined as in Definition 20 and let Ui be some interval in the sequence. Furthermore, let C = {ci,... ,cm} be the set of critical points for TD,«. If Ui C [CJ,CJ+I] for some j G {1,... ,ra- 1}, then m(Ui+i) = 2m(Ui). Proof. Since Ui C [CJ,CJ+\] for some j £ {l,...,m-l}, because we are in the first case of the definition of U, either U? C [0, \) or U° C [i, 1). By simple inspection of the individual cases that define Trji(X, it is apparent that all of Ui, except possibly the points Cj and Cj+i, fall within the same case of Tr),a- Therefore, the resulting interval Ui+i will be double the length of Ui. • Definition 22 (Active Valleys). Given TDt(X € 93Tn, define V = {ctiD : i 6 {1,..., n) and \ < atD < 1} . V is called the set of active valleys for To,a-C = {Ci : i 6 {1, • • •, m}, a E B U {0, ±, 1}} 28 Definition 23 (Active Peaks). Given Tn,a G Tln, define P = {if>f : te{l,...,n-l} andi<^f<l}. P is called the set of active peaks for To,a-Lemma 12 (Non-shrinking). Given TD,OC G with separation(a) < |, let the sequence of intervals {Ui}i^ be defined as above and let V denote the set of active valleys for Trj,a. For any interval Ui G U such that V fl Ui = 0, either m(Ui+i) > m(Ui) or m(Ui+2) > m(Ui). Proof, separation(a) < | implies that cti+\ < For a given separation, the value of ip\ is maximized when ipf = 1. This implies that aj = We calculate the value of ipf with the assumption that ipf = 1 to get a bound on ipf for D < 1: iPf < D(lai - ai) = D(lai) = £>(§&) = 5 • Case 1: Consider when Ui C [0, \]. In this case, m(Ui+\) — 2m(Ui). Case 2: Consider when Ui C [^,1). The interval Ui can span at most one peak. Therefore, m(£/j+i) > m(Ui). A further observation is that since Ui+i C [0, m{Ui+2) = 2m{Ui). Case 3: Consider when Ui £ [0, \] and Ui % 1). In this case, Ui straddles \. From the definition of U, we see that in the worst case we might throw away up to half of Ui. Call the part not thrown away Ui and observe that m(Ui) > \m(Ui). Now, either Ui' C [0, \) or Ui' C [i, 1). If [// C [0, ±], then m(C/i+i) = 2m(<7;') > m{Ui). If t/i' C [i, 1), then m(C/i+2) = 2m(£//) > m(c/;). • Lemma 13. A multi-divisor S-R-T division transformation Tr>,a G 9JI is expanding when separation(a) < |. Proof. Let V be the set of active valleys (as defined in Definition 22) for a Trj,a- Let P be the set of active peaks (as defined in Definition 23) for a To,a- Let U = {Ui\i^n be the sequence of intervals associated with a To,a and an initial interval U. 29 By way of contradiction, assume that a T£>>a is not expanding. This means that for some Trj,a, there does not exist an interval Ui where any of the points in V are contained in Ui. This is true because if any of the valley points are in Ui, then Ui+i = [0, e) or C/j+1 = [0,e], and after a finite number of steps, Ui will have grown to include all of [0,1). If there is a sequence U that avoids all points in V, then by Lemma 12 it must be true that the intervals in the sequence can only double a finite number of times. Let ieNbe the first index for which there is no j > i such that m(Uj) > 2m(Ui). It now follows that Ui straddles ^. The proof for Lemma 12 reveals that this is the only situation where it is not necessarily the case that either m{Ui+\) = 2m{Ui) or rn(Ui+2) = 2m(Ui). In fact, Ui must straddle both \ and minP. If minP is not straddled and m(Ui fl [0, ^)) < m(Ui fl [|,1)), then either m(Ui+2) > 2m([/j) or m(Ui+z) > 2m(Ui). In the other possibility where minP is not straddled and m(Ui n [0, ^)) > m{Ui n [1,1)), we find that m(Ui+2) > 2m{Ui). Assuming that Ui straddles both ^ and minP, we also observe that there can be no j > i such that m(Uj D [0, 5)) > m(Uj fl [5,1)) because this quickly leads to doubling. In other words, the right side must be larger than the left side whenever we straddle |. Therefore, we must be in the situation where t/i = (i-e',i + e), e'<£ Ui+i = (min{2(i - aiD),2(ai+lD-Ul+2 = (2min{2(i - aiD),2(ai+1D _(i+e))}, 2^?) ui+3 = (min{2(i - aiD),2{ai+1D- 2vf)},^r) Ui+4 = (2min{2(i -aiD),2{ai+1D -2ltf)},2#) => Ui+5 = (min{2(i - aiD),2{ai+1D- 2^)},^) = l7i+3 It is apparent that the interval represented by [/j+4 will re-occur every other interval ad infinitum. We now use this interval to show that in fact such a sequence of non-expanding intervals is not possible. 30 Since straddles \, we can compare the length of the left and right sides of J7j+4. Let R = [^,2i/>f) denote the right side and let L = (4(^ — o^-D), \) and V = (4(cti+iD — 2ipy), ^) denote the two possibilities for the left side. The length of the right side is m(R) = 2Vf - i, while the length of the left side is the larger of two possible lengths m(L) = \ - 4(i - aiD) and m(L') = i-4(ai+i£>-2^) . We then compare the differences between the right side and each of the two possible left sides. The first possibility is m(R) - m(L) = 2$ - I - (I - 4(i - atD)) = 2D(ai+l -ai)-1 + 2- 4a{D = 2ai+1D - GctiD + 1 , while the second possibility is m(R) - m(L') = 2^f - ± - (± - 4(al+1 - 2$)) = 2D{al+x - ai) - 1 + 4{al+1D - 2D{al+1 - at)) = -2ai+iD + 6aiD - 1. It is now clear that m(R) - m(L) = - (m{R) - m(L')) . But this means that the length of the left side is always greater than or equal to the length of the right side, which contradicts our assumption that the right side must be bigger than the left side whenever the interval straddles ^. • 31 Theorem 14. To,a G %Jl is Bernoulli when separation(cx) < |. Proo/. Let T = Toia. From the definition of T, we see that To>a is C2 and that info<x<i |T'(a;)| = 2 > 1 since |T'(x)| = 2 for all x for which the derivative is defined. Since info<x<i |T"(a;)| > 1, by Theorem 4, there exists at least one /z such that zz is a smooth T-invariant probability measure. By Lemma 13 we see that Theorem 3 holds when separation(a) < §. Hence, (T, /z) is weak-mixing and by Theorem 2, (T,/z) is Bernoulli when separation(a) < |. • 3.3 Some Restrictions on ex. In section 3.2, we showed that if all TD)Q G 9Jt, if separation(a) < §, then TD>OC is Bernoulli. In this section, we construct examples of T G %Jln, for every n, that fail to be Bernoulli when the restriction that separation(a) < § is relaxed. Theorem 15. For TD,O. G ffin>4, if separation(a) > §, then for each D G [|,1), i/iere ea;zsr; uncountably many a. for which Tut0l is not ergodic. Proof. We begin this proof by considering T G 9Jln=4-Assume that we relax the restrictions on a by e > 0. This means that separation(a) < | + e and that no peak can be above the line f(x) = With this relaxation, we can define a = (c*i, a2,0:3,0:4) with respect to a given D so that a subset of [0,1) is non-expanding. We let ai = 80g+48D£ > a2 = 8or>+48£>e' 0:3 = 40C+294£Pe1 an(^ a4 = 40P+24Pe • ^or our constructed a to be valid, we must be careful that conditions (a) and (b) of Definition 15 hold. Condition (a) requires that the components of a remain in ascending order. This is satisfied when e G (0, ^]. Since ordering is maintained, separation(a) < 3, and minrjg[i/2,i),ee(o,2/i5] a4 = 1-2 > 1, to verify that condition (b) of Definition 15 holds, it is sufficient to show (by Lemma 10) that for all values of D and e, either ot\, a2, or a3 G [5,1]- By maximizing and minimizing over e and D, we find that a\ G [0.375,0.7] and a2 G [0.625,1.3]. Figure 32 3.2 provides a visual proof that as e is varied over [0, ^] and D is varied over [5,1], Having verified that our defined a satisfies Definition 15, we calculate that peak ^ = (i±if, l{j±if§) and peak </>3 = (f^, ftl||). With this definition for while remaining above the line g(x) — ^, and the point ip1 will always be slightly chosen so that we are in a situation where 1 — ip% = ^3 ~~ \ — 2(V'i ~~ \) = 2{ip\ — |)-Another important feature in this construction is the interval between a2D and a^D. Since ip2 is not used in our construction, it is possible to insert an arbitrary number of divisor multiples between a2D and a3D. Thus, the results in this proof apply to T G 9Jt„ for arbitrarily large n. Figure 3.3 illustrates the type of transformation that we have constructed. We are now in a position to show that there exists a set of points A with 0 < m(A) < 1, for which TD,OL{A) = A. This is the definition of a transformation being non-ergodic [11, p. 59]. Define A = A\ U A2 U A3 where A\ = [\ - (ipf -5). i + w - A* = [h- m -M+m - h)iand 4. = [i - 2(1 - 1]. It can be shown by calculation that To]a(Ai) = A2, T^A^) = A\ U A3, and TD,OL{M) = A2. Therefore, TD,CI(A) = A, and by definition, To,a is non-ergodic or it is never the case that both a\ < \ and a2 > 1. Therefore, it is always the case that either a\ or a2 G [5, !]• below f(x) while remaining above the line g(x) = \. All of the definitions have been non-expanding. • 33 Figure 3.2: Combined plot of the regions where a\(e,D) < \ and ct2{e,D) > 1. Over the domain e 6 [0, ^] and D € [\, 1], it is never true that both ct\ < \ and «2 > 1-X Figure 3.3: An example of a non-ergodic system for Trja € 9Jt„>4- In this ex ample n = 4, D = a = (||, 1, ||), and separation(a) = | + j^-. The thick lines represent Trj]a. The coarse dashed line represents the necessary separation restriction on a to guarantee that TD)Q is ergodic. In this case, partial remainders in the set A = §] u tl> I] u (it. !) are mapped back to A by TD,a. This means that TD)Q. is not ergodic, and therefore not Bernoulli. 34 Theorem 16. For To,a G 9Jt3) if separation(a) > |, then for each D £ [5,1), there exists an a for which Toia is not ergodic. Proof. The proof for this theorem comes as a special case from the proof for The orem 15. Consider a = (oti, 0:2, 0^3,0^4) as defined in the proof for 15. When separation{a) = | = | + we are in the special situation where a2 = 0:3. Since all of the results for the proof of Theorem 15 still hold, we now have an example transformation T with only three unique multiples of D and this T has been proven to be non-ergodic. Figure 3.4 gives an example of a non-ergodic transformation for D = l2. • 0 0.25 0.5 0.75 1 X Figure 3.4: An example of a non-ergodic system for To,a £ 9^3- In this example, D = and « = (§> f> if)- Tne tmc^ unes rePresent I'D,a- The coarse dashed line represents the necessary separation restriction on a to guarantee that To,a is ergodic. In this case, partial remainders in the set A = [±, ^]U[^, i§My§, 1) are mapped back to A by TD,a. This means that Trj,a is not ergodic, and therefore not Bernoulli. 35 Theorem 17. For Trj,a € 9#2, if separation(a) > 3, then for some D G (^,1), there exist uncountably many a for which TD>(X is not ergodic. Proof. Assume that separation(a) < 3 + e and D G {\, ^p). First, we choose ai = jjj so that aiD = | and a2 = 1 + OL\. Our restriction on D in terms of e has been chosen so that a2/a\ < 3 + e when 0:2 = 1 + «i- Since 02 > condition (a) of Definition 15 is satisfied. Since a\ G (\, 5), and a2 G (1,1 + a\], by Lemma 10, condition (b) of Definition 15 is satisfied. Thus, our defined a is always valid. Define A = [±, D]. We now apply T = TD>a to A: T[i, D] =[min{2(i - aiD),2(a2D - £>)},^] =[min{2(± - 4%), 2(D + \ - D)},D(a2 - ai)] =[min{I,i},D(l + 4^-4^)] Now, since \ < D < 1, 0 < m(A) < 1 and TDt(xA = A, by Definition TD]a is not ergodic. • 36 X Figure 3.5: An example of a non-ergodic system for Trj,a S 93?2. In this example, D = | and a = (^, ^). The thick lines represent Tr>,a- The coarse dashed line represents the necessary separation restriction on a to guarantee that Ta is ergodic. In this case, partial remainders within the interval [|, |] map back to |] and which means To,a is not ergodic, and therefore not Bernoulli. 3.4 Entropy of Multi-Divisor S-R-T Division The calculation for entropy in multi-divisor S-R-T division follows the same method used for single divisor S-R-T division. We begin by showing that To,a is a PC-map. Lemma 18. TrjtOC eiVl is a PC-map (as defined in Definition 14)-Proof. By inspection, each To,a is a finite collection of line segments each with slope 2. Each of these line segments is a C-map by the same argument used in the proof for Theorem 8. Therefore, by definition, each To,a is a PC-map. • Theorem 19. The entropy of any TD>(X S 9^ with separation(a) < | is log 2. 37 Proof. By Lemma 18, all To,a G 9Jt are PC-maps. By Theorem 14, TD,<X is Bernoulli when separation(ot) < | and hence there exists a unique a.c.i.m. /J. Theorem 7 says that Rohlin's formula for the entropy is true and therefore: h{TD,a) = J log |Tb,a'| dii = log 2^ dfi = log 2. • 38 Chapter 4 Future Work The original question that inspired this thesis was "Is simple S-R-T division ergodic for all real divisors?" In pursuing the answer to this problem, we discovered that not only is simple S-R-T division ergodic for all divisors, but it is also Bernoulli. Having established a Bernoulli property, and having calculated the entropy for our transformations, we were able to use the Kolmogorov-Ornstein theorem to conclude that our transformations are isomorphic to each other. In proving these important properties for simple S-R-T division, we made extensive use of more general results from dynamical systems theory. Consequently, our results were shown to be easily extensible to more general division systems. In general, it is difficult to prove that a particular class of transformations are ergodic or Bernoulli. Our results have provided an effective means of proving both of these properties for a large class of S-R-T-like division algorithms. Prom the standpoint of understanding an algorithm's expected performance, it is necessary to know that when a stationary distribution is found, it is unique. Having established the uniqueness of stationary distributions, the next step is to find the actual stationary distribution for as wide a class of transformations as possible. In section 1.3, we verified a known expression for the stationary distribution function for TD where D e [|, 1). In addition, many of the stationary distribution functions 39 have been classified by Shively and Freiman for D G [§, §], although the derivations are not nearly as simple as for D G [§, 1). It turns out that things become very complicated when D G [^, §]. In his thesis [22], Shively shows many interesting properties for the stationary distribution functions in this region. For example, he shows that there are many different intervals of D where there are an infinite number of different stationary distribution equations. As such, the graph of the shift average for D G [5, |] is far from complete and appears to have a°complex pattern (from the few points that have been plotted in this region). This is surprising considering the simplicity of the underlying transformation. A better understanding of this final region of simple S-R-T division would be an interesting goal to pursue. In the work of Freiman [6], it was first shown that the shift average for D G [|, |] is constantly 3, which can be easily shown to be the maximum possible shift average. This property was then used by Metze [15] to obtain a version of S-R-T division that has an expected shift average of 3 for all divisors. Another area to pursue would be to explore shift averages for multi-divisor S-R-T division and, if other plateaus are found, they could possibly be used to obtain higher expected shift averages for all possible divisors. Undoubtedly, obtaining a complete understanding of the stationary distribution functions for multi-divisor division would be even more difficult than it is for simple S-R-T division. It is possible that such results in this area could lead to improvements in modern S-R-T division. Related to this, it would be interesting to attempt to extend the results of this thesis to modern S-R-T division. 40 Bibliography [1] Rufus Bowen. Bernoulli maps of the interval. Israel J. Math., 28(1-2):161-168, 1977. [2] Abraham Boyarsky and Pawel Gora. Laws of chaos. Birkhauser Boston Inc., Boston, MA, 1997. Invariant measures and dynamical systems in one dimension. [3] Joseph F. Cavanagh. Digital Computer Arithmetic: Design and Implementa tion. McGraw-Hill, New York, NY, 1984. [4] J. Cocke and D. W. Sweeney. High speed arithmetic in a parallel device. Technical report, IBM, February 1957. [5] Milos D. Ercegovac and Tomas Lang. Division and square root: digit-recurrence algorithms and implementations. Kluwer Academic Publishers Group, Norwell, MA, USA, and Dordrecht, The Netherlands, 1994. [6] C. V. Freiman. Statistical analysis of certain binary division algorithms. Proc. IRE, 49:91-103, 1961. [7] D. Harris, S. Oberman, and M. Horowitz. SRT division architectures and implementations. In 13th IEEE Symposium on Computer Arithmetic: proceed ings, July 6-9, 1997, Asilomar, California, USA, volume 13 of Symposium on Computer Arithmetic, pages 18-25. IEEE Computer Society Press, 1997. [8] A. N. Kolmogorov. A new invariant for transitive dynamical systems. Dokl. Akad. Nauk SSSR, 119:861-864, 1958. 41 [9] A. N. Kolmogorov. Entropy per unit time as a metric invariant of automor phisms. Dokl. Akad. Nauk SSSR, 124:754-755, 1959. [10] A. Lasota and James A. Yorke. On the existence of invariant measures for piecewise monotonic transformations. Trans. Amer. Math. Soc, 186:481-488 (1974), 1973. [11] Andrzej Lasota and Michael C. Mackey. Chaos, fractals, and noise. Springer-Verlag, New York, second edition, 1994. Stochastic aspects of dynamics. [12] Frangois Ledrappier. Some properties of absolutely continuous invariant mea sures on an interval. Ergodic Theory Dynamical Systems, l(l):77-93, 1981. [13] Tien Yien Li and James A. Yorke. Ergodic transformations from an interval into itself. Trans. Amer. Math. Soc., 235:183-192, 1978. [14] O. L. MacSorley. High-speed arithmetic in binary computers. Proc. IRE, 49:67-91, 1961. [15] Gemot Metze. A class of binary divisions yielding minimally represented quo tients. IRE Trans, on Electronic Computers, EC-ll:761-764, Dec. 1961. [16] Donald S. Ornstein. Bernoulli shifts with the same entropy are isomorphic. Advances in Math.,.4:337-352, 1970. [17] Donald S. Ornstein. Ergodic theory, randomness, and dynamical systems. Yale University Press, New Haven, Conn., 1974. James K. Whittemore Lectures in Mathematics given at Yale University, Yale Mathematical Monographs, No. 5. [18] Karl Petersen. Ergodic theory. Cambridge University Press, Cambridge, 1983. [19] J. E. Robertson. A new class of digital division methods. IRE Trans. Electronic Computers, EC-7:218-222, Sept. 1958. 42 [20] V. A. Rohlin. Exact endomorphisms of a Lesbesgue space. Amer. Math. Soc. Transl., 39, 1964. [21] Paul Shields. The theory of Bernoulli shifts. The University of Chicago Press, Chicago, Ill.-London, 1973. Chicago Lectures in Mathematics. [22] Robert Shively. Stationary distribution of partial remainders in S-R- T digital division. PhD thesis, University of Illinois, 1963. [23] K. D. Tocher. Techniques of multiplication and division for automatic binary computers. Quart. J. Mech. Appl. Math., 11:364-384, July-September 1958. [24] Peter Walters. An introduction to ergodic theory. Springer-Verlag, New York, 1982. 43
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- S-R-T division algorithms as dynamical systems
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
S-R-T division algorithms as dynamical systems McCann, Mark A. 2002-08-13
pdf
Page Metadata
Item Metadata
Title | S-R-T division algorithms as dynamical systems |
Creator |
McCann, Mark A. |
Date Issued | 2002 |
Description | 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. |
Extent | 1827172 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
File Format | application/pdf |
Language | eng |
Date Available | 2009-08-13 |
Provider | Vancouver : University of British Columbia Library |
Rights | 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. |
DOI | 10.14288/1.0051671 |
URI | http://hdl.handle.net/2429/12179 |
Degree |
Master of Science - MSc |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 2002-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-ubc_2002-0175.pdf [ 1.74MB ]
- Metadata
- JSON: 831-1.0051671.json
- JSON-LD: 831-1.0051671-ld.json
- RDF/XML (Pretty): 831-1.0051671-rdf.xml
- RDF/JSON: 831-1.0051671-rdf.json
- Turtle: 831-1.0051671-turtle.txt
- N-Triples: 831-1.0051671-rdf-ntriples.txt
- Original Record: 831-1.0051671-source.json
- Full Text
- 831-1.0051671-fulltext.txt
- Citation
- 831-1.0051671.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051671/manifest