Nuts and Volts - September 2007

Resources

Binary representation:
001010001110.010100100010

■ Java version 5 is available at http://java.sun.com/javase/down loads/index_jdk5.jsp.

CSD representation:
0010100100-10.010100100010

■ Information on the Texas Instruments MSP430 development kit is available at http://focus.ti.com/docs/toolsw/folders/print/ ez430-f2013.html.

Horner equations:
T1= X*2²+X
T2 = T1 * 2³+ X
T3 = T2 * 2³- X
Decimal result = T3 * 2¹

■ A Texas Instruments application note discussing Horner’s method is available at http://focus.ti.com/mcu/docs/mcusupport techdocsc.tsp?sectionId= 96&tabId=1502&abstractName=slaa329.

T1= X*2^-4+X
T2 = T1 * 2^-3+ X
T3 = T2 * 2^-2+ X
Fraction result = T3 * 2^-2

■ For information on computer arithmetic and algorithms see the book Computer Organization by Carl Hamacher, Zvonko Vranesic and Safawat Zaky, 3rd edition, McGraw-Hill Publications, 1990.

Total Result = Decimal result + Fraction
result

You can see there is one less equation as a result of the CSD optimization.

equation with its rotate and add. Therein lies the optimization.

Generating the Horner equations for a CSD optimized multiplier is the same as was described previously, except instead of adding + X to each equation, a – X is added for each -1 in the representation.

Here are the CSD optimized Horner equations for our previous example of 654.321:

Horner.java

As mentioned, Horner.java is a program I wrote to quickly generate Horner equations and executable code for performing floating point multiplication and/or division on the MSP430 family of microcontrollers. Check out the sidebar that shows how to run this program and what program options are available. The source code for

Horner.java can be extracted from the included jar file listed in the sidebar. You may like to look at the code to see how signed multiplications are performed.

Conclusions

Horner’s method can be used to provide floating point support on microprocessors or microcontrollers that don’t have support built in. It is ideal for applications like mine, that aren’t written using a high level language. Horner’s method was just what I needed for my color organ application. After developing the digital filters using Horner’s method, I can say that the code for the color organ project can fit in the 2K bytes of Flash memory provided by the F2012 microcontroller (though just barely).

It may seem like a lot of work to use the techniques presented here, but often optimizing performance and/or memory usage of an application usually is work. NV