Web site templates - 4.6.3 EVALUATION OF POWERS 447 In terms of
4.6.3 EVALUATION OF POWERS 447 In terms of these functions, the binary addition chain for n requires exactly x(n) + u(n) -1 steps, and (5) becomes l(n) 5 x(n) + v(n) -1. (10) Special classes of chains. We may assume without any loss of generality that an addition chain is ascending, 1 = %I < Ul < a2 < .. < a, = n. (11) For if any two a s are equal, one of them may be dropped; and we can also rearrange the sequence (1) into ascending order and remove terms > n without destroying the addition chain property (2). from now on we shall consider only ascending chains, without explicitly mentioning this assumption. It is convenient at this point to define a few special terms relating to addition chains. By definition we have, for 1 5 i 2 T, Ui = aj + ak (14 for some j and k, 0 < k 2 j < i. Let us say that step i of (11) is a doubling, if j=k=i-1; then ai has the maximum possible value 2ai-1 that can follow the ascending chain 1, al, . . . , CJ-~. If j (but not necessarily k) equals i -1, let us say that step i is a star step. The importance of star steps is explained below. Finally let us say that step i is a small step if x(ai) = X(ai.-1). Since ai-< ai 5 2ai-1, the quantity x(ai) is always equal to either X(ai-1) or X(ai-1) + 1; it follows that, in any chain (ll), the length r is equal to A(n) plus the number of small steps. Several elementary relations hold between these types of steps: Step 1 is always a doubling. A doubling obviously is a star step, but never a small step. A doubling must be followed by a star step. Furthermore if step i is not a small step, then step i + 1 is either a small step or a star step, or both; putting this another way, if step i + 1 is neither small nor star, step i must be small. A star chain is an addition chain that involves only star steps. This means that each term ai is the sum of ai- and a previous ak; the simple computer discussed above after Eq. (2) makes use only of the two operations STA and ADD (not LDA) in a star chain, since each new term of the sequence utilizes the pre- ceding result in the accumulator. Most of the addition chains we have discussed so far are star chains. The minimum length of a star chain for n is denoted by l*(n); clearly l(n) 5 l*(n). (13) We are now ready to derive some nontrivial facts about addition chains. First we can show that there must be fairly many doublings if r is not far from x(n).
Note: If you are looking for best quality webspace to host and run your tomcat application check Vision personal web hosting services