Talk:CORDIC

Value of K in implentations

The value in the implentation section should really be what it was before someone changed it, 0.607. My comment wasn't correct which may have led to the confusion. The inverse of K is needed to get the true magnitude because all the shifts result in a gain of K = 1.647 which then must be removed to get the true magnitude.

See the article in the references section: http://www.dspguru.com/info/faqs/cordic2.htm

"Now, having rotated our complex number to have a phase of zero, we end up with "C = Ic + j0". The magnitude of this complex value is just "Ic" (since "Qc" is zero.) However, in the rotation process, C has been multiplied by a CO

RDIC Gain (cumulative magnitude) of about 1.647. Therefore, to get the true value of magnitude we must multiply by the reciprocal of 1.647, which is 0.607. (Remember, the exact CORDIC Gain is a function of the how many iterations you do."

Addps4cat 19:56, 21 March 2006 (UTC)

Yeah, the value of K in the implentation is indeed correct. However, the equation for K given in previous edition was wrong, which led to my confusion and my changing of K in the implentation before. K is defined as cos(arctan(2^(-i))), you can simply check that K should be 1/sqrt(1+2^(-2i)), instead of sqrt(1+2^(-2i)) as given before. And by this definition, lim(K)=0.6073, again not 1.647 as given before. I've corrected it and removed the "inv" in the implentation to avoid further confusion. Cdpango 11:16, 23 March 2006 (UTC)

I hate to belabor this but I think the definition of K = 1.647 is correct. The 1.647 is a result of the 2^-i shifts (I think). Then you must undo this gain by dividing by K at the end to remove this gain. I've done the algorithm on my computer and you do indeed up with a value K times greater than it should be. For example, if I ignore K, a 90 deg. shift of (1 , 0) becomes (0, 1.647). So you indeed must either multiply by inv. K or divide by K to obtain the true result. I'll wait until you respond to this so we don't end up reverting each other's edits. Addps4cat 21:08, 23 March 2006 (UTC)

Maybe I've not expressed myself clearly. You indeed needs to multiply 0.6073(or divide 1.647) after the iterations. But the problem is we define K as "product of cos(arctan(2^(-i)))", so its value should be "product of 1/sqrt(1+2^(-2i))", instead of "product of sqrt(1+2^(-2i))", and it approaches 0.6073 when n approaches infinite. On the other hand, the system gain is A="product of sqrt(1+2^(-2i))"=1.647=1/K. I think that you just mixed up A and K. You can check the beignning part of section 3 of the following article, which explains this issue quite clearly. http://www.andraka.com/files/crdcsrvy.pdf It's nice to have a discussion. Best wishes! Cdpango 04:59, 24 March 2006 (UTC)

Ahh I see. You are right on all accounts. Thanks for the clarification. Addps4cat 07:03, 24 March 2006 (UTC)

---

It seems interesting that the gain for the hyperbolic mode (m=-1)

$K(n)=\prod _{i=1}^{n-1}{\sqrt {1-2^{-2i}}}$

is quoted in J.S. Walther's paper and in many other places as

$K=\lim _{n\to \infty }K(n)\approx 0.80$

If you run it it seems to converge to :

$K=\lim _{n\to \infty }K(n)\approx 0.828$

Has anyone else ran into this discrepency?

---

—Preceding unsigned comment added by 71.228.178.91 (talk) 04:35, 1 February 2011 (UTC)

There is no sense to say of the limit of K

$K=\lim _{n\to \infty }K(n)\approx 0.6072529350088812561694$. It is well known, that number of iterations n should be equal the wordlength of the computer. Unlimited n corresponds to unlimited wordlength. But it is very hard to imagine a computer with the unlimited the length of word. Modern computers have 32, 64, 128 bits. Can you imagine the weight and the size of the computer with : $\_{n\to \infty }$ ?

Nonsense!

On the other side, when if the number of iterations is, for example, 32, then the value of K should necessary to evaluate just for n=32. If instead of that we use suggested K=0.6072529350088812561694 (for : $\_{n\to \infty }$) then error would be very big. By the way, coefficient K is not the Number $\pi$!! For Number $\pi$ the more digits you use, the more precisely result you get. But for K the number n should be exactly equal to the number of iterations. Not more and not less!

---

Mixing i and n

The article mixes in n and i for subscripts and superscripts and it is confusing. n should be used to refer to the total number of iterations while i should refer to the current iteration. This pops up in the beta(n+1) equation. I don't know if I am right so I am hesitant to change it. Maybe someone with a little more experience w/the algorithm can edit it. Addps4cat 20:01, 3 March 2006 (UTC)

*takes a second look at what actually is written*. Hm. You are absolutely correct, it is very unclear and confusing right now. If no one else beats me to it, I'll fix it tomorrow. Henrik 01:59, 4 March 2006 (UTC)

---

Decimal CORDIC

Decimal CORDIC was first suggested by J. E. Meggitt, "Pseudo Division and Pseudo Multiplication Processes", IBM Journal, April 1962

Hermann Schmid and Anthony Bogacki described decimal CORDIC only in 1973.[6]Vladimir Baykov (talk) 19:29, 29 July 2010 (UTC)

And Hewlett-Packard is known to have had decimal CORDIC implemented in 1966 internally.

At least the 1983 reprint edition of Schmid's 1974 "Decimal Computation" contains the following sentence on page 162: "So far CORDIC has been known to be implemented only in binary form. But, as will be demonstrated here, the algorithm can be easily modified for a decimal system." with a footnote added reading "In the meantime it has been learned that Hewlett Packard and other calculator manufacturers employ the decimal CORDIC techniques in their scientific calculators." It is unclear, if this footnote was added in the 1983 reprint edition only, or if it is already present in the 1974 edition.

Quite interesting, even Jean-Michel Muller's "Elementary Functions - Algorithms and Implementations" (2nd edition, 2006, page 156) can be read as if Hermann Schmid & Anthony Bogacki were the first to suggest decimal CORDIC in their 1973 paper, although he doesn't say so explicitly.

I have clarified the WP article accordingly.

--Matthiaspaul (talk) 23:24, 20 January 2016 (UTC)

Small update: Even the original 1974 edition of Schmid's book contains the above-mentioned footnote, so it must have been a "last-minute" correction in 1974. --Matthiaspaul (talk) 17:58, 6 February 2016 (UTC)

Strange statement

Somebody has written: "For most ordinary purposes, 40 iterations (n = 40) is sufficient to obtain the correct result to the 10th decimal place."

Actually the number of iterations for CORDIC must be equal to the wordlength. For example, if the wordlength is 16 there is no sense to do 40 iterations , as said unknown author. In this case the number of iterations must be 16. Not more and not less! —Preceding unsigned comment added by Vladimir Baikov (talk • contribs) 08:28, 22 November 2007 (UTC)

I don't fully agree with this. It would be true, if for each iteration the angle adjustment was half the previous adjustment. As anyone can see from the angle table in the article, this is not so. Though the number of bits required can be used as an indication of the number of iterations needed, it is not exact. --89.146.28.90 (talk) 10:52, 2 February 2011 (UTC)

Disputed

I can't figure out who developed it, and the articles creator left us with two choices, hence the "dispute" —siroχo 21:49, Jul 26, 2004 (UTC)

• I presume by 'it', you mean who is credited with the original development of the algorithm? Andraka says the original work is credited to Volder.
• Andraka is right, Jack Volder was the first (1959), to say nothing about Henry Briggs (1624).

accuracy

any idea of the accuracy of this algorithm and connections with the number of iterations ? any comparison between this algorithm an some others ? --bloublou 10:58, 11 August 2006 (UTC)

[1]

found also in DSP forum from Andraka "Sounds about right. THe worst case angular error after each iteration is the rotation angle of that iteration (which happens if the previous iteration landed exactly on your target angle), so the max error angle is atan(2^-i) after iteration i. Iterations start at 0. The last iteration needed to get an error of less than 0.1 degrees is therefore log2(tan(0.1)) rounded away from zero => 10, and counting from 0 you have 11 iterations to complete not counting your angle reduction." --bloublou 17:23, 11 August 2006 (UTC)

about accuracy

you can have a look at: [2] on page 13 you can see the table contained the formulae of the CORDIC errors. naturally you cant read russian but the formulaes language is international. in this table:

                n -  word length (number of iterations equals to n for sin, cos, OR equals to 2n     
                      for asin, acos, ln, exp)
                r - the number of additional bits of the words

and here we say about root mean square errors.

you can find many other ideas incl. cordic accuracy in [3]

Vladimir Baykov

vladimir@baykov.de

Python

Just for the record, here is the souce code in Python programming language

#!/usr/bin/python
from __future__ import division
from math import atan,pi,sqrt
import sys

def main_function(degrees,iterations = 8):
  # convert from degrees into radians
  beta = degrees * pi / 180.0
  
  ArcTanTable = []
  for i in range(iterations):
    ArcTanTable.append(    atan( 2.0**(-1 * i) )    )
  
  KN = []
  value = 1.0
  for i in range(iterations):
    value = value * sqrt(  1.0 + 2.0**(-2 * i)  )  
    KN.append(1.0 / value)

  Vx , Vy = 1.0 , 0.0
  for i in range(iterations):
    if beta < 0:
      Vx,Vy = Vx + Vy * 2.0**(-1 * i)  ,  Vy - Vx * 2.0**(-1 * i)
      beta = beta + ArcTanTable[i]
    else:
      Vx,Vy = Vx - Vy * 2.0**(-1 * i)  ,  Vy + Vx * 2.0**(-1 * i)
      beta = beta - ArcTanTable[i]
  Vx,Vy = Vx * KN[iterations - 1] , Vy * KN[iterations - 1]
  print "K[%9d] = %14.12f" % (iterations - 1,KN[iterations - 1])
  print "Sin(%4.1f) = %14.12f  and Cos(%4.1f) = %14.12f" % (degrees,Vy,degrees,Vx)
  
if __name__ == '__main__':
  if len(sys.argv) == 2:
    deg  = float(sys.argv[1])
    iter = 8
  elif len(sys.argv) == 3:
    deg  = float(sys.argv[1])
    iter = int(sys.argv[2])
  else:
    print "using default values of 17 degrees and 8 iterations"
    deg  = 17.0
    iter = 8
  main_function(deg,iter)

Here is a sample run

$ python cordic.py 30 40
K[       39] = 0.607252935009
Sin(30.0) = 0.500000000000  and Cos(30.0) = 0.866025403785

JavaScript

The python code above seems a little complex given that a port of the C implementation to JS can be written like this:

var AG_CONST = 0.6072529350;
 
function FIXED(X)
{
  return X * 65536.0;
}
 
function FLOAT(X)
{
  return X / 65536.0;
}
 
function DEG2RAD(X)
{
  return 0.017453 * (X);
}
 
var Angles = [
  FIXED(45.0), FIXED(26.565), FIXED(14.0362), FIXED(7.12502),
  FIXED(3.57633), FIXED(1.78991), FIXED(0.895174), FIXED(0.447614),
  FIXED(0.223811), FIXED(0.111906), FIXED(0.055953),
  FIXED(0.027977) 
	      ];
 
var X;
var Y;
var TargetAngle;
var CurrAngle;
var Step;
 
X = FIXED(AG_CONST);         /* AG_CONST * cos(0) */
Y = 0;                       /* AG_CONST * sin(0) */
 
TargetAngle = FIXED(28.027);
CurrAngle = 0;
for (Step = 0; Step < 12; Step++) {
    var NewX;
    if (TargetAngle > CurrAngle) {
      NewX = X - (Y >> Step);
      Y = (X >> Step) + Y;
      X = NewX;
      CurrAngle += Angles[Step];
    } else {
      NewX = X + (Y >> Step);
      Y = -(X >> Step) + Y;
      X = NewX;
      CurrAngle -= Angles[Step];
    }
}
 
print('CORDIC: ' + FLOAT(TargetAngle) + ' ' + FLOAT(Y) + ' ' + FLOAT(X) + '\n' );
print('FP: ' + FLOAT(TargetAngle) + ' ' + Math.sin(DEG2RAD(FLOAT(TargetAngle))) + ' ' + Math.cos(DEG2RAD(FLOAT(TargetAngle))) + '\n' );

86.152.208.199 00:55, 19 February 2007 (UTC)richmoore44@gmail.com86.152.208.199 00:55, 19 February 2007 (UTC)

Strange

It seems a little strange that Volder should publish his first paper describing the CORDIC in the IRE Transactions on Electronic Computers, September 1959 and in the very same journal Daggett publishes his work on CORDIC. I reckon Daggett was peer reviewing for the journal and stole some ideas!! But seriously had Volder written an earlier or paper or were the two actually working together? Graemec2 07:46, 10 October 2006 (UTC)

Both... ;-)

