search

ejmahler / RustFFT

RustFFT is a high-performance FFT library written in pure Rust.
Apache License 2.0
678 stars 47 forks source link

use FloatConst/Float and from_usize to reduce conversion loss #63

Closed roosephu closed 3 years ago

roosephu commented 3 years ago

This is a follow-up to #62.

I'm not familiar with the codebase so I only tried to find as f64 or T::from_f64 and modify them accordingly. It's very possible that I missed something.

I also ran cargo test and it seems to be fine.

HEnquist commented 3 years ago

I would propose to use 2*pi instead of Tau. Tau isn't a very well known constant so it can be a little confusing. For me, and probably a lot of other people, it's a time constant.

ejmahler commented 3 years ago

Actually - as I think about this more, I would like to approach this in a different way. I'd like f32 to continue using f64 for butterflies, because it improves the precision of f32. The changes in this PR would reduce the precision for f32, which I want to avoid unless we have no other choice.

I can easily think of a solution that involves specialization - @roosephu do you run on nightly or on stable? If you were willing to run on nightly, we could devise a solution where RustFFT compiles on stable, and then you provide a specialization that computes the twiddles with higher precision.

roosephu commented 3 years ago

I can use the nightly version, as it's a personal projection so I can whatever feature I want. I do believe specialization is the future but it seems there's a long haul for it to be stabilized, given its current status -- but I'm not opposing specialization.

ejmahler commented 3 years ago

ok! in that case, what I'm thinking of doing is making the twiddle factor function a provided method on the FftNum trait. That would compile fine on stable, and you could specialize it to use a more-accurate computation on your own type.

The compiler might give you trouble about orphan rules, but you can get around that with a newtype.

As for floatindex, what I might do instead is "bigindex", where the index is a u128 instead of a u64 or f64. The only reason floatindex exists is because bluestein's algorithm uses i^2 instead of just i for its twiddle factor indexes, so we need something that can store numbers larger than u64 max. u128 will do fine for that.

ejmahler commented 3 years ago

I'm sorry to say that after looking into this, I don't think RustFFT can support this until Rust supports specialization on stable.

I implemented the two fixes to precision problems in rader's algorithm and bluestein's algorithm, but we're fundamentally stuck with f64 precision for twiddles. We can't add trait bounds to FftNum, and specialization will require specialization-aware changes to the definition of FftNum, neither of which are on the table.

I'm closing this for now, but if you have any bursts of inspiration on how to solve this problem, please bring it up.

HEnquist commented 3 years ago

So now we calculate all twiddles in f64 and then convert to T. One way could be to calculate the twiddles with a higher precision type than f64, for example f128. I don't find any good candidate library for doing it today, but this one could maybe become one: https://github.com/Barandis/qd