Fast Fourier transform using complex type

 

There is a post here (which updated by me) : https://rosettacode.org/wiki/Fast_Fourier_transform#M2000_Interpreter

M2000 use Complex type native. Look at Sub FFT we can use as *Complex[] to restrict the parameter to be a pointer to a RefArray type of Complex type. Because we pass a pointer by value, the RefArray values are like passed by reference, because we alter values. We need this because in other recursive calls we exchange the pointers (out in place of buf and puf in place of out).

module FFT {
	' print $("0.000", 16)   ' #1 (use #1, #2, #3 for 4 decimals for printing numbers )
	locale 1033
	open "output.txt" for wide output as #F
	complex buf[7], out[7]
	buf[0]|r = 1: buf[1]|r = 1: buf[2]|r = 1: buf[3] = (1, 0i)
	showArr(buf, "Input")
	FFT(out, buf, 0, 1, 8)
	ShowArr(out, "Output")
	' print $("") ' #2
	close #F
	print #-2, eval$(buffer(dir$+"output.txt"))
	Sub ShowArr(m, mes as string)
		local n, mx=len(m)
		print #F, mes;": (real imag abs)"
		while n<mx
			' print m[n]  ' #3
			' round(number) round to 13th decimal, is same as round(exp, 13)
			' Abs(complex) = Mod(complex)
			print #F, format$("{0:0:-10} {1:-10} {2:-12}",m[n]|r, round(m[n]|i, 4)+"", round(abs(m[n]), 8)+"")
			n++
		end while
	End Sub
	Sub FFT()
		Shift 5
		Read New N as long
		FFT1()		
	End Sub
	' FFT1() use N always
	Sub  FFT1(buf as *Complex[], out as *Complex[], begin as Long, stp as Long)
		If stp < N Then
			FFT1(out, buf, begin, 2 * stp)
			FFT1(out, buf, begin + stp, 2 * stp)
			Local i as long, t as complex
			for i=0 to N-1 step 2*stp
				t = Polar(1, -pi* i / N) * out[begin + i + stp]
				buf[begin + i  div 2] = out[begin + i] + t
				buf[begin + (i + N)  div 2] = out[begin + i] - t
			next
		End If
	End Sub
}
FFT
Output.txt
Input: (real imag abs)
         1          0            1
         1          0            1
         1          0            1
         1          0            1
         0          0            0
         0          0            0
         0          0            0
         0          0            0
Output: (real imag abs)
         4          0            4
         1    -2.4142   2.61312593
         0          0            0
         1    -0.4142    1.0823922
         0          0            0
         1     0.4142    1.0823922
         0          0            0
         1     2.4142   2.61312593