Editing CORDIC (section)

=={{anchor|Binary CORDIC|Decimal CORDIC|Unified CORDIC}}History==
Similar mathematical techniques were published by [[Henry Briggs (mathematician)|Henry Briggs]] as early as 1624<ref name="Briggs_1624"/><ref name="Laporte_2014_Briggs"/> and Robert&nbsp;Flower in 1771,<ref name="Flower_1771"/> but CORDIC is better optimized for low-complexity finite-state CPUs.

CORDIC was conceived in 1956<ref name="Volder_1956"/><ref name="Volder_2000"/> by [[Jack&nbsp;E.&nbsp;Volder]] at the [[aeroelectronics]] department of [[Convair]] out of necessity to replace the [[analog resolver]] in the [[B-58 Hustler|B-58 bomber]]'s navigation computer with a more accurate and faster real-time digital solution.<ref name="Volder_2000"/> Therefore, CORDIC is sometimes referred to as a [[digital resolver]].<ref name="Perle_1971"/><ref name="Schmid_1983"/>

In his research Volder was inspired by a formula in the 1946 edition of the ''[[CRC Handbook of Chemistry and Physics]]'':<ref name="Volder_2000"/>
: <math>
\begin{align}
 K_n R \sin(\theta \pm \varphi) &= R \sin(\theta) \pm 2^{-n} R \cos(\theta), \\
 K_n R \cos(\theta \pm \varphi) &= R \cos(\theta) \mp 2^{-n} R \sin(\theta), \\
\end{align}
</math>
where <math>\varphi</math> is such that <math>\tan(\varphi) = 2^{-n}</math>, and <math>K_n := \sqrt{1 + 2^{-2n}}</math>.

His research led to an internal technical report proposing the CORDIC algorithm to solve [[sine]] and [[cosine]] functions and a prototypical computer implementing it.<ref name="Volder_1956"/><ref name="Volder_2000"/> The report also discussed the possibility to compute hyperbolic [[coordinate rotation]], [[logarithm]]s and [[exponential function]]s with modified CORDIC algorithms.<ref name="Volder_1956"/><ref name="Volder_2000"/> Utilizing CORDIC for [[multiplication]] and [[division (mathematics)|division]] was also conceived at this time.<ref name="Volder_2000"/> Based on the CORDIC principle, Dan&nbsp;H.&nbsp;Daggett, a colleague of Volder at Convair, developed conversion algorithms between binary and [[binary-coded decimal]] (BCD).<ref name="Volder_2000"/><ref name="Daggett_1959"/>

{{anchor|CORDIC I|CORDIC II}}In 1958, Convair finally started to build a demonstration system to solve [[radar fix]]–taking problems named ''CORDIC I'', completed in 1960 without Volder, who had left the company already.<ref name="Volder_1959_1"/><ref name="Volder_2000"/> More universal ''CORDIC II'' models ''A'' (stationary) and ''B'' (airborne) were built and tested by Daggett and Harry Schuss in 1962.<ref name="Volder_2000"/><ref name="ASG_1962"/>

Volder's CORDIC algorithm was first described in public in 1959,<ref name="Volder_1959_1"/><ref name="Volder_1959_2"/><ref name="Volder_2000"/><ref name="Schmid_1983"/><ref name="Schmid_1974"/> which caused it to be incorporated into navigation computers by companies including [[Martin-Orlando]], [[Computer Control]], [[Litton Industries|Litton]], [[Kearfott]], [[Lear-Siegler]], [[Sperry Rand|Sperry]], [[Raytheon]], and [[Collins Radio]].<ref name="Volder_2000"/>

{{anchor|Pseudo-division|Pseudo-multiplication|Athena|Green Machine}}Volder teamed up with Malcolm McMillan to build ''Athena'', a [[fixed-point arithmetic|fixed-point]] [[desktop calculator]] utilizing his binary CORDIC algorithm.<ref name="Leibson_2010_2"/> The design was introduced to [[Hewlett-Packard]] in June 1965, but not accepted.<ref name="Leibson_2010_2"/> Still, McMillan introduced [[David S. Cochran]] (HP) to Volder's algorithm and when Cochran later met Volder he referred him to a similar approach [[John&nbsp;E. Meggitt]] (IBM<ref name="Meggitt_1962"/>) had proposed as ''pseudo-multiplication'' and ''pseudo-division'' in 1961.<ref name="Meggitt_1962"/><ref name="Cochran_2010_2"/> Meggitt's method also suggested the use of base 10<ref name="Meggitt_1962"/> rather than [[binary numeral system|base 2]], as used by Volder's CORDIC so far. These efforts led to the [[ROMable]] logic implementation of a decimal CORDIC prototype machine inside of Hewlett-Packard in 1966,<ref name="Cochran_1966"/><ref name="Cochran_2010_2"/> built by and conceptually derived from [[Tom Osborne (engineer)|Thomas E. Osborne]]'s prototypical ''Green Machine'', a four-function, [[floating-point]] desktop calculator he had completed in [[Diode–transistor logic|DTL]] logic<ref name="Leibson_2010_2"/> in December 1964.<ref name="Osborne_1994"/> This project resulted in the public demonstration of Hewlett-Packard's first desktop calculator with scientific functions, the [[HP&nbsp;9100A]] in March 1968, with series production starting later that year.<ref name="Leibson_2010_2"/><ref name="Osborne_1994"/><ref name="Leibson_2010_1"/><ref name="Cochran_1968"/>

