FFT without loops, is it possible?

Richard_Russell

This is a genuine question, I don't already know the answer! Is it possible to code a Fast Fourier Transform in BBC BASIC, using array arithmetic to avoid the usual loops (hence making it much quicker)? It would be amazing if it is, but I really have no idea.

P.S. If this question is deemed inappropriate for this forum, please delete it. Thanks.

Soruk

I don't know the maths of FFT, however as far as appropriateness goes, it's perfectly fine.

Richard_Russell

Soruk wrote: »

I don't know the maths of FFT, however as far as appropriateness goes, it's perfectly fine.

Thanks. I find it difficult to navigate the fine line between this being a forum to support and promote Matrix Brandy and it being permitted to discuss other dialects (hence deleting my previous post).

I felt much the same at StarDot, which exists very specifically to support Acorn products, but where discussion of my BASICs was tolerated (despite which I was always uneasy about doing so).

There's a BBC BASIC implementation of the FFT algorithm at Rosetta Code, but it uses loops as is conventional. Before even contemplating whether it might be possible to use array arithmetic the structures would have to be converted to arrays.

Soruk

If it's about BBC BASIC then it's on topic, and there are sections for specific variants if it isn't a general BBC BASIC question, so you mustn't feel a BBC BASIC question is off-topic here.

When I get some time I'll have a look at the Rosetta Code implementation (at the moment I'm out with my little boy enjoying the good weather today)

Richard_Russell

Richard_Russell wrote: »

Is it possible to code a Fast Fourier Transform in BBC BASIC, using array arithmetic to avoid the usual loops (hence making it much quicker)?

I should have realised that the DFT (Discrete Fourier Transform) can be implemented as a dot-product, so not only is it possible to code a Fourier Transform without loops, it can be done in a single BBC BASIC statement!

Of course this isn't an FFT (Fast Fourier Transform), so the "hence making it much quicker" comment doesn't necessarily apply, but I reckon that because of the efficiency of the dot-product it's probably faster than an FFT coded in BBC BASIC up to an aperture of at least 256.

Even when it's not any faster, the elegance of the dot-product solution makes it very attractive. I've coded a 1024-aperture audio spectrum analyser this way and it works in near real-time (especially when the imaginary input terms and negative output frequencies are eliminated, which is appropriate for audio).

Here's a reworking of the BBC BASIC FFT example at Rosetta Code (which is only an aperture of 8) using the dot-product DFT technique:

      DIM in(7), out(15), DFT(15,7)

      N% = DIM(in(),1) + 1
      FOR I% = 0 TO N%-1
        FOR J% = 0 TO N%-1
          DFT(2*I%+0,J%) = COS(-2*PI*I%*J%/N%)
          DFT(2*I%+1,J%) = SIN(-2*PI*I%*J%/N%)
        NEXT
      NEXT I%

      DATA 1, 1, 1, 1, 0, 0, 0, 0

      @% = &2060A
      PRINT "Input (real, imag):"
      FOR I% = 0 TO N%-1
        READ in(I%)
        PRINT in(I%) "," 0
      NEXT

      out() = DFT() . in()

      PRINT '"Output (real, imag):"
      FOR I% = 0 TO N%-1
        PRINT out(2*I%+0) "," out(2*I%+1)
      NEXT
      END