Hi!
First of all, thank you for your fast library for FT.

I tried to split the range of frequencies and perform an inverse FT.
In detail, my EEG data is sampled at 200Hz per second.
Here are the steps I followed:

1. Convert from time domain to frequency domain using STFT
2. split the frequencies into three ranges: 14Khz, 416Khz, 16~64Khz
3. Perform an Inverse FT

As far as I know, a spectrogram is Frequency + Amplitude(or can be Magnitude) + Time.
When I ran the Spectrogram example, I couldn't understand the result:

        final chunkSize = 300;
        final stft = STFT(chunkSize, Window.hanning(chunkSize));
        final spectrogram = <Float64List>[];
        stft.run(d, (Float64x2List freq) {
          spectrogram.add(freq.discardConjugates().magnitudes());
        });

The result of the spectrogram is a list of 151 double array and etc

stft = {STFT} 
 _fft = {CompositeFFT} CompositeFFT(300)
 _win = {_Float64List} size = 300
 _chunk = {_Float64x2List} size = 300

Where can I find frequency information from this spectrogram? and how to split?

There's a faster 64-bit reversal algorithm than what we're doing. It's O(log(bits)) instead of O(bits), using clever bit hacks:

x = ((x >> 32) & 0x00000000ffffffff) | (x << 32);
x = ((x >> 16) & 0x0000ffff0000ffff) | ((x & 0x0000ffff0000ffff) << 16);
x = ((x >> 8) & 0x00ff00ff00ff00ff) | ((x & 0x00ff00ff00ff00ff) << 8);
x = ((x >> 4) & 0x0f0f0f0f0f0f0f0f) | ((x & 0x0f0f0f0f0f0f0f0f) << 4);
x = ((x >> 2) & 0x3333333333333333) | ((x & 0x3333333333333333) << 2);
x = ((x >> 1) & 0x5555555555555555) | ((x & 0x5555555555555555) << 1);

This is slightly different to our case because we want to reverse the bit string based on the size of the FFT. So for a 256 element FFT we want to turn 0x1 into 0x80, not 2^63. So we'll need to shift the result based on the log2 of the FFT size.

Also rerun the benchmarks with this improvement.

Hi.
I'am trying to get information from audio like Key and BPM from Audio byte.
Can I use this package to detect audio key and Bpm?

My audio byte in pcm16buffer with sample rate 16000 but stored in Uint8List, so i convert to Int16List.

         List<double> pcmDoubleData = audioBytes.buffer
          .asInt16List()
          .map((value) => value / 32768.0)
          .toList();

But i don't know next part to using this fft.

Hi I have used FFT(); like this
...
final fftx = FFT(audio.length);
final freqlist = fftx.realFft(audio);
...
that result is real and imagine number
How i convert to Decibel ?

https://github.com/benchmark-action/github-action-benchmark

Is there anywhere we're calculating the GCD? If so, implement Stein's algorithm to make it faster.

CompositeFFT is built on a series of lower level FFTs that are evaluated in sequence. But the evaluation order doesn't matter. So what happens if we change the order? Is it faster to do the larger FFTs first, or smaller first?

I don't know about audio data / data science, but can this library produce sound from text,

sorry this question is stupid, I'm really already dizzy looking on google

I would like to have GPU accelerated FFT.
Is it possible?
This will have applications for real time simulations and games.

Hello dear @liamappelbe
Can you provide an explanation for spectrogram example please?

Hello!
Congratulations for this great project. I'm glad that you mentioned SciDart inside of your benchmarks.
I quit the Radix implementation because of complexity and the shortly time. I'm just wondering here: What you think to bring this implementation to be part of SciDart? For me make sense because SciDart was born exactly with the propose to merge all the Dart Scientific stuff.

Hello, I'm looking for Gaussian Window implementation. Is there any future plan?

Thank you a lot for this great plugin !
It works perfectly on Android, but I get this error on web :

The integer literal 0xAAAAAAAAAAAAAAAA can't be represented exactly
in JavaScript

