feat: add initial implementation of `fft/base/fftpack`

[gunjjoshi]

Progresses #3131

Description

What is the purpose of this pull request?

This pull request:

• adds fft/base/fftpack.

• adds the following packages:

  • [ ] cfftb
  • [ ] cfftf
  • [ ] cffti
  • [ ] cosqb
  • [ ] cosqf
  • [ ] cosqi
  • [ ] cost
  • [ ] costi
  • [x] decompose
  • [ ] rfftb
  • [ ] rfftf
  • [x] rffti
  • [ ] sinqb
  • [ ] sinqf
  • [ ] sinqi
  • [ ] sint
  • [ ] sinti

Related Issues

Does this pull request have any related issues?

This pull request:

• progresses #3131.

Questions

Any questions for reviewers of this pull request?

No.

Other

Any other information relevant to this pull request? This may include screenshots, references, and/or implementation notes.

No.

Checklist

Please ensure the following tasks are completed before submitting this pull request.

• [x] Read, understood, and followed the contributing guidelines.

---

@stdlib-js/reviewers

[gunjjoshi]

/stdlib update-copyright-years

[gunjjoshi]

I had a confusion here. If we see the reference implementations of cosqf and cosqf1, cosqf calls cosqf1 here, and passes pointers to the wsave arrays, as cosqf1 accepts pointers to that array. But in the current JS implementation in this PR, I am passing a single element of the array here, while cosqf1 takes an entire array as an argument here. This might not be the right approach. Is there any other way to achieve the same behavior as shown in the reference C implementation?

[gunjjoshi]

Should I follow something like what we are doing in the C and JS implementations of modf?

[kgryte]

@gunjjoshi It's a little hard to follow what you are asking given the various links. Can you provide relevant snippets in a single comment so we can see what you are referencing in one view?

[gunjjoshi]

@kgryte Ahh, sorry for the confusion.

This is the cosqf1 function:

static void cosqf1(integer n, real *x, real *w, real *xh)

This cosqf1 is used within the cosqf function as:

cosqf1(n, &x[1], &wsave[1], &wsave[n + 1]);

In order to replicate this same behavior in JS, currently, what I'm doing is:

cosqf1:

function cosqf1( n, x, w, xh )

where n is a number, while x, w and xh are Float64Arrays.

And, while calling this cosqf1 from cosqf, we are currently using it as:

cosqf1( n, x[ 1 - 1 ], wsave[ 1 - 1 ], wsave[ n + 1 - 1 ] );

But in this JS version, instead of passing arrays, I am currently passing single elements, such as wsave[ n + 1 - 1 ]. This seems to be wrong. Is there any other way of passing arrays here, but from a specific index (something like a subarray)?

I think this problem might be summed up as, how should we replicate the logic of passing subarrays (using pointers) in C, for the JS implementation?

[kgryte]

@gunjjoshi What about providing an array and then offsets, similar in concept to the ndarray APIs we have. E.g.,

xptr = ...;
wptr = ...;
xhptr = ...;

cosqf1(n, x, xptr, wsave, wptr, xhptr ); // =>cosqf1( n: number, x: Float64Array, xptr: number, wsave: Float64Array, wptr: number, xhptr: number )

where the *ptr variables are indices into the respective arrays.

Another alternative is that you pass down slices which has more overhead due to object creation.

cosqf1( n, x.slice( 1 ), wsave.slice( 1 ), wsave.slice( n+1 ) )

[gunjjoshi]

Thanks, @kgryte, I'll go with the first method!

[gunjjoshi]

The required functions are implemented now, will move on to testing the implementations locally, comparing with the reference ones and then creating the tests.

[kgryte]

The required functions are implemented now, will move on to testing the implementations locally, comparing with the reference ones and then creating the tests.

Great! Thanks for your continued work on this!

[gunjjoshi]

@kgryte For the tests, should we have the tests for all functions in a single test.js file, or should we keep them separate, such as test.rffti.js, test.cosqb.js, etc.? The functions that would be tested are mentioned here: https://github.com/marton78/pffft/blob/master/fftpack.c#L2710

[kgryte]

@gunjjoshi Let's try in separate files to start.

[stdlib-bot]

Coverage Report

Package	Statements	Branches	Functions	Lines
fft/base/fftpack	$\color{red}2793/3991$ $\color{green}+69.98\%$	$\color{red}42/68$ $\color{green}+61.76\%$	$\color{red}14/27$ $\color{green}+51.85\%$	$\color{red}2793/3991$ $\color{green}+69.98\%$

The above coverage report was generated for the changes in this PR.

[gunjjoshi]

The original C reference implementation here: https://github.com/marton78/pffft/blob/master/fftpack.c has a tolerance of 0.001. But currently, I'm getting it as follows:

      ✖ forward transform error: 0.4907203841224826 (expected <= 0.001)
      ✖ backward transform error: 40.50771641905412 (expected <= 0.001)
      ✖ forward-backward transform error: 34.05132902258452 (expected <= 0.001)

Seems like a major difference. I went through the whole implementation multiple times, still trying to figure out the problem. Especially, testing rffti, rfftf and rfftb implementations.

[gunjjoshi]

Here's what I've done so far:

• Implemented all the functions, as given in the reference C implementation: https://github.com/marton78/pffft/blob/master/fftpack.c
• Added tests for rffti, rfftf and rfftb, in test.rfft.js. I've implemented the same tests given in the reference implementation here: https://github.com/marton78/pffft/blob/master/fftpack.c#L2656
• Used offsets in JS to replicate the behavior of pointers in C.
• Some tests still fail, in test.rfft.js.

[kgryte]

/stdlib merge

[gunjjoshi]

/stdlib merge