Re: [music-dsp] Anyone using Chebyshev polynomials to approximate trigonometric functions in FPGA DSP

[robert bristow-johnson]

�
i thought i understood Tchebyshev polynomials well. �including their trig 
definitions (for |x|<1), but if what you're trying to do is generate a sinusoid 
from polynomials, i don't understand where the "Tchebyshev" (with or without 
the "T") comes
in.
is it min/max error (a.k.a. Tchebyshev norm)?
�
if you want a quick 'n clean polynomial for sin(x), there is a very low-order 
optimized polynomial implementation for |x|http://dsp.stackexchange.com/questions/20444/books-resources-for-implementing-various-mathematical-functions-in-fixed-point-a/20482#20482
 .
�
is the purpose to generate a sinusoidal waveform or perhaps to do math with 
(like in the generation of filter
coefficients)?
�
--

r b-j � � � � � � � � � r...@audioimagination.com


"Imagination is more important than knowledge."




 Original Message ------------

Subject: Re: [music-dsp] Anyone using Chebyshev polynomials to approximate 
trigonometric functions in FPGA DSP

From: "Bogac Topaktas" <bo...@bteaudio.com>

Date: Wed, January 20, 2016 6:12 pm

To: music-dsp@music.columbia.edu

--



> Jack Crenshaw's book "Math Toolkit for Real-Time Programming"

> contains all the information you need: "Chapter 5 - Getting the

> Sines Right" provides theory and practice of approximating

> sines & cosines with various methods including Chebyshev polynomials.

>

> Another good resources is Jean-Michel Muller's book

> "Elementary Functions: Algorithms and Implementation".

>

�
___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

Re: [music-dsp] Anyone using Chebyshev polynomials to approximate trigonometric functions in FPGA DSP

[Ross Bencina]

On 21/01/2016 2:36 PM, robert bristow-johnson wrote:
> i thought i understood Tchebyshev polynomials well.  including their
> trig definitions (for |x|<1), but if what you're trying to do is
> generate a sinusoid from polynomials, i don't understand where the
> "Tchebyshev" (with or without the "T") comes in.
>
> is it min/max error (a.k.a. Tchebyshev norm)?

Here's the relevant passage from p. 119:

"""
An article about sines and cosines wouldn’t be complete without some 
mention of the use of Chebyshev polynomials. Basically, the theory of 
Chebyshev polynomials allows the programmer to tweak the coefficients a 
bit for a lower error bound overall. When I truncate a polynomial, I 
typically get very small errors when x is small, and the errors increase 
dramatically and exponentially outside a certain range near x = 0. The 
Chebyshev polynomials, on the other hand, oscillate about zero with peak 
deviations that are bounded and equal. Expressing the power series in 
terms of Chebyshev polynomials allows you to trade off the small errors 
near zero for far less error near the extremes of the argument range. I 
will not present a treatise on Chebyshev polynomials here; for now, I’ll 
only give the results of the process.


You don’t need to know how this is done for the purposes of this 
discussion, but the general idea is to substitute every power of x by 
its equivalent in terms of Chebyshev polynomials, collect the terms, 
truncate the series in that form, and substitute back again. When all 
the terms have been collected, you’ll find that you are back to a power 
series in x again, but the coefficients have been slightly altered in an 
optimal way. Because this process results in a lower maximum error, 
you’ll normally find you can drop one term or so in the series expansion 
while still retaining the same accuracy

"""

R.



if you want a quick 'n clean polynomial for sin(x), there is a very
low-order optimized polynomial implementation for |x|http://dsp.stackexchange.com/questions/20444/books-resources-for-implementing-various-mathematical-functions-in-fixed-point-a/20482#20482
.

is the purpose to generate a sinusoidal waveform or perhaps to do math
with (like in the generation of filter coefficients)?

___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

Re: [music-dsp] Anyone using Chebyshev polynomials to approximate trigonometric functions in FPGA DSP

