[PD] efficient approximation of trig functions for hi pass formula (was: could vanilla borrow iemlib's hi pass filter recipe?)

[Jonathan Wilkes]

When implemented in C, which approach takes the least amount of time 
to read, reason about, and fully comprehend?

-Jonathan




      From: katja <katjavetter at gmail.com>
 To: "pd-list at lists.iem.at" <pd-list at lists.iem.at> 
 Sent: Wednesday, October 19, 2016 9:06 AM
 Subject: [PD] efficient approximation of trig functions for hi pass formula (was: could vanilla borrow iemlib's hi pass filter recipe?)
   
Changing the thread title to reflect the new approach. Extract of the
original thread;

- I suggested using iemlib's hi pass filter recipe to improve
frequency response of [hip~]
- Christof Ressi pointed to formula in
http://www.arpchord.com/pdf/coeffs_first_order_filters_0p1.pdf
- this formula calculates feedback coefficient k = (1 - sin(a)) /
cos(a) where a = 2 * pi * fc / SR
- the filter implementation is y[n] = (x[n] - x[n-1]) * (1 + k) / 2
+  k * y[n-1]
- following convention in d_filter.c (and pd tilde classes in
general), trig functions should best be approximated
- Cyrille provided libre office linear regression result for (1-sin(x))/cos(x)

Thanks for the useful infos and discussion. My 'math coach' suggested
using odd powers of -(x-pi/2) in an approximation polynomial for
(1-sin(x))/cos(x). The best accuracy/performance balance I could get
is with this 5th degree polynomial:

(-(x-pi/2))*0.4908 - (x-pi/2)^3*0.04575 - (x-pi/2)^5*0.00541

Using this approximation in the filter formula, response at cutoff
frequency is -3 dB with +/-0.06 dB accuracy in the required range 0 <
x < pi. It can be efficiently implemented in C, analogous to an
approximation Miller uses in [bp~]. So that is what I'll try next.

Attached patch hip~-models.pd illustrates and compares filter recipes
using vanilla objects:

- current implementation, most efficient, accuracy +/- 3 dB
- implementation with trig functions, least efficient, accuracy +/- 0.01 dB
- implementation with approximation for trig functions, efficient,
accuracy +/- 0.06 dB

A note on efficiency: coefficients in [hip~] are only recalculated
when cutoff frequency is changed. How important is performance for a
function rarely called? I'm much aware of the motto 'never optimize
early', yet I spent much time on finding a fast approximation, for
several reasons: it's a nice math challenge, instructive for cases
where performance matters more, and I want to respect Miller's code
efficiency when proposing a change. Today pd is even deployed on
embedded devices so the frugal coding approach is still relevant.
After 20 years.

Katja


On Tue, Oct 18, 2016 at 10:28 AM, cyrille henry <ch at chnry.net> wrote:
>
>
> Le 18/10/2016 à 00:47, katja a écrit :
>>
>> The filter recipe that Christof pointed to was easy to plug into the C
>> code of [hip~] and works perfectly. But when looking further in
>> d_filter.c I came across an approximation function 'sigbp_qcos()' used
>> in the bandpass filter. It made me realize once more how passionate
>> Miller is about efficiency. I'm not going to make a fool of myself by
>> submitting a 'fix' using two trig functions to calculate a filter
>> coefficient when a simple approximation could do the job. So that is
>> what I'm now looking into, with help of a math friend: an efficient
>> polynomial approximation for (1-sin(x))/cos(x).
>
> according to libre office linear regression, for x between 0 and Pi,
> (1-sin(x))/cos(x) is about :
> -0.057255x³ + 0.27018x² - 0.9157x + 0.99344
>
> the calc is in attachment, if you want to tune the input source or
> precision.
> cheers
> c
_______________________________________________
Pd-list at lists.iem.at mailing list
UNSUBSCRIBE and account-management -> https://lists.puredata.info/listinfo/pd-list


   
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puredata.info/pipermail/pd-list/attachments/20161019/50ffd7e6/attachment-0001.html>