Re: [eigen] uniform spaced cpx sinusoid via rootfinding, was Re: FFT module thoughts

[Pavel Holoborodko <pavel@xxxxxxxxxxxxxxx>]

Mark, thank you for explaining your ideas. I think it might be a great way to avoid exp() computing (prone to cancellation errors).

Need to study this further, thank you for the Matlab script!

On Fri, Apr 6, 2012 at 12:55 AM, Mark Borgerding <mark@xxxxxxxxxxxxxx> wrote:

To create a root-finder, I'd probably start by trying to use http://en.wikipedia.org/wiki/Newton%27s_method.  There might be a more suitable algorithm for finding complex roots of unity.

One could use this root-finder to create an entire cycle via the algorithm in the attached octave/matlab script.
The idea is similar to http://en.wikipedia.org/wiki/CORDIC

The only reason I can think of not to do this for the general case is fear of worst-case numerical performance (e.g. n is a large prime).  One thought: This  might be mitigated by comparing the complex sinusoid with its time-reversed and conjugated self.


On 04/05/2012 11:02 AM, Pavel Holoborodko wrote:

Hi Mark.

[...]

I would really appreciate if you would provide some links on how to re-write make_twiddles using root finding approach.