FFT without loops, is it possible?
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.
P.S. If this question is deemed inappropriate for this forum, please delete it. Thanks.
0
Comments

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

I don't know the maths of FFT, however as far as appropriateness goes, it's perfectly fine.
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.0 
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 offtopic 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)0 
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)?
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 dotproduct 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 dotproduct solution makes it very attractive. I've coded a 1024aperture audio spectrum analyser this way and it works in near realtime (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 dotproduct 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
0