76-543: CORDIC ( coordinate rotation digital computer ), Volder's algorithm , 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 to calculate trigonometric functions , hyperbolic functions , square roots , multiplications , divisions , and exponentials and logarithms with arbitrary base, typically converging with one digit (or bit) per iteration. CORDIC
152-582: A = sup x ∈ A x {\displaystyle a=\sup _{x\in A}x} and b = sup y ∈ B y , {\displaystyle b=\sup _{y\in B}y,} then a ⋅ b = sup x ∈ A , y ∈ B x ⋅ y . {\displaystyle a\cdot b=\sup _{x\in A,y\in B}x\cdot y.} In particular,
228-478: A fixed-point desktop calculator utilizing his binary CORDIC algorithm. The design was introduced to Hewlett-Packard 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
304-461: A multiplication table of memorized or consulted products of small numbers (typically any two numbers from 0 to 9). However, one method, the peasant multiplication algorithm, does not. The example below illustrates "long multiplication" (the "standard algorithm", "grade-school multiplication"): In some countries such as Germany , the above multiplication is depicted similarly but with the original product kept horizontal and computation starting with
380-411: A rectangle (for whole numbers) or as finding the area of a rectangle whose sides have some given lengths . The area of a rectangle does not depend on which side is measured first—a consequence of the commutative property. The product of two measurements (or physical quantities ) is a new type of measurement, usually with a derived unit . For example, multiplying the lengths (in meters or feet) of
456-461: 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
532-515: 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 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
608-414: 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 . In two of the publications by Vladimir Baykov, it was proposed to use the double iterations method for the implementation of the functions: arcsine, arccosine, natural logarithm, exponential function, as well as for the calculation of
684-605: 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 , Raytheon , and Collins Radio . Volder teamed up with Malcolm McMillan to build Athena ,
760-421: A fixed-point format. To determine the sine or cosine for an angle β {\displaystyle \beta } , the y or x coordinate of a point on the unit circle corresponding to the desired angle must be found. Using CORDIC, one would start with the vector v 0 {\displaystyle v_{0}} : In the first iteration, this vector is rotated 45° counterclockwise to get
836-576: A list of the first twenty multiples of a certain principal number n : n , 2 n , ..., 20 n ; followed by the multiples of 10 n : 30 n 40 n , and 50 n . Then to compute any sexagesimal product, say 53 n , one only needed to add 50 n and 3 n computed from the table. In the mathematical text Zhoubi Suanjing , dated prior to 300 BC, and the Nine Chapters on the Mathematical Art , multiplication calculations were written out in words, although
SECTION 10
#1733105106049912-616: A multiplication operation is called a product . The multiplication of whole numbers may be thought of as repeated addition ; that is, the multiplication of two numbers is equivalent to adding as many copies of one of them, the multiplicand , as the quantity of the other one, the multiplier ; both numbers can be referred to as factors . For example, the expression 3 × 4 {\displaystyle 3\times 4} , phrased as "3 times 4" or "3 multiplied by 4", can be evaluated by adding 3 copies of 4 together: Here, 3 (the multiplier ) and 4 (the multiplicand ) are
988-456: A multiplication sign (such as ⋅ or × ), while the asterisk appeared on every keyboard. This usage originated in the FORTRAN programming language. The numbers to be multiplied are generally called the "factors" (as in factorization ). The number to be multiplied is the "multiplicand", and the number by which it is multiplied is the "multiplier". Usually, the multiplier is placed first, and
1064-422: A multiplier-based or CORDIC-based implementation will depend on the context. The multiplication of two complex numbers 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
1140-567: A nonzero natural number, or minus a nonzero natural number. The product of zero and another integer is always zero. The product of two nonzero integers is determined by the product of their positive amounts , combined with the sign derived from the following rule: × + − + + − − − + {\displaystyle {\begin{array}{|c|c c|}\hline \times &+&-\\\hline +&+&-\\-&-&+\\\hline \end{array}}} (This rule
1216-450: 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 –
1292-501: A professor of mathematics at Princeton University , wrote the following: These place value decimal arithmetic algorithms were introduced to Arab countries by Al Khwarizmi in the early 9th century and popularized in the Western world by Fibonacci in the 13th century. Grid method multiplication , or the box method, is used in primary schools in England and Wales and in some areas of
1368-553: A prototypical computer implementing it. The report also discussed the possibility to compute hyperbolic coordinate rotation , logarithms and exponential functions with modified CORDIC algorithms. Utilizing CORDIC for multiplication 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 (BCD). In 1958, Convair finally started to build
1444-651: A rotation, which is performed by multiplying the vector v i {\displaystyle v_{i}} with the rotation matrix R i {\displaystyle R_{i}} : The rotation matrix is given by Using the trigonometric identity : the cosine factor can be taken out to give: The expression for the rotated vector v i + 1 = R i v i {\displaystyle v_{i+1}=R_{i}v_{i}} then becomes: where x i {\displaystyle x_{i}} and y i {\displaystyle y_{i}} are
1520-422: A scaling factor K ( n ) {\displaystyle K(n)} : 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 v 0 {\displaystyle v_{0}} and hence saving a multiplication. Additionally, it can be noted that to allow further reduction of
1596-430: Is a consequence of the distributivity of multiplication over addition, and is not an additional rule .) In words: Two fractions can be multiplied by multiplying their numerators and denominators: There are several equivalent ways to define formally the real numbers; see Construction of the real numbers . The definition of multiplication is a part of all these definitions. A fundamental aspect of these definitions
SECTION 20
#17331051060491672-987: Is both a multiple of 3 and a multiple of 5. The product of two numbers or the multiplication between two numbers can be defined for common special cases: natural numbers, integers, rational numbers, real numbers, complex numbers, and quaternions. The product of two natural numbers r , s ∈ N {\displaystyle r,s\in \mathbb {N} } is defined as: r ⋅ s ≡ ∑ i = 1 s r = r + r + ⋯ + r ⏟ s times ≡ ∑ j = 1 r s = s + s + ⋯ + s ⏟ r times . {\displaystyle r\cdot s\equiv \sum _{i=1}^{s}r=\underbrace {r+r+\cdots +r} _{s{\text{ times}}}\equiv \sum _{j=1}^{r}s=\underbrace {s+s+\cdots +s} _{r{\text{ times}}}.} An integer can be either zero,
1748-572: Is much more important than speed. CORDIC has been implemented in the ARM-based STM32G4 , Intel 8087 , 80287 , 80387 up to the 80486 coprocessor series as well as in the Motorola 68881 and 68882 for some kinds of floating-point instructions, mainly as a way to reduce the gate counts (and complexity) of the FPU sub-system. CORDIC uses simple shift-add operations for several computing tasks such as
1824-491: Is often written using the multiplication sign (either × or × {\displaystyle \times } ) between the terms (that is, in infix notation ). For example, There are other mathematical notations for multiplication: In computer programming , the asterisk (as in 5*2 ) is still the most common notation. This is due to the fact that most computers historically were limited to small character sets (such as ASCII and EBCDIC ) that lacked
1900-404: Is positive, then σ i {\displaystyle \sigma _{i}} is +1, otherwise it is −1. The following trigonometric identity can be used to replace the cosine: giving this multiplier for each iteration: The K i {\displaystyle K_{i}} factors can then be taken out of the iterative process and applied all at once afterwards with
1976-760: Is slightly more complex than CORDIC, but has the advantage that it does not need a scaling factor ( K ). Jack E. Volder Jack Edward Volder (1924–2013 ) was an American electrical engineer. He is best known for inventing the CORDIC algorithm. Jack Volder was born in Fort Worth, Texas . During World War II, he served as a B-24 flight engineer. After the war, he studied electrical engineering, graduating from Texas Technological College in 1949. He first joined Allis-Chalmers in Milwaukee, Wisconsin before returning to Fort Worth to work at Convair in 1951, where he worked in
2052-427: Is such that tan ( φ ) = 2 − n {\displaystyle \tan(\varphi )=2^{-n}} , and K n := 1 + 2 − 2 n {\displaystyle K_{n}:={\sqrt {1+2^{-2n}}}} . His research led to an internal technical report proposing the CORDIC algorithm to solve sine and cosine functions and
2128-394: Is that every real number can be approximated to any accuracy by rational numbers . A standard way for expressing this is that every real number is the least upper bound of a set of rational numbers. In particular, every positive real number is the least upper bound of the truncations of its infinite decimal representation ; for example, π {\displaystyle \pi }
2204-421: Is that the magnitudes are multiplied and the arguments are added. The product of two quaternions can be found in the article on quaternions . Note, in this case, that a ⋅ b {\displaystyle a\cdot b} and b ⋅ a {\displaystyle b\cdot a} are in general different. Many common methods for multiplying numbers using pencil and paper require
2280-535: 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 optimization, may be used to control both kinds of error. 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,
2356-624: 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 x {\displaystyle x} (in radians) by computing the exponential of 0 + i x {\displaystyle 0+ix} , which is cis ( x ) = cos ( x ) + i sin ( x ) {\displaystyle \operatorname {cis} (x)=\cos(x)+i\sin(x)} . The BKM algorithm
CORDIC - Misplaced Pages Continue
2432-412: Is the least upper bound of { 3 , 3.1 , 3.14 , 3.141 , … } . {\displaystyle \{3,\;3.1,\;3.14,\;3.141,\ldots \}.} A fundamental property of real numbers is that rational approximations are compatible with arithmetic operations , and, in particular, with multiplication. This means that, if a and b are positive real numbers such that
2508-568: Is the number of digits), i.e. for each digit of the result. For the natural logarithm, exponential, hyperbolic sine, cosine and arctangent, R {\displaystyle R} iterations should be performed for each value i {\displaystyle i} . For the functions arcsine and arccosine, two R − 1 {\displaystyle R-1} iterations should be performed for each number digit, i.e. for each value of i {\displaystyle i} . For inverse hyperbolic sine and arcosine functions,
2584-445: 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 microcontrollers and field-programmable gate arrays or FPGAs), as the only operations they require are additions , subtractions , bitshift and lookup tables . As such, they all belong to
2660-522: The AN/UYK-7 computer. In 1975 he joined Hughes Aircraft Company . He married in 1949 and had children and grandchildren. Multiplication Multiplication (often denoted by the cross symbol × , by the mid-line dot operator ⋅ , by juxtaposition , or, on computers , by an asterisk * ) is one of the four elementary mathematical operations of arithmetic , with the other ones being addition , subtraction , and division . The result of
2736-459: The Marchant , automated multiplication of up to 10-digit numbers. Modern electronic computers and calculators have greatly reduced the need for multiplication by hand. Methods of multiplication were documented in the writings of ancient Egyptian , Greek, Indian, and Chinese civilizations. The Ishango bone , dated to about 18,000 to 20,000 BC, may hint at a knowledge of multiplication in
2812-627: The Upper Paleolithic era in Central Africa , but this is speculative. The Egyptian method of multiplication of integers and fractions, which is documented in the Rhind Mathematical Papyrus , was by successive additions and doubling. For instance, to find the product of 13 and 21 one had to double 21 three times, obtaining 2 × 21 = 42 , 4 × 21 = 2 × 42 = 84 , 8 × 21 = 2 × 84 = 168 . The full product could then be found by adding
2888-547: 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 : where φ {\displaystyle \varphi }
2964-468: The aeroelectronics department. Here he initiated research into the CORDIC algorithm in 1956. It was used in specialized flight control and radar computer systems. In 1959, he published a highly cited description of the algorithm. Volder left Convair before completion of the first such computer in 1961, but did occasional consulting for them. In 1971, he joined Litton Data Systems in California , working on
3040-492: The discrete Fourier transform reduce the computational complexity to O ( n log n log log n ) . In 2016, the factor log log n was replaced by a function that increases much slower, though still not constant. In March 2019, David Harvey and Joris van der Hoeven submitted a paper presenting an integer multiplication algorithm with a complexity of O ( n log n ) . {\displaystyle O(n\log n).} The algorithm, also based on
3116-568: The factors , and 12 is the product . One of the main properties of multiplication is the commutative property , which states in this case that adding 3 copies of 4 gives the same result as adding 4 copies of 3: Thus, the designation of multiplier and multiplicand does not affect the result of the multiplication. Systematic generalizations of this basic definition define the multiplication of integers (including negative numbers), rational numbers (fractions), and real numbers. Multiplication can also be visualized as counting objects arranged in
CORDIC - Misplaced Pages Continue
3192-412: The x axis) by an angle between −90° and +90°. Decisions on the direction of the rotation depend on β i {\displaystyle \beta _{i}} being positive or negative. The vectoring-mode of operation requires a slight modification of the algorithm. It starts with a vector whose x coordinate is positive whereas the y coordinate is arbitrary. Successive rotations have
3268-518: 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
3344-508: The United States to help teach an understanding of how multiple digit multiplication works. An example of multiplying 34 by 13 would be to lay the numbers out in a grid as follows: and then add the entries. The classical method of multiplying two n -digit numbers requires n digit multiplications. Multiplication algorithms have been designed that reduce the computation time considerably when multiplying large numbers. Methods based on
3420-571: The algorithm into the Unified CORDIC algorithm in 1971, allowing it to calculate hyperbolic functions , natural exponentials , natural logarithms , multiplications , divisions , and square roots . The CORDIC subroutines 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
3496-450: The algorithm's complexity. Some applications may avoid correcting for K {\displaystyle K} altogether, resulting in a processing gain A {\displaystyle A} : After a sufficient number of iterations, the vector's angle will be close to the wanted angle β {\displaystyle \beta } . For most ordinary purposes, 40 iterations ( n = 40) are sufficient to obtain
3572-418: The appropriate terms found in the doubling sequence: The Babylonians used a sexagesimal positional number system , analogous to the modern-day decimal system . Thus, Babylonian multiplication was very similar to modern decimal multiplication. Because of the relative difficulty of remembering 60 × 60 different products, Babylonian mathematicians employed multiplication tables . These tables consisted of
3648-502: The calculation of trigonometric, hyperbolic and logarithmic functions, real and complex multiplications, division, square-root calculation, solution of linear systems, eigenvalue estimation, singular value decomposition , QR factorization and many others. As a consequence, CORDIC has been used for applications in diverse areas such as signal and image processing , communication systems , robotics and 3D graphics apart from general scientific and technical computation. The algorithm
3724-448: 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. 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
3800-471: The components of v i {\displaystyle v_{i}} . Setting the angle γ i {\displaystyle \gamma _{i}} for each iteration such that tan ( γ i ) = ± 2 − i {\displaystyle \tan(\gamma _{i})=\pm 2^{-i}} still yields a series that converges to every possible output value. The multiplication with
3876-437: 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 with radix R {\displaystyle R} showed that for the functions sine, cosine, arctangent, it is enough to perform R − 1 {\displaystyle R-1} iterations for each value of i (i = 0 or 1 to n, where n
SECTION 50
#17331051060493952-403: 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 σ {\displaystyle \sigma } ). 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
4028-576: The early Chinese mathematicians employed Rod calculus involving place value addition, subtraction, multiplication, and division. The Chinese were already using a decimal multiplication table by the end of the Warring States period. The modern method of multiplication based on the Hindu–Arabic numeral system was first described by Brahmagupta . Brahmagupta gave rules for addition, subtraction, multiplication, and division. Henry Burchard Fine , then
4104-485: The fast Fourier transform, is conjectured to be asymptotically optimal. The algorithm is not practically useful, as it only becomes faster for multiplying extremely large numbers (having more than 2 bits). One can only meaningfully add or subtract quantities of the same type, but quantities of different types can be multiplied or divided without problems. For example, four bags with three marbles each can be thought of as: When two measurements are multiplied together,
4180-416: The first digit of the multiplier: Multiplying numbers to more than a couple of decimal places by hand is tedious and error-prone. Common logarithms were invented to simplify such calculations, since adding logarithms is equivalent to multiplying. The slide rule allowed numbers to be quickly multiplied to about three places of accuracy. Beginning in the early 20th century, mechanical calculators , such as
4256-509: 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 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
4332-413: The fundamental idea of multiplication. The product of a sequence, vector multiplication , complex numbers , and matrices are all examples where this can be seen. These more advanced constructs tend to affect the basic properties in their own ways, such as becoming noncommutative in matrices and some forms of vector multiplication or changing the sign of complex numbers. In arithmetic , multiplication
4408-411: 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 β i {\displaystyle \beta _{i}} 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
4484-696: 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 = 0 , 0 , 1 , 1 , 2 , 2 … {\displaystyle i=0,0,1,1,2,2\dots } . Whereas with ordinary iterations: i = 0 , 1 , 2 … {\displaystyle i=0,1,2\dots } . The double iteration method guarantees
4560-419: The multiplicand is placed second; however, sometimes the first factor is considered the multiplicand and the second the multiplier. Also, as the result of multiplication does not depend on the order of the factors, the distinction between "multiplicand" and "multiplier" is useful only at a very elementary level and in some multiplication algorithms , such as the long multiplication . Therefore, in some sources,
4636-439: 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. 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 radians and represented in
SECTION 60
#17331051060494712-508: The number of gates required to implement the functions it supports should be minimized (e.g., in an FPGA or ASIC ). 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
4788-407: The number of iterations will be 2 R {\displaystyle 2R} for each i {\displaystyle i} , that is, for each result digit. 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
4864-399: The others. Thus, 2 × π {\displaystyle 2\times \pi } is a multiple of π {\displaystyle \pi } , as is 5133 × 486 × π {\displaystyle 5133\times 486\times \pi } . A product of integers is a multiple of each factor; for example, 15 is the product of 3 and 5 and
4940-416: The product of two positive real numbers is the least upper bound of the term-by-term products of the sequences of their decimal representations. As changing the signs transforms least upper bounds into greatest lower bounds, the simplest way to deal with a multiplication involving one or two negative numbers, is to use the rule of signs described above in § Product of two integers . The construction of
5016-727: 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 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
5092-505: The real numbers through Cauchy sequences is often preferred in order to avoid consideration of the four possible sign configurations. Two complex numbers can be multiplied by the distributive law and the fact that i 2 = − 1 {\displaystyle i^{2}=-1} , as follows: The geometric meaning of complex multiplication can be understood by rewriting complex numbers in polar coordinates : Furthermore, from which one obtains The geometric meaning
5168-403: The table size. As can be seen in the illustration above, the sine of the angle β {\displaystyle \beta } is the y coordinate of the final vector v n , {\displaystyle v_{n},} while the x coordinate is the cosine value. The rotation-mode algorithm described above can rotate any vector (not only a unit vector aligned along
5244-392: The tangent can therefore 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: and σ i {\displaystyle \sigma _{i}} is used to determine the direction of the rotation: if the angle γ i {\displaystyle \gamma _{i}}
5320-405: The term "multiplicand" is regarded as a synonym for "factor". In algebra, a number that is the multiplier of a variable or expression (e.g., the 3 in 3 x y 2 {\displaystyle 3xy^{2}} ) is called a coefficient . The result of a multiplication is called a product . When one factor is an integer, the product is a multiple of the other or of the product of
5396-454: The two sides of a rectangle gives its area (in square meters or square feet). Such a product is the subject of dimensional analysis . The inverse operation of multiplication is division . For example, since 4 multiplied by 3 equals 12, 12 divided by 3 equals 4. Indeed, multiplication by 3, followed by division by 3, yields the original number. The division of a number other than 0 by itself equals 1. Several mathematical concepts expand upon
5472-568: 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 desktop calculator he had completed in DTL logic in December 1964. This project resulted in
5548-557: The vector v 1 {\displaystyle v_{1}} . 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 γ i = arctan ( 2 − i ) {\displaystyle \gamma _{i}=\arctan {(2^{-i})}} for i = 0 , 1 , 2 , … {\displaystyle i=0,1,2,\dots } . More formally, every iteration calculates
5624-521: The vectoring mode is the transformation from rectangular to polar coordinates. 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. The number of logic gates 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
5700-632: The wanted angle β {\displaystyle \beta } , if β n + 1 {\displaystyle \beta _{n+1}} is positive, the rotation is clockwise, otherwise it is negative and the rotation is counterclockwise: The values of γ n {\displaystyle \gamma _{n}} must also be precomputed and stored. For small angles it can be approximated with arctan ( γ n ) ≈ γ n {\displaystyle \arctan(\gamma _{n})\approx \gamma _{n}} to reduce
5776-553: Was used in the navigational system of the Apollo program 's Lunar Roving Vehicle to compute bearing and range, or distance from the Lunar module . CORDIC was used to implement the Intel 8087 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
#48951