CORDIC (for "coordinate rotation digital computer"), also known as Volder's algorithm, or: Digit-by-digit method Circular CORDIC (Jack E. Volder),
Linear CORDIC, Hyperbolic CORDIC (John Stephen Walther),
and Generalized Hyperbolic CORDIC (GH CORDIC) (Yuanyong Luo et al.),
is a simple and efficient
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
to calculate
trigonometric function
In mathematics, the trigonometric functions (also called circular functions, angle functions or goniometric functions) are real functions which relate an angle of a right-angled triangle to ratios of two side lengths. They are widely used in a ...
s,
hyperbolic function
In mathematics, hyperbolic functions are analogues of the ordinary trigonometric functions, but defined using the hyperbola rather than the circle. Just as the points form a circle with a unit radius, the points form the right half of the u ...
s,
square roots,
multiplications,
divisions, and
exponentials and
logarithms with arbitrary base, typically converging with one digit (or bit) per iteration. CORDIC is therefore also an example of digit-by-digit algorithms. 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
microcontroller
A microcontroller (MCU for ''microcontroller unit'', often also MC, UC, or μC) is a small computer on a single VLSI integrated circuit (IC) chip. A microcontroller contains one or more CPUs ( processor cores) along with memory and programmabl ...
s and
FPGA
A field-programmable gate array (FPGA) is an integrated circuit designed to be configured by a customer or a designer after manufacturinghence the term '' field-programmable''. The FPGA configuration is generally specified using a hardware d ...
s), as the only operations it requires are
addition
Addition (usually signified by the plus symbol ) is one of the four basic operations of arithmetic, the other three being subtraction, multiplication and division. The addition of two whole numbers results in the total amount or '' sum'' ...
s,
subtraction
Subtraction is an arithmetic operation that represents the operation of removing objects from a collection. Subtraction is signified by the minus sign, . For example, in the adjacent picture, there are peaches—meaning 5 peaches with 2 taken ...
s,
bitshift
In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic operat ...
and
lookup table
In computer science, a lookup table (LUT) is an array that replaces runtime computation with a simpler array indexing operation. The process is termed as "direct addressing" and LUTs differ from hash tables in a way that, to retrieve a value v w ...
s. As such, they all belong to the class of
shift-and-add algorithm
A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are more efficient than others. Efficient multiplication algorithms have existed since the advent of the d ...
s. In computer science, CORDIC is often used to implement
floating-point arithmetic
In computing, floating-point arithmetic (FP) is arithmetic that represents real numbers approximately, using an integer with a fixed precision, called the significand, scaled by an integer exponent of a fixed base. For example, 12.345 can be ...
when the target platform lacks hardware multiply for cost or space reasons.
History
Similar mathematical techniques were published by
Henry Briggs as early as 1624
and Robert Flower in 1771,
but CORDIC is better optimized for low-complexity finite-state CPUs.
CORDIC was conceived in 1956
by
Jack E. Volder at the
aeroelectronics department of
Convair out of necessity to replace the
analog resolver in the
B-58 bomber's navigation computer with a more accurate and faster real-time digital solution.
Therefore, CORDIC is sometimes referred to as a
digital resolver.
In his research Volder was inspired by a formula in the 1946 edition of the ''
CRC Handbook of Chemistry and Physics
The ''CRC Handbook of Chemistry and Physics'' is a comprehensive one-volume reference resource for science research. First published in 1914, it is currently () in its 103rd edition, published in 2022. It is sometimes nicknamed the "Rubber Bible ...
'':
:
with
,
.
His research led to an internal technical report proposing the CORDIC algorithm to solve
sine
In mathematics, sine and cosine are trigonometric functions of an angle. The sine and cosine of an acute angle are defined in the context of a right triangle: for the specified angle, its sine is the ratio of the length of the side that is opp ...
and
cosine functions and a prototypical computer implementing it.
The report also discussed the possibility to compute hyperbolic
coordinate rotation,
logarithm
In mathematics, the logarithm is the inverse function to exponentiation. That means the logarithm of a number to the base is the exponent to which must be raised, to produce . For example, since , the ''logarithm base'' 10 ...
s and
exponential function
The exponential function is a mathematical function denoted by f(x)=\exp(x) or e^x (where the argument is written as an exponent). Unless otherwise specified, the term generally refers to the positive-valued function of a real variable, ...
s with modified CORDIC algorithms.
Utilizing CORDIC for
multiplication
Multiplication (often denoted by the Multiplication sign, cross symbol , by the mid-line #Notation and terminology, dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four Elementary arithmetic, elementary Op ...
and
division was also conceived at this time.
Based on the CORDIC principle, Dan H. Daggett, a colleague of Volder at Convair, developed conversion algorithms between binary and
binary-coded decimal
In computing and electronic systems, binary-coded decimal (BCD) is a class of binary encodings of decimal numbers where each digit is represented by a fixed number of bits, usually four or eight. Sometimes, special bit patterns are used ...
(BCD).
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.
More universal ''CORDIC II'' models ''A'' (stationary) and ''B'' (airborne) were built and tested by Daggett and Harry Schuss in 1962.
Volder's CORDIC algorithm was first described in public in 1959,
which caused it to be incorporated into navigation computers by companies including
Martin-Orlando,
Computer Control,
Litton,
Kearfott,
Lear-Siegler,
Sperry Sperry may refer to:
Places
In the United States:
* Sperry, Iowa, community in Des Moines County
*Sperry, Missouri
* Sperry, Oklahoma, town in Tulsa County
*Sperry Chalet, historic backcountry chalet, Glacier National Park, Montana
*Sperry Glacier ...
,
Raytheon, and
Collins Radio
Rockwell Collins was a multinational corporation headquartered in Cedar Rapids, Iowa, providing avionics and information technology systems and services to government agencies and aircraft manufacturers. It was formed when the Collins Radio Compa ...
.
Volder teamed up with Malcolm McMillan to build ''Athena'', a
fixed-point desktop calculator utilizing his binary CORDIC algorithm.
The design was introduced to
Hewlett-Packard
The Hewlett-Packard Company, commonly shortened to Hewlett-Packard ( ) or HP, was an American multinational information technology company headquartered in Palo Alto, California. HP developed and provided a wide variety of hardware components ...
in June 1965, but not accepted.
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 E. Meggitt (IBM
) had proposed as ''pseudo-multiplication'' and ''pseudo-division'' in 1961.
Meggitt's method also suggested the use of base 10
rather than
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,
built by and conceptually derived from
Thomas E. Osborne's prototypical ''Green Machine'', a four-function,
floating-point
In computing, floating-point arithmetic (FP) is arithmetic that represents real numbers approximately, using an integer with a fixed precision, called the significand, scaled by an integer exponent of a fixed base. For example, 12.345 can ...
desktop calculator he had completed in
DTL logic
in December 1964.
This project resulted in the public demonstration of Hewlett-Packard's first desktop calculator with scientific functions, the
hp 9100A in March 1968, with series production starting later that year.
When
Wang Laboratories
Wang Laboratories was a US computer company founded in 1951 by An Wang and G. Y. Chu. The company was successively headquartered in Cambridge, Massachusetts (1954–1963), Tewksbury, Massachusetts (1963–1976), and finally in Lowell, Massachus ...
found that the hp 9100A used
an approach similar to the ''factor combining'' method in their earlier
LOCI-1 (September 1964) and
LOCI-2 (January 1965)
''Logarithmic Computing Instrument'' desktop calculators,
they unsuccessfully accused Hewlett-Packard of infringement of one of
An Wang's patents in 1968.
John Stephen Walther at Hewlett-Packard generalized the algorithm into the ''Unified CORDIC'' algorithm in 1971, allowing it to calculate
hyperbolic functions,
natural exponentials,
natural logarithm
The natural logarithm of a number is its logarithm to the base of the mathematical constant , which is an irrational and transcendental number approximately equal to . The natural logarithm of is generally written as , , or sometimes, if ...
s,
multiplication
Multiplication (often denoted by the Multiplication sign, cross symbol , by the mid-line #Notation and terminology, dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four Elementary arithmetic, elementary Op ...
s,
divisions, and
square root
In mathematics, a square root of a number is a number such that ; in other words, a number whose '' square'' (the result of multiplying the number by itself, or ⋅ ) is . For example, 4 and −4 are square roots of 16, because .
...
s.
The CORDIC
subroutines
In computer programming, a function or subroutine is a sequence of program instructions that performs a specific task, packaged as a unit. This unit can then be used in programs wherever that particular task should be performed.
Functions may ...
for trigonometric and hyperbolic functions could share most of their code.
This development resulted in the first
scientific handheld calculator, the
HP-35 in 1972.
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.
Theoretically, Hyperbolic CORDIC is a special case of GH CORDIC.
Originally, CORDIC was implemented only using the
binary numeral system
A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method of mathematical expression which uses only two symbols: typically "0" ( zero) and "1" (one).
The base-2 numeral system is a positional notati ...
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 and Anthony Bogacki still suggested it as a novelty as late as 1973
and it was found only later that Hewlett-Packard had implemented it in 1966 already.
Decimal CORDIC became widely used in
pocket calculators,
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-based STM32G4,
Intel 8087
The Intel 8087, announced in 1980, was the first x87 floating-point coprocessor for the 8086 line of microprocessors.
The purpose of the 8087 was to speed up computations for floating-point arithmetic, such as addition, subtraction, multiplic ...
,
80287
x87 is a floating-point-related subset of the x86 architecture instruction set. It originated as an extension of the 8086 instruction set in the form of optional floating-point coprocessors that worked in tandem with corresponding x86 CPUs. These ...
,
80387
x87 is a floating-point-related subset of the x86 architecture instruction set. It originated as an extension of the 8086 instruction set in the form of optional floating-point coprocessors that worked in tandem with corresponding x86 CPUs. These ...
up to the
80486
The Intel 486, officially named i486 and also known as 80486, is a microprocessor. It is a higher-performance follow-up to the Intel 386. The i486 was introduced in 1989. It represents the fourth generation of binary compatible CPUs following t ...
coprocessor series as well as in the
Motorola 68881
The Motorola 68881 and Motorola 68882 are floating-point units (FPUs) used in some computer systems in conjunction with Motorola's 32-bit 68020 or 68030 microprocessors. These coprocessors are external chips, designed before floating point math bec ...
and
68882
The Motorola 68881 and Motorola 68882 are floating-point units (FPUs) used in some computer systems in conjunction with Motorola's 32-bit 68020 or 68030 microprocessors. These coprocessors are external chips, designed before floating point math bec ...
for some kinds of floating-point instructions, mainly as a way to reduce the gate counts (and complexity) of the
FPU sub-system.
Applications
CORDIC uses simple shift-add operations for several computing tasks such as the calculation of trigonometric, hyperbolic and logarithmic functions, real and complex multiplications, division, square-root calculation, solution of linear systems,
eigenvalue
In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denote ...
estimation,
singular value decomposition
In linear algebra, the singular value decomposition (SVD) is a factorization of a real or complex matrix. It generalizes the eigendecomposition of a square normal matrix with an orthonormal eigenbasis to any \ m \times n\ matrix. It is re ...
,
QR factorization
In linear algebra, a QR decomposition, also known as a QR factorization or QU factorization, is a decomposition of a matrix ''A'' into a product ''A'' = ''QR'' of an orthogonal matrix ''Q'' and an upper triangular matrix ''R''. QR decom ...
and many others. As a consequence, CORDIC has been used for applications in diverse areas such as
signal and
image processing
An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensio ...
,
communication systems,
robotics
Robotics is an interdisciplinary branch of computer science and engineering. Robotics involves design, construction, operation, and use of robots. The goal of robotics is to design machines that can help and assist humans. Robotics integrat ...
and
3D graphics apart from general scientific and technical computation.
Hardware
The algorithm was used in the navigational system of the
Apollo program's
Lunar Roving Vehicle
The Lunar Roving Vehicle (LRV) is a battery-powered four-wheeled rover used on the Moon in the last three missions of the American Apollo program ( 15, 16, and 17) during 1971 and 1972. It is popularly called the Moon buggy, a play on the ...
to compute
bearing and range, or distance from the
Lunar module
The Apollo Lunar Module (LM ), originally designated the Lunar Excursion Module (LEM), was the lunar lander spacecraft that was flown between lunar orbit and the Moon's surface during the United States' Apollo program. It was the first crewed ...
.
CORDIC was used to implement the
Intel 8087
The Intel 8087, announced in 1980, was the first x87 floating-point coprocessor for the 8086 line of microprocessors.
The purpose of the 8087 was to speed up computations for floating-point arithmetic, such as addition, subtraction, multiplic ...
math coprocessor in 1980, avoiding the need to implement hardware multiplication.
CORDIC is generally faster than other approaches when a hardware multiplier is not available (e.g., a microcontroller), or when the number of gates required to implement the functions it supports should be minimized (e.g., in an FPGA or
ASIC
An application-specific integrated circuit (ASIC ) is an integrated circuit (IC) chip customized for a particular use, rather than intended for general-purpose use, such as a chip designed to run in a digital voice recorder or a high-efficie ...
).
In fact, CORDIC is a standard drop-in
IP in FPGA development applications such as Vivado for Xilinx, while a power series implementation is not due to the specificity of such an IP, i.e. CORDIC can compute many different functions (general purpose) while a hardware multiplier configured to execute power series implementations can only compute the function it was designed for.
On the other hand, when a hardware multiplier is available (''e.g.'', in a
DSP microprocessor), table-lookup methods and
power series
In mathematics, a power series (in one variable) is an infinite series of the form
\sum_^\infty a_n \left(x - c\right)^n = a_0 + a_1 (x - c) + a_2 (x - c)^2 + \dots
where ''an'' represents the coefficient of the ''n''th term and ''c'' is a con ...
are generally faster than CORDIC. In recent years, the CORDIC algorithm has been used extensively for various biomedical applications, especially in FPGA implementations.
The
STM32G4 series and certain
STM32H7 series of MCUs implement a CORDIC module to accelerate computations in various mixed signal applications such as graphics for
human-machine interface and
field oriented control of motors. While not as fast as a power series approximation, CORDIC is indeed faster than interpolating table based implementations such as the ones provided by the ARM CMSIS and C standard libraries.
Though the results may be slightly less accurate as the CORDIC modules provided only achieve 20 bits of precision in the result. For example, most of the performance difference compared to the ARM implementation is due to the overhead of the interpolation algorithm, which achieves full floating point precision (24 bits) and can likely achieve relative error to that precision.
Another benefit is that the CORDIC module is a coprocessor and can be run in parallel with other CPU tasks.
The issue with using Taylor series is that while they do provide small absolute error, they do not exhibit well behaved relative error.
Other means of polynomial approximation, such as
minimax
Minimax (sometimes MinMax, MM or saddle point) is a decision rule used in artificial intelligence, decision theory, game theory, statistics, and philosophy for ''mini''mizing the possible loss for a worst case (''max''imum loss) scenario. When ...
optimization, may be used to control both kinds of error.
Software
Many older systems with integer-only CPUs have implemented CORDIC to varying extents as part of their
IEEE floating-point libraries. As most modern general-purpose CPUs have floating-point registers with common operations such as add, subtract, multiply, divide, sine, cosine, square root, log
10, natural log, the need to implement CORDIC in them with software is nearly non-existent. Only microcontroller or special safety and time-constrained software applications would need to consider using CORDIC.
Modes of operation
Rotation mode
CORDIC can be used to calculate a number of different functions. This explanation shows how to use CORDIC in ''rotation mode'' to calculate the sine and cosine of an angle, assuming that the desired angle is given in
radian
The radian, denoted by the symbol rad, is the unit of angle in the International System of Units (SI) and is the standard unit of angular measure used in many areas of mathematics. The unit was formerly an SI supplementary unit (before that ...
s and represented in a fixed-point format. To determine the sine or cosine for an angle
, the ''y'' or ''x'' coordinate of a point on the
unit circle
In mathematics, a unit circle is a circle of unit radius—that is, a radius of 1. Frequently, especially in trigonometry, the unit circle is the circle of radius 1 centered at the origin (0, 0) in the Cartesian coordinate system in the Eucli ...
corresponding to the desired angle must be found. Using CORDIC, one would start with the vector
:
:
In the first iteration, this vector is rotated 45° counterclockwise to get the vector
. Successive iterations rotate the vector in one or the other direction by size-decreasing steps, until the desired angle has been achieved. Each step angle is
for
.
More formally, every iteration calculates a rotation, which is performed by multiplying the vector
with the
rotation matrix In linear algebra, a rotation matrix is a transformation matrix that is used to perform a rotation in Euclidean space. For example, using the convention below, the matrix
:R = \begin
\cos \theta & -\sin \theta \\
\sin \theta & \cos \theta
\ ...
:
:
The rotation matrix is given by
:
Using the following two
trigonometric identities:
:
the rotation matrix becomes
:
The expression for the rotated vector
then becomes
:
where
and
are the components of
. Restricting the angles
such that
, the multiplication with the tangent can be replaced by a division by a power of two, which is efficiently done in digital computer hardware using a
bit shift. The expression then becomes
:
where
:
and
is used to determine the direction of the rotation: if the angle
is positive, then
is +1, otherwise it is −1.
All
factors can be ignored in the iterative process and then applied all at once afterwards with a scaling factor
:
which is calculated in advance and stored in a table or as a single constant, if the number of iterations is fixed. This correction could also be made in advance, by scaling
and hence saving a multiplication. Additionally, it can be noted that
:
to allow further reduction of the algorithm's complexity. Some applications may avoid correcting for
altogether, resulting in a processing gain
:
:
After a sufficient number of iterations, the vector's angle will be close to the wanted angle
. For most ordinary purposes, 40 iterations (''n'' = 40) is sufficient to obtain the correct result to the 10th decimal place.
The only task left is to determine whether the rotation should be clockwise or counterclockwise at each iteration (choosing the value of
). This is done by keeping track of how much the angle was rotated at each iteration and subtracting that from the wanted angle; then in order to get closer to the wanted angle
, if
is positive, the rotation is clockwise, otherwise it is negative and the rotation is counterclockwise:
:
:
The values of
must also be precomputed and stored. But for small angles,
in fixed-point representation, reducing table size.
As can be seen in the illustration above, the sine of the angle
is the ''y'' coordinate of the final vector
while the ''x'' coordinate is the cosine value.
Vectoring mode
The rotation-mode algorithm described above can rotate any vector (not only a unit vector aligned along the ''x'' axis) by an angle between −90° and +90°. Decisions on the direction of the rotation depend on
being positive or negative.
The vectoring-mode of operation requires a slight modification of the algorithm. It starts with a vector the ''x'' coordinate of which is positive and the ''y'' coordinate is arbitrary. Successive rotations have the goal of rotating the vector to the ''x'' axis (and therefore reducing the ''y'' coordinate to zero). At each step, the value of ''y'' determines the direction of the rotation. The final value of
contains the total angle of rotation. The final value of ''x'' will be the magnitude of the original vector scaled by ''K''. So, an obvious use of the vectoring mode is the transformation from rectangular to polar coordinates.
Implementation
Software example
The following is a
MATLAB
MATLAB (an abbreviation of "MATrix LABoratory") is a proprietary multi-paradigm programming language and numeric computing environment developed by MathWorks. MATLAB allows matrix manipulations, plotting of functions and data, implementat ...
/
GNU Octave
GNU Octave is a high-level programming language primarily intended for scientific computing and numerical computation. Octave helps in solving linear and nonlinear problems numerically, and for performing other numerical experiments using a lan ...
implementation of CORDIC that does not rely on any
transcendental function
In mathematics, a transcendental function is an analytic function that does not satisfy a polynomial equation, in contrast to an algebraic function.
In other words, a transcendental function "transcends" algebra in that it cannot be expressed ...
s except in the precomputation of tables. If the number of iterations ''n'' is predetermined, then the second table can be replaced by a single constant. With MATLAB's standard double-precision arithmetic and "format long" printout, the results increase in accuracy for ''n'' up to about 48.
function v = cordic(beta,n)
% This function computes v = os(beta), sin(beta)(beta in radians)
% using n iterations. Increasing n will increase the precision.
if beta < -pi/2 , , beta > pi/2
if beta < 0
v = cordic(beta + pi, n);
else
v = cordic(beta - pi, n);
end
v = -v; % flip the sign for second or third quadrant
return
end
% Initialization of tables of constants used by CORDIC
% need a table of arctangents of negative powers of two, in radians:
% angles = atan(2.^-(0:27));
angles = [ ...
0.78539816339745 0.46364760900081 0.24497866312686 0.12435499454676 ...
0.06241880999596 0.03123983343027 0.01562372862048 0.00781234106010 ...
0.00390623013197 0.00195312251648 0.00097656218956 0.00048828121119 ...
0.00024414062015 0.00012207031189 0.00006103515617 0.00003051757812 ...
0.00001525878906 0.00000762939453 0.00000381469727 0.00000190734863 ...
0.00000095367432 0.00000047683716 0.00000023841858 0.00000011920929 ...
0.00000005960464 0.00000002980232 0.00000001490116 0.00000000745058 ];
% and a table of products of reciprocal lengths of vectors [1, 2^-2j]:
% Kvalues = cumprod(1./abs(1 + 1j*2.^(-(0:23))))
Kvalues = [ ...
0.70710678118655 0.63245553203368 0.61357199107790 0.60883391251775 ...
0.60764825625617 0.60735177014130 0.60727764409353 0.60725911229889 ...
0.60725447933256 0.60725332108988 0.60725303152913 0.60725295913894 ...
0.60725294104140 0.60725293651701 0.60725293538591 0.60725293510314 ...
0.60725293503245 0.60725293501477 0.60725293501035 0.60725293500925 ...
0.60725293500897 0.60725293500890 0.60725293500889 0.60725293500888 ];
Kn = Kvalues(min(n, length(Kvalues)));
% Initialize loop variables:
v = ;0 % start with 2-vector cosine and sine of zero
poweroftwo = 1;
angle = angles(1);
% Iterations
for j = 0:n-1;
if beta < 0
sigma = -1;
else
sigma = 1;
end
factor = sigma * poweroftwo;
% Note the matrix multiplication can be done using scaling by powers of two and addition subtraction
R = , -factor; factor, 1
v = R * v; % 2-by-2 matrix multiply
beta = beta - sigma * angle; % update the remaining angle
poweroftwo = poweroftwo / 2;
% update the angle from table, or eventually by just dividing by two
if j+2 > length(angles)
angle = angle / 2;
else
angle = angles(j+2);
end
end
% Adjust length of output vector to be os(beta), sin(beta)
v = v * Kn;
return
endfunction
The two-by-two
matrix multiplication can be carried out by a pair of simple shifts and adds.
x = v - sigma * (v * 2^(-j));
y = sigma * (v * 2^(-j)) + v
v = ; y
In Java the Math class has a
scalb(double x,int scale)
method to perform such a shift,
C has the
ldexp function,
and the x86 class of processors have the
fscale
floating point operation.
Hardware example
The number of
logic gate
A logic gate is an idealized or physical device implementing a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output. Depending on the context, the term may refer to an ideal logic ga ...
s for the implementation of a CORDIC is roughly comparable to the number required for a multiplier as both require combinations of shifts and additions. The choice for a multiplier-based or CORDIC-based implementation will depend on the context. The multiplication of two
complex number
In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the fo ...
s represented by their real and imaginary components (rectangular coordinates), for example, requires 4 multiplications, but could be realized by a single CORDIC operating on complex numbers represented by their polar coordinates, especially if the magnitude of the numbers is not relevant (multiplying a complex vector with a vector on the unit circle actually amounts to a rotation). CORDICs are often used in circuits for telecommunications such as
digital down converters.
Double iterations CORDIC
In the publications: http://baykov.de/CORDIC1972.htm and http://baykov.de/CORDIC1975.htm it was proposed to use the double iterations method for the implementation of the functions: arcsinX, arccosX, lnX, expX, as well as for calculation of the hyperbolic functions. Double iterations method consists in the fact that unlike the classical CORDIC method, where the iteration step value changes EVERY time, i.e. on each iteration, in the double iteration method, the iteration step value is repeated twice and changes only through one iteration. Hence the designation for the degree indicator for double iterations appeared: ''i'' = 1,1,2,2,3,3... Whereas with ordinary iterations: ''i'' = 1,2,3... The double iteration method guarantees the convergence of the method throughout the valid range of argument changes.
The generalization of the CORDIC convergence problems for the arbitrary positional number system http://baykov.de/CORDIC1985.htm with Radix R showed that for the functions sin, cos, arctg, it is enough to perform (R-1) iterations for each value of i (i = 0 or 1 to n, where n is the number of digits), i.e. for each digit of the result. For the functions ln, exp, sh, ch, arth, R iterations should be performed for each value i. For the functions arcsin and arccos 2 (R-1) iterations should be performed for each number digit, i.e. for each value of i.
For arsh, arch functions, the number of iterations will be 2R for each i, that is, for each result digit.
Related algorithms
CORDIC is part of the class of
"shift-and-add" algorithms, as are the logarithm and exponential algorithms derived from Henry Briggs' work. Another shift-and-add algorithm which can be used for computing many elementary functions is the
BKM algorithm, which is a generalization of the logarithm and exponential algorithms to the complex plane. For instance, BKM can be used to compute the sine and cosine of a real angle
(in radians) by computing the exponential of
, which is
. The BKM algorithm is slightly more complex than CORDIC, but has the advantage that it does not need a scaling factor (''K'').
See also
*
Methods of computing square roots
*
IEEE 754
The IEEE Standard for Floating-Point Arithmetic (IEEE 754) is a technical standard for floating-point arithmetic established in 1985 by the Institute of Electrical and Electronics Engineers (IEEE). The standard addressed many problems found ...
*
Floating-point unit
In computing, floating-point arithmetic (FP) is arithmetic that represents real numbers approximately, using an integer with a fixed precision, called the significand, scaled by an integer exponent of a fixed base. For example, 12.345 can be ...
s
*
Digital Circuits/CORDIC in Wikibooks
References
Further reading
* (NB. ''DIVIC'' stands for ''DIgital Variable Increments Computer''. Some sources erroneously refer to this as by ''J. M. Parini''.)
*
*
*
*
*
*
*
*
*
*
*
*
*
*
* (about CORDIC in
TI-58/
TI-59)
*
*
*
*
*
* (x+268 pages)
*
*
*
*
*
External links
*
Soft CORDIC IP (verilog HDL code)''CORDIC Bibliography Site''CORDIC implementation in verilogCORDIC Vectoring with Arbitrary Target ValuePicBasic Pro, Pic18 CORDIC math implementationPython CORDIC implementationSimple C code for fixed-point CORDIC*
ttp://bibix.nl/index.php?menu1=arx_ip Descriptions of hardware CORDICs in Arx with testbenches in C++ and VHDLAn Introduction to the CORDIC algorithmImplementation of the CORDIC Algorithm in a Digital Down-Converter50-th Anniversary of the CORDIC Algorithm*Implementation of the CORDIC Algorithm
fixed point C code for trigonometric and hyperbolic functionsC code for test and performance verification
{{DEFAULTSORT:Cordic
Digit-by-digit algorithms
Shift-and-add algorithms
Root-finding algorithms
Computer arithmetic
Numerical analysis
Trigonometry