Volder conceived and wrote about CORDIC in 1956 already, but this was an internal report only. Daggett was a co-worker of Volder.

--Matthiaspaul (talk) 01:05, 4 January 2016 (UTC)

References

It would be much more logical to put the References in the chronological order: beginning from the first publications to the recent ones. —The preceding unsigned comment was added by 80.133.27.236 (talk) 21:37, 12 January 2007 (UTC).

I disagree. Let them come in the order that they are referred to, like most wikipedia articles do. Dicklyon 01:36, 13 January 2007 (UTC)

The reference number [3] was made by Muller only to show very doubtful or more precisely speaking absolute senseless the limit value of K

$K=\lim _{n\to \infty }K(n)\approx 0.6072529350088812561694$.

The number of iterations n should be equal the wordlength of the computer. Unlimited n corresponds to unlimited wordlength. Did anybody see a computer with the unlimited length of word?! On the other hand, if the number of iterations is, for example, 32, then the value of K should be necessary to evaluate just for n=32. If instead of that we use suggested K=0.6072529350088812561694 (for : $\_{n\to \infty }$) then error would be large!

In the other words the coefficient K for unlimited n has neither practical nor theoretical sense! So reference number [3] is unnecessary. Vladimir Baykov (talk) 21:25, 18 July 2010 (UTC)

