Transformations - Transformations and Projections in Computer Graphics - page 23

1. CORDIC employs only shifts and additions/subtractions, so any implementation
should use fixed-point, instead of floating-point, arithmetic. This is fast since shifting
and adding fixed-point numbers can be done with integer operations. Notice that all the
numbers involved in the computations are less than unity, except perhaps the original
coordinates ( x, y ). A software package for graphics employing this method should there-
fore use normalized coordinates (fixed-point numbers in the interval [0 , 1]) throughout
and perform all the calculations on these small numbers. Each iteration results in a pair
( x i +1 ,y i +1 ) that's slightly larger than its predecessor, but the last iteration results in
a pair that can be larger than ( x, y ) by a factor of at most 1 / 0 . 60725 ... =1 . 64676 ... .
This pair is then scaled down when multiplied by K m . The final step is to scale the
final coordinates up.
All this suggests a 32-bit fixed-point format where the leftmost bit is reserved, as
usual, for the sign, the next two bits are the integer part, and the remaining 29 bits are
the fractional part (29 bits being equivalent to 9 decimal digits). The largest number
that can be represented by this format is 11 . 11 ... 1 2 =3 . 999 ... and the smallest one
is 110 ... 0 2 = − 4. It's a good idea to reserve two bits for the integer part because (1)
even though all the numbers involved are 1 or smaller, some intermediate results may
be greater than 1 and (2) this convention makes it possible to represent the important
constants π , e ,and φ (the Golden Ratio).
2. Earlier, we said, “It is easy to write a program that decides which of the θ i 's
should be added and which should be subtracted.” The practical way to do this is to
initialize a variable z to θ and try to drive z to zero during the iterations. In iteration
i the program should calculate both z + θ i and z

θ i , select the value that's closer to
zero, use it to decide whether to add or subtract θ i , and then update z .If z − θ i is
closer to zero, then θ i should be added; otherwise, θ i should be subtracted. An example
is θ =58 ◦ . We initialize z to 58. In iteration 0, it is clear that 58

−

45 = 13 is closer
to zero than 58 + 45. The program therefore adds θ 0 and updates z to 13. In iteration
1, the program finds that 13

−

− 26 . 5651 = − 13 . 5651 is closer to zero than 13 + 26 . 5651,

so it adds θ 1 and updates z to − 13 . 5651. In iteration 2, the program discovers that

− 13 . 5651 + 14 . 0362 = 0 . 4711 is closer to zero than − 13 . 5651 − 14 . 0362, so it subtracts

θ 2 and updates z to 0 . 4711.
Finally, we realize that there is really no need to compare z + θ i and z−θ i in iteration
i . We simply start by selecting d 0 = +1 and update z by subtracting z ← z − θ 0 ,
z ← z − θ 1 , etc., until we get a negative value in z . We then change d i to − 1 (the new

sign of z ) and update z by z d i θ i (which now amounts to adding θ i to z ). This is

summarized by the Mathematica code of Figure 1.13. (But note that the Sign function
of Mathematica returns +1, 0, or

← z −

− 1, while we need a result of +1 or − 1. The code as

shown is simple but not completely general.)

Compared to other approaches, CORDIC is a clear winner when a hardware multiplier
is unavailable (e.g. in a microcontroller) or when you want to save the gates required
to implement one (e.g. in an FPGA). On the other hand, when a hardware multiplier
is available (e.g. in a DSP microprocessor), table-lookup methods and good old-
fashioned power series are generally faster than CORDIC.
—Grant R. Gri n, www.dspguru.com/info/faqs/cordic.htm