[robert bristow-johnson]

 Original Message 

Subject: Re: [music-dsp] Anyone using Chebyshev polynomials to approximate 
trigonometric functions in FPGA DSP

From: "Ross Bencina" <rossb-li...@audiomulch.com>

Date: Wed, January 20, 2016 11:00 pm

To: "A discussion list for music-related DSP" <music-dsp@music.columbia.edu>

--



> On 21/01/2016 2:36 PM, robert bristow-johnson wrote:

> > i thought i understood Tchebyshev polynomials well. including their

> > trig definitions (for |x|<1), but if what you're trying to do is

> > generate a sinusoid from polynomials, i don't understand where the

> > "Tchebyshev" (with or without the "T") comes in.

> >

> > is it min/max error (a.k.a. Tchebyshev norm)?

>

> Here's the relevant passage from p. 119:

>

> An article about sines and cosines wouldnt be complete without some

> mention of the use of Chebyshev polynomials. Basically, the theory of

> Chebyshev polynomials allows the programmer to tweak the coefficients a

> bit for a lower error bound overall. When I truncate a polynomial, I

> typically get very small errors when x is small, and the errors increase

> dramatically and exponentially outside a certain range near x = 0. The

> Chebyshev polynomials, on the other hand, oscillate about zero with peak

> deviations that are bounded and equal. Expressing the power series in

> terms of Chebyshev polynomials allows you to trade off the small errors

> near zero for far less error near the extremes of the argument range.
okay, i guess. �i'll have to do a bit more internet research, because stated as 
such, this isn't exactly in my "Approximation Theory" book (Cheney). �the 
"Tchebyshev norm" for error is
mentioned. �but the technique is the "Remes" (with an "s") algorithm.
�
so, the fundamental thing that i don't understand, is that given the same order 
N for the polynomials, whether your basis set are the Tchebyshevs, T_n(x), or 
the basis is just set of
x^n, if you come up with a min/max optimal fit to your data, how can the two 
polynomials be different? �i know that Parks-McClellan use the Tchebyshevs to 
convert an optimized polynomial to a sum of cosines (of which a symmetrical FIR 
filter comes forth), but i am curious how the technique that
Jack shows you gets a different answer than the Remes alg, after the sum of 
Tchebyshevs is expanded and converted to a sum of x^n.



--
�
r b-j � � � � � � � � � r...@audioimagination.com
�


"Imagination is more important than knowledge."
�
___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

Re: [music-dsp] Anyone using Chebyshev polynomials to approximate trigonometric functions in FPGA DSP

[Ethan Duni]

>given the same order N for the polynomials, whether your basis set are
> the Tchebyshevs, T_n(x), or the basis is just set of x^n, if you come up
>with a min/max optimal fit to your data, how can the two polynomials be
>different?

Right, if you do that you'll end up with equivalent answers (to within
numerical precision).

The idea is that you avoid the cost of doing the iterative algorithm to get
the optimal polynomial, and instead you simply truncate the Chebyshev
expansion to the desired order to get an approximation. For well-behaved
target functions it should be quite close. The justification is that the
Chebyshev polynomials each look like solutions to the minimax problem (they
oscillate between +-1 and the Nth polynomial has N+1 extrema), and the
error from truncating a series is approximately proportional to the last
retained term, so truncating a Chebyshev expansion should resemble the
optimal polynomial.

E

On Wed, Jan 20, 2016 at 10:32 PM, robert bristow-johnson <
r...@audioimagination.com> wrote:

