This month, it seemed like fate destined me to do a Resource Page on math functions. Someone asked a question on the Circuit Cellar newsgroups about how to do math functions on a processor with limited resources like the Motorola 6805. The next day someone asked me if I could redesign the controls for their Industrial Plasma Cutter System because its old Intel 8231 math chip went bad.  So, I'll share what I found about how to do math in systems of limited resources like PICs, FPGAs and such.

In 1959, J.E.Volder came up with a system that he dubbed COordinate Rotation DIgital Computer (CORDIC). It is an iterative algorithm for calculating trig functions including sine, cosine, magnitude, and phase. It is particularly suited to hardware implementations because it does not require any multiplies.

Volder, J.E., 1959, The CORDIC Trigonometric Computing Technique, IRE Transactions on Electronic Computers, V. EC-8, No. 3, pp. 330-334

An example of using shifts and adds (or shifts and subtracts) for multiplication can be seen in a technique called Start-Chain, which is described in  Dr. Dobb's Journal, March 1987  "Optimizing Integer Multiplications by Constant Multipliers" by Robert D. Grappel. C code for doing this is on the Circuit Cellar FTP site in a file named STARMULT.ZIP.  Also, see Jarvis, P.; Implementing CORDIC Algorithms, Dr. Dobb's Journal, Oct. 1990.

For example, say you want to multiply a variable by the constant 7. This can be done via a shift (depending on the processor, it may be a single shift or multiple shift instructions) and a single subtract.

Rw = R1 = 7
Rw <<= 3
RW -=  R1

Rw = R1 = 321
Rw <<= 2
RW +=  R1
Rw <<= 6
RW +=  R1

Calculators frequently use the CORDIC algorithm to produce the values of transcendental functions.  Bruce Edwards describes this usage in his "CORDIC Algorithm -  How Do Calculators Calculate?."

Circuit Cellar's Ingo Cyliax covered how to do CORDIC on a Microchip PIC, in "CORDIC (COordinate Rotation DIgital Computer), the swiss army knife for computing math functions...".

"If you need high-precision trig functions with a small look-up table (N entries) and good performance, give CORDIC a try.  I was able to implement a 12-bit CORDIC routine on a Parallax BASIC Stamp2. The C code used to calculate the table is in the sidebar (you didn't really think I did it with pencil and paper ?)."

The DSP Guru site offers the CORDIC FAQ by Grant R. Griffin. They have examples in both C code and in the form of an Excel spreadsheet.

Some links of interest from the FAQ:

• MATH REAL - A VHDL math library that uses CORDIC.
• CORDIC algorithm inverse tangent by Frontier Design is provided in C, VHDL, and Verilog formats.

Implementation of various CORDIC Architectures - "As intended by Jack E. Volder, the CORDIC algorithm only performs shift and add operations and is, therefore, easy to implement and resource friendly. However, when implementing the CORDIC algorithm you can choose from various design methodologies and balance circuit complexity with respect to performance. The most obvious methods of implementing a CORDIC, bit-serial, bit-parallel, unrolled, and iterative are described and compared." - Norbert Lindlbauer.

For a small fee you can download A survey of CORDIC algorithms for FPGA based computers Pages 191-200 Ray Andraka from the Proceedings of the 1998 ACM/SIGDA sixth international symposium on field programmable gate arrays, February 22–25, 1998, Monterey, CA USA.  You can also find some of the related papers for free at Ray Andraka's home page.

Tomás Lang, Member and Elisardo Antelo show how to extend CORDIC for other functions in CORDIC Vectoring with Arbitrary Target Value.

From the same site you can find Design CORDIC-based Systems Using Term Rewriting Techniques by Xiaobo (Sharon) Hu and M. Lyle Benson.

HammerCores by Altera CORDIC Functions CDPP & CDPS White Paper implement rectangular to polar coordinates.

Mathcad and C code can be found in Numerical Methods for DSP Systems Inc. from Don Morgan's book of the same title.

Not directly CORDIC related but interesting perhaps even useful, sometimes finding the correct mathematical constants is the hardest part of the math problem.

Favorite Mathematical Constants by Steven Finch (part of the Research and Development Team at MathSoft, Inc.) shows that math at times can be entertaining.

"All numbers are not created equal; that certain constants appear at all and then echo throughout mathematics, in seemingly independent ways, is a source of fascination. Just as physical constants provide 'boundary conditions' for the physical universe, mathematical constants somehow characterize the structure of mathematics."

• Ever since I read "The Hitchhikers Guide To The Galaxy" by Douglas Adams, I've always wanted to know what is largest prime number?
• You could discover one of the most coveted finds in all of Mathematics—a new Mersenne prime number.
• Proth.exe - by Yves Gallot A Windows program for finding large primes.

You have the chance at winning from $1000 to $250,000 for certain primes and factorizations from The Prime Pages.

All product names and logos contained herein are the trademarks of their respective holders.

The fact that an item is listed here does not mean we promote its use for your application.  No endorsement of the vendor or product is made or implied.