Logic Circuits - Models of Computation: Exploring the Power of Computing - page 73

x 0 ) n + 1
( n + 1 )!

= ( x

−

f [ n + 1 ] ( ψ )

for some ψ satisfying x 0 ≤ ψ ≤ x .

2 2 n− 1 / by applying it to the function f ( w )=

( 1 + w ) − 1 on the interval [ 0, 1 ] . The Taylor expansion of this function is
( 1 + w ) − 1 = 1

Taylor's theorem is used to expand | u |

w 3 ( 1 + ψ ) − 4

w + w 2 − −

1. The magnitude of the last term is at most w 3 .

for some 0 ≤ ψ ≤

Let n ≥ 12, k = n/ 2 , l = n/ 12 and restrict | u | as follows:

= 2 k +

| u | | a | where

= 2 l

| a | | b | + 1and

2 l− 1

| b |≤ − 1

2 2 l− 1 2 l + 1 < 2 2 l− 1 for l It follows that | a |≤ − ≥ 1. Applying the Taylor series expansion

/ 2 k ) − 1 ,wehave
2 2 n− 1
( 2 k +

to ( 1 + | a |

= 2 2 n− 1 −k 1

( 1 + ψ ) − 4 + |

2 k 2

|

2 k 3

− |

|
2 k

a a | a |

− (2.14)

| a |

)

for some 0 both the sum of the first two terms

and the third term on the right-hand side have the following bounds:
2 2 n− 1 −k ( 1

≤ ψ ≤ 1. For the given range of values for | u |

/ 2 k ) > 2 2 n− 1 −k 1 2 2 l− 1 / 2 k

−| a | −

/ 2 k ) 2 < 2 2 n− 1 −k 2 2 l− 1 / 2 k 2
Since 2 2 l− 1 / 2 k < 1 / 2, the value of the third term, 2 2 n− 1 −k (

2 2 n− 1 −k (

| a |

/ 2 k ) 2 , is an integer that does
not overlap in any bit positions with the sum of the first two terms.
The fourth term is negative; its magnitude has the following upper bound:
2 2 n− 1 − 4 k

| a |

3 ( 1 + ψ ) − 4 < 2 3 ( 2 l− 1 )+ 2 n− 1 − 4 k

| a |

Expanding the third term, we have
2 2 n− 1 − 3 k (

) 2 = 2 2 n− 1 − 3 k ( 2 2 l

2 + 2 l + 1

| a | | b | | b | + 1 )

Because 3 ( 2 l

k , the third term on the right-hand side of this expansion has value
2 2 n− 1 − 3 k and is larger than the magnitude of the fourth term in ( 2.14 ). Consequently the
fourth term does not affect the value of the result in ( 2.14 ) in positions occupied by the binary
representation of 2 2 n− 1 − 3 k ( 2 2 l

−

1 )

≤

2 + 2 l + 1

) .Inturn,2 l + 1 is less than 2 2 l ,whichmeans | b | | b | | b |

that the binary representation of 2 2 n− 1 − 3 k ( 2 2 l

2 ) appears in the output shifted but otherwise
without modification. This provides the following result.

| b |

LEMMA 2.10.1 The reciprocal function f ( n )
recip

contains as a subfunction the squaring function

f ( m ) square for m = 1 .

Proof The value of the l -bit binary number denoted by b appears in the output if l =

n/ 12 −

n/ 12 ≥ 1.

Lower bounds similar to those derived for the reciprocal function can be derived for special
fractional powers of binary numbers. (See Problem 2.35 .)