Indeed, Horners method is for a constant multiplier, as needed for some algorithms. (e.g. fixed scaling of gazillions of values). It is not suitable if both parameters change.
The standard multiplication of the C compiler has some limitations. First, it does at least 16 bit multiplication even if the arguments are 8 bit or mixed, and then it uses always same arguments and result size. So to get a 32 bit result, you'll need to expand the arguments (possibly 8 and 16 bit) to 32 bit and do a 32x32 bit multiplication, even if only a 16x16 multiplication is needed. A formula like "int32 = int16*int16" gives only a 16 bit result. You'll need to cast one of the int16 to int32 if you want a 32 bit result and then the second parameter is also turned in an int32 implicitely and an (unnecessary) 32x32 bit multiplication is done. Even with the hardware multiplier this is inefficient, as the hardware multiplier already gives a 32 bit result from a 16x16 multiplication. I wrote a set of multiplication macros (using inline assembly) which gives a 16 bit result from 8x8 multiplication and so on (using the 32 bit hardware multiplier). It is MUCH faster than using the normal * operator and does not need typecasting of the parameters to avoid result truncation. The combination of method (so result does not need to be the same size as the arguments) and macro (inlined and optimizable) together with the hinting you can usie in GCCs inline assembly, results in very fast code. I think I published the file some time ago here in the list. But maybe not the latest version. JMGross ----- Ursprüngliche Nachricht ----- Von: William "Chops"Westfield An: GCC for MSP430 - http://mspgcc.sf.net Gesendet am: 03 Sep 2010 09:28:43 Betreff: Re: [Mspgcc-users] Multiplication using Horner's method On Sep 2, 2010, at 12:35 PM, Andres Vahter wrote: > I would like to use Horner's method for fast multiplication on > MSP430f2234. > I found source files from: > http://focus.ti.com/general/docs/litabsmultiplefilelist.tsp?literatureNumber=slaa329 You need to read the app note associated with that code, which is here: http://focus.ti.com/lit/an/slaa329/slaa329.pdf It says, among other things: "The memory requirement is much higher for Horner's method since, for each multiplier or divisor, the code is different. In cases where speed is of prime concern, this is not a serious limitation." That is, the multiplication algorithm they talk about (and the performance improvement they get) is only suitable for a constant multiplier. If you need multiplication faster than that provided by the C compiler, you probably have to give up some that the C compiler assumes. It's not like the C compiler writers sit around going "Well, we're a HLL, so we can make our multiply function needlessly complex!" One possibility is a mixed-size multiplication. C (probably) assumes a 16x16bit multiply, and if you KNOW your arguments are always going to be less than 16 bits, you can write a significantly faster multiply function. BillW ------------------------------------------------------------------------------ This SF.net Dev2Dev email is sponsored by: Show off your parallel programming skills. Enter the Intel(R) Threading Challenge 2010. http://p.sf.net/sfu/intel-thread-sfd _______________________________________________ Mspgcc-users mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/mspgcc-users