I was planing on replacing all those 64bits integer litterals by something along the line of this.
for my app. Do you know if there would be a better way ?

Hello, I'm trying to implement a function to extract MFCCs and I need to understand its function.

I implemented this same algorithm in Javascript and it gave great results, but for that I used tensorflow.
I used it like this:

const stfts = tf.signal.stft(input, n_fft, 512);

How could I use your function to do something like this?

Please understand that I don't have much understanding on the matter.

Hello. I'm wondering how I can use the FFT to change the pitch of audio data in pcm16 format. I've already been using this package flutter ffmpeg, which works great with this argument:

   "-i test.mp3 -af  asetrate=$sampleRate*$shift=$sampleRate,atempo=1/$shift output.mp3";

However, since this ffmpeg requires writing and reading files, it takes time to change the pitch on realtime. So, how does this FFT achieve pitch changes more efficiently?

primePaddingHeuristic is built on largestPrimeFactor, but that function is overkill. We don't care what the largest prime factor is, just whether it's larger than 5. Write a new function that returns a bool of whether the number's largest prime factor is larger than some threshold: largestPrimeFactorIsLargerThan(n, p). This function can bail early if it divides out all the prime factors below that limit, but the number still hasn't been reduced to 1.

Hello.
I have a reference wav file and wanna compare other wav files with it to check if same pattern is played or not.
I wrote the below code (Also I used wav package to read wav file data and fl_chart to draw line charts).

import 'package:wav/wav.dart';
import 'package:fftea/fftea.dart';
...

    final Wav wav1 = await Wav.readFile("path-to-reference-sound.wav");
    List<double> wavData1 = wav1.channels[0];
    final fftxWav1 = FFT(wavData1.length);
    final freqListWav1 = fftxWav1.realFft(wavData1).discardConjugates().magnitudes();
    final List<double> decibelsWav1 = freqListWav1.map((amp) => 20 * math.log(amp) / math.ln10).toList();

    final Wav wav2 = await Wav.readFile("path-to-second-sound.wav");
    List<double> wavData2 = wav2.channels[0];
    final fftxWav2 = FFT(wavData2.length);
    final freqListWav2 = fftxWav2.realFft(wavData2).discardConjugates().magnitudes();
    final List<double> decibelsWav2 = freqListWav2.map((amp) => 20 * math.log(amp) / math.ln10).toList();

    for (int i = 0; i < decibelsWav1.length; ++i) {
      final freq = fftxWav1.frequency(i, 44100);
      chartPointsWave1.add(FlSpot(freq, freqListWav1[i]));
    }
    for (int i = 0; i < decibelsWav2.length; ++i) {
      final freq = fftxWav2.frequency(i, 44100);
      chartPointsWave2.add(FlSpot(freq, freqListWav2[i]));
    }

Now I can draw 2 line charts from chartPointsWave1 and chartPointsWave2.
Is this approach true?
Could you please suggest me a solution?

How hard would this be? Is it worth the effort? Last time I implemented non-power-of-two sizes it was really complicated and had serious numerical precision issues. Maybe could do one of the factorization based algorithms with an O(n^2) fallback for prime sizes?

Hello,

I would like some guidance on how to implement a real-time (FFT) on microphone data to detect the peak frequency. However, most of the examples in the repo are using WAV files, and I am unsure of how to get this working with the microphone data directly on the device.

Currently, I am using mic_stream lib to obtain real-time readings of the microphone as 32-bit float Pulse Code Modulation (PCM) values. My current approach is to buffer X number of samples from the mic_stream, run a STFT on the buffered input, and then use the magnitude method to perform a max search to get the index of the peak frequency. Finally, I use the stft.frequency method to obtain the actual frequency.

I'm having trouble selecting the buffer sample size X. My current approach is to collect values of the mic_stream lib for 250ms, then process it via STFT. Unfortunately, in 90% of cases, the STFT function returns a list of NaN values, and in cases where it does not, the detected peak is not even close to the frequency I am playing into the input (200hz wave).

