CORDIC: error analysis

[Baykov Vladimir]

I'll try to explain briefly my results in the field of CORDIC
and CORDIC-like algorithms error analysis. All of them are reflected
in my PhD (1972), in my DrSC thesis (1985) and in my books and papers.
It is possible to read about them in :
RLIN Bibliographic DB, in OCLC WorldCat and "Comp.&Contr.Abstr".

The main source of the errors of CORDIC is ignoring of rightmost bits,
when we shift X or Y to i positions to the right in every iteration
if we don't have additional bits, i.e. if the word size is n and number
of iterations is also n.
We may use analyse maximal errors or statistical (probabilistic) errors.
Maximum error equals to (n-1)* 2**(-n). Statistical evaluation is much
less.
I prefer the statistical ones. The reason is the following: for getting
maximal errors it is necessary to have in all shifted to the right bits
(ignored bits) only "ones". If we assume equal distributution of the
"zeroes" and
"ones" in any binary number then probability of exactly of I "ones" in
shifted to the right bits is equal to 0.5**I.
If we shift X(I) to I bits and then shift X(I+1) to I+1 bits (emphasise
that X(I) and X(I+1) are absolutely different numbers!) then probability
of all "ones" in these two cases is the product of 0.5**I to 0.5**(I+1).
For CORDIC algorithms shiftings are executing from 1 bit to n bits.
So we have that probability of all shifted "ones" in all iterations
(all shifts) equals to 0.5**(n**2)/2. Even for n=16 it is equal to 10**(-38).

So I prefer probabilistic evaluations.
According to this approach we assume equal probability of "ones" and
"zeroes" in any numbers and if we shift, for example, to three bits to the
right we can get all the combinations , beginning from -7 to 0 and to +7
(in scale of 2**{-(n+3)}). The total number of combinations is 15. So the
probability of each combination is 1/15. So we can evaluate the dispersion
of the error in each iteration. Then we add all the dispersions for all
iterations and evaluate root-mean square.
I got that root-mean square, assuming zero mean value, equals to

square root[(n-2)/3], measuring in the least significant bit.

For example, for n=16 according to the formula we have approx. 2.15*2**(-n).
Compare: maximum error for n=16 is 15*2**(-n), that is absolutely not realistic.

The other source of errors is : reducible to zero variable, according to
which we choose the sign of operation: + or - in CORDIC, with every
new iteration becomes less and less, but the error of computation becomes
larger and larger. And the last 1 or 2 iterations we are moving in the
"noise of errors". It is an additional sourse of errors.

All the last sourses: limited number of iterations, adding of rounded con-
stants are traditional.
I simulated all the functions at a computer, changing word size from
4 bits to 32. Number of points were from 16 to 64000.

Vladimir Baykov