{{anchor|Logarithmic Computing Instrument|Factor combining}}When [[Wang Laboratories]] found that the HP&nbsp;9100A used [[multiple discovery|an approach similar]] to the ''factor combining'' method in their earlier [[Wang LOCI-1|LOCI-1]]<ref name="Wang_1964_LOCI-1"/> (September 1964) and [[Wang LOCI-2|LOCI-2]] (January 1965)<ref name="Bensene_2013"/><ref name="Wang_1967_LOCI"/> ''Logarithmic Computing Instrument'' desktop calculators,<ref name="Bensene_2004"/> they unsuccessfully accused Hewlett-Packard of infringement of one of [[An Wang]]'s patents in 1968.<ref name="Cochran_2010_2"/><ref name="Cochran_2010_1"/><ref name="Wang_US3402285"/><ref name="Wang_DE1499281B1"/>

[[John Stephen Walther]] at Hewlett-Packard generalized the algorithm into the ''Unified CORDIC'' algorithm in 1971, allowing it to calculate [[hyperbolic functions]], [[natural exponential]]s, [[natural logarithm]]s, [[multiplication]]s, [[Division (mathematics)|division]]s, and [[square root]]s.<ref name="Swartzlander_1990"/><ref name="Walther_1971"/><ref name="Walther_2000"/><ref name="Petrocelli_1972"/> The CORDIC [[subroutines]] for trigonometric and hyperbolic functions could share most of their code.<ref name="Cochran_2010_1"/> This development resulted in the first [[scientific calculator|scientific]] [[handheld calculator]], the [[HP-35]] in 1972.<ref name="Cochran_2010_1"/><ref name="Cochran_1972"/><ref name="Laporte_2005_Trig"/><ref name="Laporte_2005_Secret"/><ref name="Laporte_2012_Digit"/><ref name="Laporte_2012_HP35Log"/> Based on hyperbolic CORDIC, [[Yuanyong Luo]] et al. further proposed a Generalized Hyperbolic CORDIC (GH CORDIC) to directly compute logarithms and exponentials with an arbitrary fixed base in 2019.<ref name="Luo_2019_TVLSI"/><ref name="Luo_2019_TVLSI_c"/><ref name="Wang_2020_tvlsi"/><ref name="Mopuri_2019_Nth"/><ref name="Vachhani_2020"/> Theoretically, Hyperbolic CORDIC is a special case of GH CORDIC.<ref name="Luo_2019_TVLSI"/>

Originally, CORDIC was implemented only using the [[binary numeral system]] and despite Meggitt suggesting the use of the decimal system for his pseudo-multiplication approach, decimal CORDIC continued to remain mostly unheard of for several more years, so that [[Hermann Schmid (computer scientist)|Hermann Schmid]] and Anthony Bogacki still suggested it as a novelty as late as 1973<ref name="Schmid_1974"/><ref name="Schmid_1983"/><ref name="Schmid_1973"/><ref name="Franke_1973"/><ref name="Muller_2006"/> and it was found only later that Hewlett-Packard had implemented it in 1966 already.<ref name="Volder_2000"/><ref name="Schmid_1983"/><ref name="Cochran_1966"/><ref name="Cochran_2010_1"/>

Decimal CORDIC became widely used in [[pocket calculator]]s,<ref name="Schmid_1983"/> most of which operate in binary-coded decimal (BCD) rather than binary. This change in the input and output format did not alter CORDIC's core calculation algorithms. CORDIC is particularly well-suited for handheld calculators, in which low cost – and thus low chip gate count – is much more important than speed.

CORDIC has been implemented in the [[ARM architecture|ARM-based]] [[STM32|STM32G4]], [[Intel 8087]],<ref name="Muller_2006"/><ref name="Nave_1983"/><ref name="Palmer_1984"/><ref name="Glass_1990"/><ref name="Jarvis_1990"/> [[Intel 80287|80287]],<ref name="Jarvis_1990"/><ref name="Yuen_1988"/> [[Intel 80387|80387]]<ref name="Jarvis_1990"/><ref name="Yuen_1988"/> up to the [[Intel 80486|80486]]<ref name="Muller_2006"/> coprocessor series as well as in the [[Motorola 68881]]<ref name="Muller_2006"/><ref name="Nave_1983"/> and [[Motorola 68882|68882]] for some kinds of floating-point instructions, mainly as a way to reduce the gate counts (and complexity) of the [[floating-point unit|FPU]] sub-system.