>
>
>  Original Message --------
> Subject: Re: [music-dsp] Anyone using Chebyshev polynomials to approximate
> trigonometric functions in FPGA DSP
> From: "Ross Bencina" <rossb-li...@audiomulch.com>
> Date: Wed, January 20, 2016 11:00 pm
> To: "A discussion list for music-related DSP" <
> music-dsp@music.columbia.edu>
> --
>
> > On 21/01/2016 2:36 PM, robert bristow-johnson wrote:
> > > i thought i understood Tchebyshev polynomials well. including their
> > > trig definitions (for |x|<1), but if what you're trying to do is
> > > generate a sinusoid from polynomials, i don't understand where the
> > > "Tchebyshev" (with or without the "T") comes in.
> > >
> > > is it min/max error (a.k.a. Tchebyshev norm)?
> >
> > Here's the relevant passage from p. 119:
> >
> > An article about sines and cosines wouldn’t be complete without some
> > mention of the use of Chebyshev polynomials. Basically, the theory of
> > Chebyshev polynomials allows the programmer to tweak the coefficients a
> > bit for a lower error bound overall. When I truncate a polynomial, I
> > typically get very small errors when x is small, and the errors increase
> > dramatically and exponentially outside a certain range near x = 0. The
> > Chebyshev polynomials, on the other hand, oscillate about zero with peak
> > deviations that are bounded and equal. Expressing the power series in
> > terms of Chebyshev polynomials allows you to trade off the small errors
> > near zero for far less error near the extremes of the argument range.
>
> okay, i guess.  i'll have to do a bit more internet research, because
> stated as such, this isn't exactly in my "Approximation Theory" book
> (Cheney).  the "Tchebyshev norm" for error is mentioned.  but the technique
> is the "Remes" (with an "s") algorithm.
>
>
>
> so, the fundamental thing that i don't understand, is that given the same
> order N for the polynomials, whether your basis set are the Tchebyshevs,
> T_n(x), or the basis is just set of x^n, if you come up with a min/max
> optimal fit to your data, how can the two polynomials be different?  i know
> that Parks-McClellan use the Tchebyshevs to convert an optimized polynomial
> to a sum of cosines (of which a symmetrical FIR filter comes forth), but i
> am curious how the technique that Jack shows you gets a different answer
> than the Remes alg, after the sum of Tchebyshevs is expanded and converted
> to a sum of x^n.
>
>
>
> --
>
>
>
> r b-j   r...@audioimagination.com
>
>
>
>
> "Imagination is more important than knowledge."
>
>
>
> ___
> dupswapdrop: music-dsp mailing list
> music-dsp@music.columbia.edu
> https://lists.columbia.edu/mailman/listinfo/music-dsp
>
___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

Re: [music-dsp] Anyone using Chebyshev polynomials to approximate trigonometric functions in FPGA DSP

[robert bristow-johnson]

 Original Message 

Subject: Re: [music-dsp] Anyone using Chebyshev polynomials to approximate 
trigonometric functions in FPGA DSP

From: "Ethan Duni" <ethan.d...@gmail.com>

Date: Thu, January 21, 2016 2:34 am

To: "A discussion list for music-related DSP" <music-dsp@music.columbia.edu>

--



>>given the same order N for the polynomials, whether your basis set are

>> the Tchebyshevs, T_n(x), or the basis is just set of x^n, if you come up

>>with a min/max optimal fit to your data, how can the two polynomials be

>>different?

>

> Right, if you do that you'll end up with equivalent answers (to within

> numerical precision).

>

> The idea is that you avoid the cost of doing the iterative algorithm to get

> the optimal polynomial, and instead you simply truncate the Chebyshev

> expansion to the desired order to get an approximation. For well-behaved

> target functions it should be quite close. The justification is that the

> Chebyshev polynomials each look like solutions to the minimax problem (they

> oscillate between +-1 and the Nth polynomial has N+1 extrema), and the

> error from truncating a series is approximately proportional to the last

> retained term, so truncating a Chebyshev expansion should resemble the

> optimal polynomial.
got it. �thanks for the explanation, Ethan.



--
�
r b-j � � � � � � � � � r...@audioimagination.com
�


"Imagination is more important than knowledge."
___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

