Hi guys...
This is code that was originally designed to work on an upgraded AMIGA A1200 using Python 2.0.x.
Unfortunately it broke inside much later versions, NOT because of the print statement/function but other minor subtleties. So this is the final result tested on various machines including the desired one.
The print(FFT) function also acts correctly, (even in Python 1.4.0 believe it or not), so there is no need to alter it for any Python version from 2.0.x to the current 3.7.0; just delete it as it is only there for this DEMO...
More information inside the code and as can be seen tested on various platforms and machines.
#
# SIMPLE_FFT.py
# For Python Version(s) 2.0.x to 3.7.0...
# 20 August 2018, CC0, Public Domain Licence.
#
# TESTED ON:
#
# Python 2.0 (#1, Oct 29 2000, 23:53:20) (SAS/C 6.x] on amiga
#
# Python 2.7.10 (default, Oct 6 2017, 22:29:07)
# [GCC 4.2.1 Compatible Apple LLVM 9.0.0 (clang-900.0.31)] on darwin
#
# Python 3.5.2 (v3.5.2:4def2a2901a5, Jun 26 2016, 10:47:25)
# [GCC 4.2.1 (Apple Inc. build 5666) (dot 3)] on darwin
#
# Python 3.7.0 (v7.7.0:1bf9cc5093, Jun 27 2018,04:59:51) [MSC v.1914 64 bit
# (AMD64)] on win32
#
# Python 2.7.15rc1 (default, Apr 15 2018, 21:51:34)
# [GCC 7.3.0] on linux2
# This is a builtin, no external libraries required.
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
# NOTE: Although not necessary, for best results, DATA sizes be in powers of 2.
# http://www.bitweenie.com/listings/fft-zero-padding/
# Single cycle square wave, 8 samples.
FFT_LIST=[1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0]
FFT=fft(FFT_LIST)
print(FFT)
# Correct results, within limits of floating point accuracy, should read:
# -----------------------------------------------------------------------
#
# [(4+0j), (1-2.414213562373095j), 0j, (1-0.4142135623730949j), 0j,
# (0.9999999999999999+0.4142135623730949j), 0j,
# (0.9999999999999997+2.414213562373095j)]