# FFT_AMIGA.py
# From the python 2.0.x prompt:
# >>> execfile("PATH:to/FFT.py")[ENTER]
# Very basic FFT code for tha AMIGA A1200, with 68030, MMU, MPU, and 6MB RAM.
# This is recursive and will only work on Python 2.0.x to 2.7.x on any platform.
# The only module needed is the builtin 'cmath'.
# Slowish? Yes but better to have this facility than not.
# Licence is CC0, 2017. Barry Walker, G0LCU.
# This works on just about any platform that has python 2.0.x to 2.7.x.

import cmath

def fft(DATA):
	N=len(DATA)
	if N<=1: return DATA
	EVEN=fft([DATA[K] for K in range(0,N,2)])
	ODD=fft([DATA[K] for K in range(1,N,2)])
	L=[EVEN[K]+cmath.exp(-2j*cmath.pi*K/N)*ODD[K] for K in range(int(N/2))]
	R=[EVEN[K]-cmath.exp(-2j*cmath.pi*K/N)*ODD[K] for K in range(int(N/2))]
	return L+R

# FFT_LIST=[1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0]
# [(4+0j), (1-2.414213562373095j), 0j, (1-0.4142135623730949j), 0j, (0.9999999999999999+0.4142135623730949j), 0j, (0.9999999999999997+2.414213562373095j)]
# ***********************
# For 1 cycle, 8 samples.
# ***********************
# 4.00000
# 2.61313
# 0.00000
# 1.08239
# 0.00000
# 1.08239
# 0.00000
# 2.61313

FFT_LIST=[1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
# [(32+0j), 0j, (2.0000000000000004-20.306340775217716j), 0j, 0j, 0j, (2.000000000000001-6.59311641787664j), 0j, 0j, 0j, (2-3.7417368235787785j),
# 0j, 0j, 0j, (2.0000000000000004-2.4370070511759523j), 0j, 0j, 0j, (1.9999999999999998-1.6413575816573212j), 0j, 0j, 0j, (2.000000000000001-1.069022271901583j),
# 0j, 0j, 0j, (1.9999999999999993-0.6066933672146853j), 0j, 0j, 0j, (2.0000000000000027-0.19698280671432933j), 0j, 0j, 0j, (1.9999999999999996+0.19698280671432755j),
# 0j, 0j, 0j, (1.9999999999999998+0.6066933672146848j), 0j, 0j, 0j, (1.9999999999999996+1.069022271901583j), 0j, 0j, 0j, (1.9999999999999996+1.6413575816573212j),
# 0j, 0j, 0j, (2.0000000000000004+2.4370070511759523j), 0j, 0j, 0j, (1.9999999999999982+3.7417368235787793j), 0j, 0j, 0j, (2+6.59311641787664j),
# 0j, 0j, 0j, (1.999999999999994+20.30634077521772j), 0j]
# *************************
# For 2 cycles, 64 samples.
# *************************
# 32.00000
# 0.00000
# 20.40459
# 0.00000
# 0.00000
# 0.00000
# 6.88979
# 0.00000
# 0.00000
# 0.00000
# 4.24271
# 0.00000
# 0.00000
# 0.00000
# 3.15262
# 0.00000
# 0.00000
# 0.00000
# 2.58729
# 0.00000
# 0.00000
# 0.00000
# 2.26778
# 0.00000
# 0.00000
# 0.00000
# 2.08999
# 0.00000
# 0.00000
# 0.00000
# 2.00968
# 0.00000
# 0.00000
# 0.00000
# 2.00968
# 0.00000
# 0.00000
# 0.00000
# 2.08999
# 0.00000
# 0.00000
# 0.00000
# 2.26778
# 0.00000
# 0.00000
# 0.00000
# 2.58729
# 0.00000
# 0.00000
# 0.00000
# 3.15262
# 0.00000
# 0.00000
# 0.00000
# 4.24271
# 0.00000
# 0.00000
# 0.00000
# 6.88979
# 0.00000
# 0.00000
# 0.00000
# 20.40459
# 0.00000

FFT=fft(FFT_LIST)
print(FFT)
LENGTH=len(FFT)
for FFT_LISTING in range(0,LENGTH,1): print("%.5f" %(abs(FFT[FFT_LISTING])))