Now I am unsure if the data I feed into the STFT is simply wrong (each sample: [-1.0; 1.0), and 32 bit precision) or if the samplingFrequency I am using for the index to frequency conversion is wrong? Currently, I am using the samplingfrequency of the mic that the mic_stream lab reports.

I wrote a small bit of code to make sure that I understand how this package works and that I get correct results. Maybe this is useful for someone else.

import 'dart:math';
import 'package:fftea/fftea.dart';
import 'dart:typed_data';

const double time = 1; // Seconds
const int fs = 48000; // Samplerate
const double delta_t = 1/fs; // Time between each audio sample
const double delta_f = fs/(time*fs); // Frequency resolution of fft output
const double ampl1 = 0.8, freq1 = 256, angle1 = 45; // Sine wave parameters (for generating input waveform)
double log10(num x) => log(x) / ln10;

void myfft(List<double> tvec, [List<double>? window, double windowcorrectionfactor = 1]) {
  List<double> itvec = List.from(tvec);
  if (window != null) {
    // Apply window
    for (var i = 0; i < itvec.length; i++) {
      itvec[i] *= window[i];
    }
  }
  // Calculate fft
  final fft = FFT(itvec.length);
  final freqbins = fft.realFft(itvec);
  // Remove frequencies above the Nyquist frequency
  Float64x2List fftresultF64x2 = freqbins.discardConjugates();
  // Calculate the phase/angle of each frequency component.
  List<double> fftangle = fftresultF64x2.map((i) => atan(i.y/i.x).toDouble()).toList();
  // Get the magnitude of each frequency component.
  Float64List fftamplF64 = fftresultF64x2.magnitudes();
  // Normalise (multiply by two because we discarded half the energy, divide by number of input samples) and correct for Window function
  List<double> fftresult = fftamplF64.map((i) => windowcorrectionfactor*2*i.toDouble()/itvec.length ).toList();

  // Find max, this should be from our input sine wave
  double max = 0;
  int maxindex = 0;
  for (int i = 0; i < fftresult.length; i++) {
    if (fftresult[i] > max) {
      max = fftresult[i];
      maxindex = i;
    }
  }
  // Look at bins around the max bin.
  for (int i = maxindex-3; i <= maxindex+3; i++) {
    //print("bin: ${i}, value: ${fftresult[i]}, ${freqbins[i].x}, ${freqbins[i].y}, ${freqbins[48000-i].x}, ${freqbins[48000-i].y}");
  }
  
  print("Number of input samples: ${itvec.length}, output bins: ${freqbins.length}, after discard: ${fftamplF64.length}");
  print("Amplitude is ${max} and phase is ${360*fftangle[maxindex]/(2*pi)} at frequency ${maxindex*delta_f}");
  print("");

}

void fftstuff() {
  List<double> tvec = []; // A list for holding the input samples
  // Generate sine to feed the fft.
  for (double i = 0; i <= time; i += delta_t) {
    tvec.add(ampl1 * cos(2*pi*freq1*i+angle1*2*pi/360));
  }

  // Perform fft with no window (rectangular), then hanning and hamming.
  myfft(tvec);
  myfft(tvec, Window.hanning(tvec.length), 2);
  myfft(tvec, Window.hamming(tvec.length), 1.85);
}

void main() {
  fftstuff();
}

The output is:

Number of input samples: 48000, output bins: 48000, after discard: 24001
Amplitude is 0.800000000000011 and phase is 45.000000029805 at frequency 256.0

Number of input samples: 48000, output bins: 48000, after discard: 24001
Amplitude is 0.7999833333354626 and phase is 45.00000002217547 at frequency 256.0

Number of input samples: 48000, output bins: 48000, after discard: 24001
Amplitude is 0.7991858166684803 and phase is 45.000000023305795 at frequency 256.0

Changing the sample rate of an audio signal is another super common use case of FFT that would make for a good util, like the convolution util.