About history and application of CORDIC. In 1966 in "Electronics" was published the paper of J.Parini about DIVIC computer, based on CORDIC technique.Vladimir Baykov (talk) 21:25, 20 July 2010 (UTC)

Numerical value

A note regarding numerical approximation: Since this is an reference work, it is foolish to assume a few digits would suite everyone. In fact, the first digits are listed on J. M. Muller, page 134. -- Ylai 08:49, 2 January 2007 (UTC)

Additional note: It is even more strange to ask for source for the additional digits, while the initial approximation is technically. unsourced itself. Not everybody calculates with single or double precision hardware only. -- Ylai 08:51, 2 January 2007 (UTC)

Not so strange, since almost anybody can easily verify up to about 14 digits. More than that requires much more specialized skill, or a good reference. However, also note that having more digits will not enable one to implement a CORDIC that accurate; one would also have to have trig functions that accurate to generate the needed angles. So the additional digits are really quite pointless, aren't they? Dicklyon 08:56, 2 January 2007 (UTC)

This is an encyclopedia, not a implementation manual. Constants are interesting themselves just for their mathematical interest.

In the other issue of precision, it is true, but not the reason you gave. Higher precision arithmetics usually are implemented on hardware with multipliers and square root circuitry, and then the quadratically converging AGM becomes more efficient. -- Ylai 08:59, 2 January 2007 (UTC)

