Speex dev - Nov 2005 - cheb_poly_eva using Clenshaw's recurrence formula

Hi,

After reading the paper entitled "The Computation of Line Spectral
Frequencies Using Chebyshev Polynomials", P. Kabal and R.
Ramachandran, IEEE Trans. on ASSP, Vol. 34, No. 6, December 1986, I
rewrite the function cheb_poly_eva in lsp.c using the Clenshaw's
recurrence formula, as described, for example, in Numerical Recipes in
C, Second Edition (5.5 and 5.8) :

static float cheb_poly_eva(spx_word32_t *coef, float x, int m, char *stack)
{
 int k;
 float b0, b1, tmp;
 int m2=m>>1;

 /* Initial conditions */
 b0=0; /* b_(m+1) */
 b1=0; /* b_(m+2) */

 x*=2;

 /* Calculate the b_(k) */
 for(k=m2;k>0;k--)
 {
    tmp=b0;                           /* tmp holds the previous value of b0 */
    b0=x*b0-b1+coef[m2-k];    /* b0 holds its new value based on b0 and b1 */
    b1=tmp;                           /* b1 holds the previous value of b0 */
 }

return(-b1+x/2*b0+coef[m2]);
}

I don't really know if it's a little improvement or not, so I'd like
to have feedback from the Speex experts here.

Thanks a lot for releasing Speex, it helps me a lot to understand
speech coding !

Matthieu Poullet

Hello,

Matthieu Poullet schrieb:
> static float cheb_poly_eva(spx_word32_t *coef, float x, int m, char *stack)
> {
>  int k;
>  float b0, b1, tmp;
>  int m2=m>>1;
> 
>  /* Initial conditions */
>  b0=0; /* b_(m+1) */
>  b1=0; /* b_(m+2) */
> 
>  x*=2;
> 
>  /* Calculate the b_(k) */
>  for(k=m2;k>0;k--)
>  {
>     tmp=b0;                           /* tmp holds the previous value of b0
*/
>     b0=x*b0-b1+coef[m2-k];    /* b0 holds its new value based on b0 and b1
*/
>     b1=tmp;                           /* b1 holds the previous value of b0
*/
>  }
> 
> return(-b1+x/2*b0+coef[m2]);
> }
> 
> I don't really know if it's a little improvement or not, so I'd
like
> to have feedback from the Speex experts here.
I'm far from beeing an expert in anything, but I've recently had a
look at the function as it is used in speex-1.1.10.
Both implementations do some assignments and then go m/2 times
through a loop.
The current implementation does in this loop two multiplications and
two additions. The function described above only uses two simple
assignments and 1 multiplication and one addition.
Seems like less operations to me. As I'm sure the return values are
the same (which should be tested before any refactoring), I suppose
the suggestion is more effective.
Maybe a new implementation should use the algorithm above plus the
explicit ALLOC which is used all over speex (why actually?).

Ciao,

Bj?rn


-- 
Q:	Are we not men?
A:	We are Vaxen.

-- 
Important! Please recognize my new GPG Public Key!
                 Bj?rn Thalheim
gpg fingerprint: 0A29 87E7 B4BE 8EFC 1063  EF09 9096 FA4B DF0C 6701
   download key: wget http://www.ifsr.de/~bjoern/gpg/public_key.asc
       See also: http://www.ifsr.de/~bjoern/gpg/key.html

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 251 bytes
Desc: OpenPGP digital signature
Url :
http://lists.xiph.org/pipermail/speex-dev/attachments/20051129/f3e4d928/signature.pgp

> > I don't really know if it's a little improvement or not, so
I'd like
> > to have feedback from the Speex experts here.
I'd have to test, but it looks right. I don't expect much improvement,
but it makes the code simpler, especially for memory. Would also have to
test on fixed-point and see if it works.
> Maybe a new implementation should use the algorithm above plus the
> explicit ALLOC which is used all over speex (why actually?).
Actually, there would be no need for the ALLOC, which is a good thing.
I'm using ALLOC only for dynamic allocation of temporary variables
(stack) and because not all compilers support C99 arrays.

	Jean-Marc