feat: add fft/base/fftpack/sinqi#13000
Open
gunjjoshi wants to merge 1 commit into
Open
Conversation
---
type: pre_commit_static_analysis_report
description: Results of running static analysis checks when committing changes.
report:
- task: lint_filenames
status: passed
- task: lint_editorconfig
status: passed
- task: lint_markdown_pkg_readmes
status: passed
- task: lint_markdown_docs
status: na
- task: lint_markdown
status: na
- task: lint_package_json
status: passed
- task: lint_repl_help
status: passed
- task: lint_javascript_src
status: passed
- task: lint_javascript_cli
status: na
- task: lint_javascript_examples
status: passed
- task: lint_javascript_tests
status: passed
- task: lint_javascript_benchmarks
status: passed
- task: lint_python
status: na
- task: lint_r
status: na
- task: lint_c_src
status: na
- task: lint_c_examples
status: na
- task: lint_c_benchmarks
status: na
- task: lint_c_tests_fixtures
status: passed
- task: lint_shell
status: na
- task: lint_typescript_declarations
status: passed
- task: lint_typescript_tests
status: passed
- task: lint_license_headers
status: passed
---
gunjjoshi
commented
Jun 20, 2026
| * var bool = ( out === workspace ); | ||
| * // returns true | ||
| * | ||
| * var cosineTable = workspace.slice( 0, N ); |
Member
Author
There was a problem hiding this comment.
Intentionally used the name cosineTable here, same as the one used in fft/base/fftpack/cosqi, since this package simply calls cosqi internally, and initializes the array with cosine values, even for quarter-wave sine transform.
Ref: https://github.com/marton78/pffft/blob/master/src/fftpack.c#L2540
Member
Author
There was a problem hiding this comment.
This is the same reason for keeping most of the documentation in this package similar to that in cosqi, since we are calculating cosine values only.
Contributor
Coverage Report
The above coverage report was generated for the changes in this PR. |
gunjjoshi
commented
Jun 20, 2026
Comment on lines
+71
to
+128
| * ## Notes | ||
| * | ||
| * The workspace array is divided into four sections: | ||
| * | ||
| * ```text | ||
| * size = N N N 2+ceil(log2(N)/2) | ||
| * ↓ ↓ ↓ ↓ | ||
| * | cosine table | scratch/workspace | twiddle factors | radix factor table | | ||
| * ↑ ↑ ↑ ↑ | ||
| * i = 0 ... N ... 2N ... 3N ... | ||
| * ``` | ||
| * | ||
| * where | ||
| * | ||
| * - **cosine table**: a table of precomputed cosine coefficients used by quarter-wave sine transforms. | ||
| * - **scratch/workspace**: used as a scratch space when performing transforms. This section is not updated during initialization. | ||
| * - **twiddle factors**: a table of reusable complex-exponential constants stored as cosine/sine pairs. | ||
| * - **radix factor table**: a table containing the radix factorization of `N`. | ||
| * | ||
| * In general, a workspace array should have `3N + 34` indexed elements (as `log2(N)/2 ≤ 32` for all `2^64`). During initialization, only the sections for storing the cosine coefficients, twiddle factors, and the factorization of `N` are updated. | ||
| * | ||
| * > Note: FFTPACK only requires `3N+15`, but we increase that number here to accommodate larger workspace arrays, where `N` may exceed `2^30` indexed elements. | ||
| * | ||
| * The factorization section is comprised as follows: | ||
| * | ||
| * ```text | ||
| * | sequence_length | number_of_factors | integer_factors | | ||
| * ``` | ||
| * | ||
| * The sequence length and number of factors (`nf`) comprise a single element each. Only the first `nf` elements in the integer factors section are written to, with the rest being unused. | ||
| * | ||
| * As for twiddle factors, these are small, reusable complex-exponential constants that appear inside each "butterfly" stage of a Cooley–Tukey–style FFT. Every arithmetic step in an FFT multiplies one intermediate value by some | ||
| * | ||
| * ```tex | ||
| * W_N^k | ||
| * ``` | ||
| * | ||
| * where `W_N^k` is an N-th root of unity. Formally, in a forward FFT, | ||
| * | ||
| * ```tex | ||
| * W_N^k = e^{-2\pi ik/N} | ||
| * ``` | ||
| * | ||
| * In a backward FFT, | ||
| * | ||
| * ```tex | ||
| * W_N^k = e^{+2\pi ik/N} | ||
| * ``` | ||
| * | ||
| * As may be observed, `W_N^k` for forward and backward FFTs is the same, except the sign of the exponent is flipped. As a consequence, both forward and backward FFT callers can reuse the same set of twiddle factors, with those performing a forward transform (e.g., `cosqf`) multiplying with `(cos,-sin)` and those performing a backward transform (e.g., `cosqb`) multiplying with `(cos,+sin)`. | ||
| * | ||
| * Because these constants only depend on the transform length `N` (and **not** on the input data), we can pre-compute and store them once, then "twiddle" them (i.e., reuse them with different indices) as we proceed through the factorization. | ||
| * | ||
| * > As a quick aside regarding the name "twiddle", early FFT papers (notably Gentleman & Sande, 1966) described how you "twiddle" one branch of each butterfly by a complex rotation before adding/subtracting. The coefficients themselves inherited the nickname "twiddle factors," and the term stuck. | ||
| * | ||
| * By reusing the workspace array when computing multiple transforms of the same length `N`, every subsequent `*f` (forward) or `*b` (backward) call can simply look up the pre-stored twiddle factors instead of recomputing sine and cosine on-the-fly. | ||
| * | ||
| * In short, twiddle factors are cached roots of unity that allow each stage of the algorithm to rotate data quickly and predictably. |
Member
Author
There was a problem hiding this comment.
Even though this file doesn't include any implementation, still I have kept these notes from cosqi. We could exclude them here, but then I thought, that anyone using sinqi would still have to pass an array of size 3N+34, and it would be good to keep this, which explains how different parts of that array are used.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
2 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
type: pre_commit_static_analysis_report
description: Results of running static analysis checks when committing changes. report:
Resolves stdlib-js/metr-issue-tracker#868.
Description
This pull request:
fft/base/fftpack/sinqi, which is a part of fftpack.fft/base/fftpack#4121.Related Issues
This pull request has the following related issues:
fft/base/fftpack/sinqimetr-issue-tracker#868Questions
No.
Other
No.
Checklist
AI Assistance
If you answered "yes" above, how did you use AI assistance?
Disclosure
Used
Gemini-3.5-Flashfor reviewing the code.@stdlib-js/reviewers