About verifying, just type in Mathematica:

N[Product[1/Sqrt[1 + 2^(-2n)], {n, 0, Infinity}], 22]

gives you the result on J.-M. Mueller, "Elementary functions", p. 134. The author probably used Maple, but it is certainly not difficult. Most commercial Fortran Compiler also supports REAL*16. -- Ylai 09:03, 2 January 2007 (UTC)

Well, I don't happen to have Mathematica nor a Fortran compiler handy, but I take your point. If you'd like to put the number back again, please do add the reference. Dicklyon 09:05, 2 January 2007 (UTC)

Implementation in C

About the following edit:

01:00, 2 January 2007 Dicklyon (Talk | contribs) (→Implementation in C - remove section, as the algorithm is not useful either pedagogically or practically in this form)

C is more known than MATLAB. Please allow the example at least here. Thanks. :) 130.83.161.82 08:39, 18 May 2007 (UTC)

This is copied from history:

The following is a C implementation of CORDIC using floats. Beta is the input angle in radians. We start with vector v = (1,0).

 int i = 0;
 int iterations = 0; // Number of times to run the algorithm
 float arctanTable[iterations]; // in Radians
 float K = 0.6073; // K
 float v_x,v_y; // Vector v; x and y components

 for(i=0; i < iterations; i++) {
    arctanTable[i] = atan(pow(2,-i));
 }

 float vnew_x;   // To store the new value of x;
 for(i = 0; i < iterations; i++) {
     // If beta is negative, we need to do a counter-clockwise rotation:
     if( beta < 0) {
        vnew_x = v_x + (v_y*pow(2,-i)); 
        v_y -= (v_x*pow(2,-i));  
        beta += arctanTable[i]; 
     }
     // If beta is positive, we need to do a clockwise rotation:
     else {
        vnew_x = v_x - (v_y*pow(2,-i));
        v_y += (v_x*pow(2,-i));
        beta -= arctanTable[i];
     }
     v_x = vnew_x;
 }
 v_x *= K;
 v_y *= K;

External Link Removed

I have removed the following external link as it appears to be broken: http://www.dspguru.com/info/faqs/cordic2.htm If it comes back or someone can find the new URL (if there is one) - please update it.194.72.120.131 (talk) 11:20, 12 November 2010 (UTC)

I removed five dead links from "external links":

• CORDIC information
• The CORDIC Algorithm
• USENET discussion
• Another USENET discussion
• Usenet discussion about CORDIC