Re: [music-dsp] Anyone using Chebyshev polynomials to approximate trigonometric functions in FPGA DSP

[Bogac Topaktas]

Jack Crenshaw's book "Math Toolkit for Real-Time Programming"
contains all the information you need: "Chapter 5 - Getting the
Sines Right" provides theory and practice of approximating
sines & cosines with various methods including Chebyshev polynomials.

Another good resources is Jean-Michel Muller's book
"Elementary Functions: Algorithms and Implementation".

On Tue, January 19, 2016 8:05 pm, Theo Verelst wrote:
> Hi all,
>
>
> Maybe a bit forward, but hey, there are PhDs here, too, so here it goes:
> I've played a
> little with the latest Vivado HLx design tools fro Xilinx FPGAs and the
> cheap Zynq implementation I use (a Parallella board), and I was looking
> for interesting examples to put in C-to_chip compiler that I can connected
> over AXI bus to a Linux program running on the ARM cores in the Zynq chip.
>
>
> In other words, computations and manipulations with additions, multiplies
> and other logical operations (say of 32 bits) that compile nicely to for
> instance the computation of y=sin(t) in such a form that the Silicon
> Compiler can have a go at it, and produce a nice
> relative low-latency FPGA block to connect up with other blocks to do nice
> (and very low
> latency) DSP with.
>
> Regards,
>
>
> Theo V.
> ___
> dupswapdrop: music-dsp mailing list
> music-dsp@music.columbia.edu
> https://lists.columbia.edu/mailman/listinfo/music-dsp
>
>
>


___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

Re: [music-dsp] Anyone using Chebyshev polynomials to approximate trigonometric functions in FPGA DSP

[Alan Wolfe]

Chebyshev is indeed a decent way to approximate trig from what I've read. (
http://www.embeddedrelated.com/showarticle/152.php)

Did you know that rational quadratic Bezier curves can exactly represent
conic sections, and thus give you exact trig values?  You essentially
divide one quadratic Bezier curve by another, with specifically calculated
weights.  Fairly simple and straightforward stuff.  Not sure if the
division is a problem for you mapping it to circuitry.
http://demofox.org/bezquadrational.html

Video cards use a handful of terms of taylor series, so that might be a
decent approach as well since it's used in high end production circuitry.


On Tue, Jan 19, 2016 at 10:05 AM, Theo Verelst  wrote:

> Hi all,
>
> Maybe a bit forward, but hey, there are PhDs here, too, so here it goes:
> I've played a little with the latest Vivado HLx design tools fro Xilinx
> FPGAs and the cheap Zynq implementation I use (a Parallella board), and I
> was looking for interesting examples to put in C-to_chip compiler that I
> can connected over AXI bus to a Linux program running on the ARM cores in
> the Zynq chip.
>
> In other words, computations and manipulations with additions, multiplies
> and other logical operations (say of 32 bits) that compile nicely to for
> instance the computation of y=sin(t) in such a form that the Silicon
> Compiler can have a go at it, and produce a nice relative low-latency FPGA
> block to connect up with other blocks to do nice (and very low latency) DSP
> with.
>
> Regards,
>
>  Theo V.
> ___
> dupswapdrop: music-dsp mailing list
> music-dsp@music.columbia.edu
> https://lists.columbia.edu/mailman/listinfo/music-dsp
>
>
___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

Re: [music-dsp] Anyone using Chebyshev polynomials to approximate trigonometric functions in FPGA DSP

[Bjorn Roche]

Years ago I attended a talk on Chebyshev polynomials and someone asked if
they could be used to approximate trig functions. My memory is hazy at
best, but here's what I recall: the answer was something like "you could,
but it would be very slow, so in practice I think that would be a bad
idea". Someone else said that the CORDIC algorithm is what's used in pocket
calculators for approximating trig functions. I remember hm going on to say
something like "Unfortunately, the CORDIC algorithm is mind-numbingly
boring and Chebychev polynomials are really interesting".

