CSE 246: Computer Arithmetic Algorithms and Hardware Design

CSE 246: Computer Arithmetic Algorithms and Hardware Design Fall 2006 Lecture 11 Cordic, Log, Square, Exponential Functions Instructor: Prof. Chung-Kuan Cheng Cordic Algorithm Idea Coordinate Rotations Digital Computer (x,y) (x,y) Rotate vector (x,y) to (x,y) Cordic Algorithm Equations

x' x cos y sin y ' x sin y cos x' x y tan cos y' x tan y cos 2 r ' ' r 1 tan 1/ 2 Main equations

Derived equations Cordic Algorithms Key: Given cos , sin , tan we can derive si i i s 1, 1 tan i 2 i i 0 45 1 26.6

2 14 3 7.1 4 3.6 5 1.8 6 0.9 7 0.4 8

0.2 9 0.1 i Cordic Algorithms (Example) i Find tan 30 tan i 2 30 45 26.6 14 7.1 3.6 1.8 0.9 0.4 0.2 0.1 x0 x y tan 45 x y y0 x tan 45 y x y

2 r0 1 tan 45 1/ 2 Cordic Algorithm Example Continued x1 x0 y0 tan 26.6 y1 x0 tan 26.6 y0 2 1/ 2

r1 1 tan 26.6 ri 1.646760 9 i 0 Logarithms Method 1 Find ln mx x m xC i 1 i 1 m m m i i y ln C ln C i 1 i 1

m 1 i C x i 1 y ( m ) ln x Logarithms Method 1 I. x 1,2 II. C i 1 d i 2 i III. A table of d i 1,0,1 ln 1 d i 2 i

Logarithms Method 1 (Example) Find ln(x), x = 1.625 1+0.5+0.125=1.625 1. 1 1.-1 -1 -1 x 1 1 0 0. 1 1 0 1 _ 0 -1 1 _ 0 1 0.1 1.0 0 1 x 0 1 1 1.0 0 1 1 1

0 0 0 1 _ 0 1 1 _ 0 1 Logarithms Method 1 (Example) 1. 0 0 0 0 0 1 1. 0 0 0 0 0-1 1. 0 0 0 0 0 0 0 0 0 0 -ln x = (1.-1) + ln(1.01) + ln(1.0000-1) Logarithms Method 2 Let define 2 x 2 2 ln 2 x 2

x 2 ln 2 x 2 y0 . y1 y2 y3 y0 y1 . y2 y3 Initially x<2, ie. y0=0 2 x 0. y 2 y 3 2 2 If x 2 2 ln 2 x y0 . y1 y2 y3 Logarithms Method 2 for i = 1 to l do x = x2 if x 2 then yi = 1 x = x/2 else yi = 0 Logarithms Method 2 (Example) Find ln2(x), x = 1.11 (1.75) x2

1.1 1 x 1.1 1 1 1 1 1 1 1 + 1 1 1 __ 1 1 0 0 0 1 y1 = 1 x2/2 1.1 x 1.1 1 1 1 1 0 0 0 1 + 1 1 0 0 0 1 1 0.0 1 0 1 1 0 y2 = 1 0 0 0 1 0 0 0 1 0 0 0 1 _ 0 0 0 1

Logarithms Method 2 (Example) (x2/2)2/2 = 1.00101100001 y3 = 0 ln2 1.11 0.110 Squarer X + + x3x1 x3x2 x2x2 x3x3 x2x3 x1x3 x3x2 x3x1 x3x0 x3 x2x1 x2 x3 x3 x3x0 x2x1

x1x2 x0x3 x2x0 x2 x1 x0 x2 x1 x0 x2x0 x1x0 x0x0 x1x1 x0x1 x0x2 _ x1x0 x0 x1 _ Exponentiation e x m x m m ln C

i 0 i 1 m i y C i 1 x ln C i y m e

ln C i ln C i e e x x Exponentiation ex I. x 1,1 II. Ci 1 d i Z i d i 1,0,1 i ln 1 2 1.24 min:

i ln 1 2 1.56 max: