Tutorial of CORDIC Algorithm


                 DOUBLE ITERATIONS IN CORDIC

Beginning from the first publications in CORDIC field many authors
(Lekven and Uno, Racy, Perle et al) indicated to principal opportunity
of using the same approach for computation of the functions :arcsin, arcos,
exp, ln, sh, Arsh etc. But it was noticed that direct using of CORDIC
gives too much errors in some points. The reason of that was "nonconvergence"
of the classical  CORDIC algorithms for these functions.

For convergence of iterative process it is necessary that any "wrong" i-th
iteration could be "corrected" in the subsequent (i+1)-th, (i+2)-th, (i+3)-th,
etc. etc. iterations.  Or, in other words, at least a half of the "wrong"
i-th iteration could be corrected in the next (i+1)-th iteration.
For atan(1/2^i) this condition is satisfied, i.e.:

atan(1/2^(i+1)) > 1/2*atan(1/2^i)

But for functions ln(1+1/2^i), ln(1-1/2^i), atanh(1/2^i)  this condition is not
satisfied.  For improving of this method it was suggested  to "double"  every
iteration in sense of magnitude of i , i.e. not to change the value i  [the
power in the  1/2^i ], every time i.e. in every iteration, but to change
it every second iteration. At the same time it is neccessary in EVERY iteration
to control of choice of its "direction" i.e. its sign. In such way we can
guarantee the convergence.  For example, for ln function:

2*ln(1+1/2^(i+1)) > 1/2*ln(1+1/2^i)

I.e. a half of "wrong" i-th iteration could be corrected by two next (i+1)-th
iterations.

So  this approach was named "double iterations" (in Russian: "dvoynie
iteratsii"). It is possible to designate "double iterations" as:
i=1,1,2,2,3,3,....n,n. Therefore total number of iterations compared with
classical CORDIC increased in two times. But we can guarantee the convergence.

For functions arcsin, arccos the necessity of "double" iterations is connected
with the magnitude of K(i). For example for evaluation of function arcsinY we
should get the final y(i) equal to Y, beginning from y(0) = 0. Then the sum of
all atan(1/2^i) with corresponding signs for i=0,1,2, ... , n  equal to
arcsinY.
But because of the coeffuicient K(i), in any iteration could be occur
a situation when we can do "wrong" iteration. Why?  Ideally  we should
correct the  value of Y (argument of arcsin function) in every iteration,
multiplying it to K(i). Instead of that we multiply Y in the beginning
of iterations to the product of all K(i), i.e. to well-known coefficient
1,64..... It is the reason of the possible "wrong" iterations.
In such case using of "double iterations" can solve this problem as well,
because in any i-th step it is possible to do only one "wrong" iteration which
could be corrected additional "right" iteration (it is very easy to show in
graphical way). In other words we also need "double" iterations for arcsin
and arccos functions.

Such approach is sufficient for all (excluded Arsh and Arch) functions.
in binary system. But when we deal with nonbinary systems: decimal,
hexadecimal etc.it is sufficient to execute for ln and exp functions
evaluation to do A iterations per digit (A - radix). But for functions
arcsin and  arccos it is necessary to execute 2(A-1) iterations per digit.
It is easy to notice that for binary numbers these values are equal,i.e.
 if A=2, then 2(A-1)=A.

Vladimir Baykov
vlad@vlad.usr.etu.spb.ru