Hacktoberfest 2026: los issues que los mantenedores marcaron para octubre, abiertos y aptos para principiantes. Explorar issues de Hacktoberfest

trig recurrence accuracy (and speed) vs. precomputed table

Abierto
  • ¿Algo no está bien?
#55 0 comentarios 1 reacción 0 asignados Ver en GitHub

Nadie ha tomado este issue todavía.

Evaluación

Dificultad
5/5
Tiempo estimado
Más de una semana
Aptitud para principiantes
35/100
Tipo de issue
Nueva funcionalidad
Claridad
Bastante claro
Estado de actividad
Estancado
Stack tecnológico
julia
Área
performance

Línea de trabajo

Localiza la recurrencia trigonométrica y la implementación del plan de FFT, y compáralas con el ejemplo directo de trigtable2 basado en cispi del issue. Determina dónde podría conservarse una tabla precalculada para FFTs repetidas y mide la precisión y el rendimiento de la reutilización frente a la recurrencia actual antes de definir el comportamiento final.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

Note that your trigonometric recurrence has $O(\sqrt{n})$ root-mean-square error growth, which is much worse than the $O(\sqrt{\log n})$ mean error growth of the Cooley–Tukey algorithm (see e.g. the references here).

In particular, if I pull out your trig recurrence code and compare it to a function that simply calls cispi to compute $e^{-2\pi k /n}$ for $k = 0,\ldots,n-1$, the code (for BigFloat) looks like:

function trigtable(n)
    n *= 2
    θ=big"-2"/n
    wtemp = sinpi(θ/2)
    wpr, wpi = -2wtemp^2, sinpi(θ)
    wr, wi = one(BigFloat), zero(BigFloat)
    w = [complex(wr, wi)]
    for m=1:2:n-2
        wr = (wtemp=wr)*wpr-wi*wpi+wr
        wi = wi*wpr+wtemp*wpi+wi
        push!(w, complex(wr, wi))
    end
    return w
end

# a more accurate alternative:
trigtable2(n) = cispi.(.- (0:n-1) ./ BigInt(n)) # simple direct-call algorithm

For the default 256-bit BigFloat precision ($\varepsilon \approx 10^{-77}$), one can see the $O(\sqrt{n})$ error growth in the relative $L_2$ error $\Vert x - y \Vert_2 / \Vert y \Vert_2$ between these two methods:

Image

The easiest accurate alternative is to use a precomputed trig table such as that returned by trigtable2(n), which could be stored in a "plan" object for efficient repeated FFTs.

Maybe it's not such a big concern if the precision is large and $n$ is small, but it might be nice to have the option for a more accurate result. Also, precomputing the trig table might be faster if you re-use it for a lot of FFTs.

Lenguaje dominante
Julia
Estrellas
16
Forks
6
Sin PR fusionados en 30 d

Preparar el entorno

Este proyecto no incluye contenedor de desarrollo, Dockerfile ni guía de contribución, así que la configuración corre por tu cuenta: empieza por su README y consulta nuestra guía para la primera contribución para los pasos generales.

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de JuliaApproximation/GenericFFT.jl

Todos los issues de JuliaApproximation/GenericFFT.jl

Issues similares

Más issues de Julia

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.