Well, to each his own. Perhaps you'll enjoy CORDIC:

https://en.wikipedia.org/wiki/CORDIC


On Tue, Jan 19, 2016 at 1:56 PM, Alan Wolfe  wrote:

> Chebyshev is indeed a decent way to approximate trig from what I've read. (
> http://www.embeddedrelated.com/showarticle/152.php)
>
> Did you know that rational quadratic Bezier curves can exactly represent
> conic sections, and thus give you exact trig values?  You essentially
> divide one quadratic Bezier curve by another, with specifically calculated
> weights.  Fairly simple and straightforward stuff.  Not sure if the
> division is a problem for you mapping it to circuitry.
> http://demofox.org/bezquadrational.html
>
> Video cards use a handful of terms of taylor series, so that might be a
> decent approach as well since it's used in high end production circuitry.
>
>
> On Tue, Jan 19, 2016 at 10:05 AM, Theo Verelst 
> wrote:
>
>> Hi all,
>>
>> Maybe a bit forward, but hey, there are PhDs here, too, so here it goes:
>> I've played a little with the latest Vivado HLx design tools fro Xilinx
>> FPGAs and the cheap Zynq implementation I use (a Parallella board), and I
>> was looking for interesting examples to put in C-to_chip compiler that I
>> can connected over AXI bus to a Linux program running on the ARM cores in
>> the Zynq chip.
>>
>> In other words, computations and manipulations with additions, multiplies
>> and other logical operations (say of 32 bits) that compile nicely to for
>> instance the computation of y=sin(t) in such a form that the Silicon
>> Compiler can have a go at it, and produce a nice relative low-latency FPGA
>> block to connect up with other blocks to do nice (and very low latency) DSP
>> with.
>>
>> Regards,
>>
>>  Theo V.
>> ___
>> dupswapdrop: music-dsp mailing list
>> music-dsp@music.columbia.edu
>> https://lists.columbia.edu/mailman/listinfo/music-dsp
>>
>>
>
> ___
> dupswapdrop: music-dsp mailing list
> music-dsp@music.columbia.edu
> https://lists.columbia.edu/mailman/listinfo/music-dsp
>



-- 
Bjorn Roche
@shimmeoapp
___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

[music-dsp] Anyone using Chebyshev polynomials to approximate trigonometric functions in FPGA DSP

[Theo Verelst]

Hi all,

Maybe a bit forward, but hey, there are PhDs here, too, so here it goes: I've played a 
little with the latest Vivado HLx design tools fro Xilinx FPGAs and the cheap Zynq 
implementation I use (a Parallella board), and I was looking for interesting examples to 
put in C-to_chip compiler that I can connected over AXI bus to a Linux program running on 
the ARM cores in the Zynq chip.


In other words, computations and manipulations with additions, multiplies and other 
logical operations (say of 32 bits) that compile nicely to for instance the computation of 
y=sin(t) in such a form that the Silicon Compiler can have a go at it, and produce a nice 
relative low-latency FPGA block to connect up with other blocks to do nice (and very low 
latency) DSP with.


Regards,

 Theo V.
___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

Re: [music-dsp] Anyone using Chebyshev polynomials to approximate trigonometric functions in FPGA DSP

[Ross Bencina]

Sorry, my previous message got truncated for some reason.

On 20/01/2016 5:56 AM, Alan Wolfe wrote:

Did you know that rational quadratic Bezier curves can exactly represent
conic sections, and thus give you exact trig values?


As Andrew said, the curve lies on a conic section, but the 
parameterization is not in terms of radian angle.


Taking equation 106 from here:

http://www.cl.cam.ac.uk/teaching/2000/AGraphHCI/SMEG/node5.html#SECTION00051000

You'll see that the graphs of P(t) and sin(pi*t/2) do not align:

https://www.desmos.com/calculator/qn7yn1jxcp

Cheers,

Ross.
___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp