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*22+X
T2 = T1 * 23+ X
T3 = T2 * 23- X
Decimal result = T3 * 21
■ 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
Contact the Author
Craig Lindley can be contacted via
email at calhjh@gmail.com.
64
September 2007