--Matthiaspaul (talk) 23:05, 20 January 2016 (UTC)

What is the difference between NOTES and REFERENCES?

I don`t understand what is the difference between NOTES and REFERENCES? I guess it would be better ALL LITERATURE state in the chronological order! — Preceding unsigned comment added by 134.99.136.28 (talk) 13:41, 12 October 2013 (UTC)

The distinction is not universally followed, but ideally Notes are clarifications and References are sources. —Tamfang (talk) 23:48, 12 October 2013 (UTC)

(Co)Processors using Cordic

The Motorola 68000 Floating Point Coprocessor, the MC68881, internally uses CORDIC. The MC68882 does as well and improves on its predecessor by generating a result step on each clock edge (doubling the speed). I think the 6809's Floating Point ROM M6839 also uses CORDIC as it was developed by the same engineers, before they worked on the 68000's co-processor. — Preceding unsigned comment added by 131.107.147.56 (talk) 20:28, 8 October 2014 (UTC)

Of course, this can be included, but we need reliable references. --Matthiaspaul (talk) 01:06, 4 January 2016 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified 5 external links on CORDIC. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20150309055201/http://www.jacques-laporte.org/Briggs%20and%20the%20HP35.htm to http://www.jacques-laporte.org/Briggs%20and%20the%20HP35.htm
• Added archive https://web.archive.org/web/20150309055210/http://www.jacques-laporte.org/Trigonometry.htm to http://www.jacques-laporte.org//Trigonometry.htm
• Added archive https://web.archive.org/web/20160818122704/http://www.jacques-laporte.org/TheSecretOfTheAlgorithms.htm to http://www.jacques-laporte.org/TheSecretOfTheAlgorithms.htm
• Added archive https://web.archive.org/web/20160818121038/http://www.jacques-laporte.org/digit_by_digit.htm to http://www.jacques-laporte.org/digit_by_digit.htm
• Added archive https://web.archive.org/web/20160818120118/http://www.jacques-laporte.org/Logarithm_1.htm to http://www.jacques-laporte.org/Logarithm_1.htm

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

Y An editor has reviewed this edit and fixed any errors that were found.

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 17:50, 28 July 2017 (UTC)

inefficient implementation

This is not the main purpose of the page (although the main reason of existence of CORDIC is efficient computation of tric functions), but IMHO it's unreasonable to do "beta = beta mod pi" by recursively adding or subtracting pi! It requires a recursion of depth > 1000 if you call it with beta = 5000 which is not an extremely large value! (In addition, you get rounding errors from performing more than 1000 additions of pi.) A simple "mod" instruction should really be preferred. — MFH:Talk 13:42, 11 September 2018 (UTC)

I agree. It gets even worse than that: the main purpose of CORDIC is to avoid multiplications and divisions in the main loop, while all implementations so far that I seen do several of these in each iteration, they do 2**-i in main loop instead of precomputing it, etc. The implementations provided suck way more than you realize. :)

~~ WhyYouAskMe (talk) 17:18, 8 July 2022 (UTC)

I came here to mention this - the article discusses a lot how the algorithm avoids the need for hardware multiply, but all the implementations use multiplication to more closely match the maths. I would prefer to see them use the appropriate shifts or ldexp and remove all uses of multiplication (with comments showing what the now somewhat obscured code is is doing). -- Axman6 (talk) 06:19, 20 July 2023 (UTC)

Bury the lede

CORDIC

• and closely related methods
  • known as:

• pseudo-multiplication

• and

• pseudo-division

• or

• factor combining

• are commonly used
  • when no hardware multiplier is available
    • (e.g. in simple microcontrollers and FPGAs).
  • as the only operations it requires are
    • additions, subtractions, bitshift and lookup tables.

As such, they all belong to the class of shift-and-add algorithms.

In computer science, CORDIC is often used to implement floating-point arithmetic when the target platform lacks hardware multiply for cost or space reasons.

I just added the last sentence quoted above. It partially duplicates the first sentence above (grammatically exploded), but 95% of readers will barely notice this, as their parse recursion is already busy dropping the factoids embedded in the first sentence into the buffer-overrun bit bucket. — MaxEnt 13:25, 3 September 2020 (UTC)

More Formalized can't be the algorithm

The More Formalized section of this article uses sin and cos in the rotation matrix to develop the ability to calculate sin and cos. 174.63.44.188 (talk) 02:28, 17 March 2023 (UTC)

oh nvm I didn't read the bitshift implementation >.< 174.63.44.188 (talk) 02:34, 17 March 2023 (UTC)