title: Can't figure out how to implement fourier series in python
body: <p>I have resently stumbled uppon this Video <a href="https://www.youtube.com/watch?v=r6sGWTCMz2k" rel="nofollow noreferrer">https://www.youtube.com/watch?v=r6sGWTCMz2k</a> by 3Blue1Brown explaining what a fourier series is.
  I was amazed by this mathematical pattern which seems like sorcery and wanted to implement it for myself. So, a lot of investigation later and I think I have gotten the basic hang of it, however my code does not yet work.
  I am using the discrete Fourier Transform to compute the phase and radius of epicycles, which each rotate with a certain frequency in an arbitrary range, to trace out a line which passes through a bunch of given sample points.
  I'm using the module pygame to visualize what i am doing and the module cmath for the exp operation.</p>
  <pre><code>import pygame as pg
  import cmath
  
  # my implementation of the fast fourier transform
  def fft(samples, k): # takes in the samplepoints and a frequency
      N = len(samples)
  
      # summing all the ft's for the sample points up and normalizing them
      sum_ = 0
      for n in range(0, N):
          sum_ += samples[n] * cmath.exp(-2 * cmath.pi * 1j * k * n / N)
      return sum_
  
  def main():
      pg.init()
      RES = WIDTH, HEIGHT = 1000, 600
      screen = pg.display.set_mode(RES)
      clock = pg.time.Clock()
      font = pg.font.Font('assets/Fonts/Raleway/Raleway-Light.ttf', 16)
  
      # sample points I want to use (a square):
      samplepoints = [[-1, -1], [1, -1], [1, 1], [-1, 1]]
  
      # creating more sample points through interpolation for better aproximation of the path
      samplepoints_len = len(samplepoints)
      new_samplepoints = []
      samples = 100 # total number of samples I want
      for i in range(samples):
          n_ = i / samples * samplepoints_len
          t = n_ % 1
          index = int(n_)
          p = (
                  samplepoints[index][0] + (samplepoints[(index + 1) % samplepoints_len][0] - samplepoints[index][0]) * t, # interpolate between the current and the next sample point
                  samplepoints[index][1] + (samplepoints[(index + 1) % samplepoints_len][1] - samplepoints[index][1]) * t  # interpolate between the current and the next sample point
              )
          new_samplepoints.append(p)
      samplepoints = new_samplepoints
  
      # create a complex set of sample points
      complex_samplepoints = [complex(s[0], s[1]) for s in samplepoints]
  
      # compute the coefficients for the different frequency epicycles
      coeffs = [fft(complex_samplepoints, k) for k in range(-int(samples / 2), int(samples) + 1)]
  
      # t = time
      # s = scalar for drawing purposes
      # path = the path that will be traced out by the epicycles
      t = 0
      s = 100
      path = []
      
      while True:
          for event in pg.event.get():
              if event.type == pg.QUIT:
                  pg.quit()
                  quit()
  
          # increment time
          t += 0.5
  
          screen.fill('black')
          surf = font.render('t: ' + str(round(t, 4)), True, (255, 255, 255))
          screen.blit(surf, (20, 20))
  
          # computing the fourier series at point t in time
          n = samples
          ftx = 0 # fourier transform x
          fty = 0 # fourier transform y
          for i in range(-int(samples / 2), int(samples / 2) + 1): # looping through all the different frequencys
              e = coeffs[i] * cmath.exp(-2 * cmath.pi * 1j * t / n) # computing the current epicycle position
              
              ftx += e.real # incrementing the x value, essentialy adding up the epicycles
              fty += e.imag # incrementing the y value, essentialy adding up the epicycles
          
          ftx /= n # normalizing the computed values
          fty /= n # normalizing the computed values
  
          path.append((ftx * s + WIDTH / 2, fty * s + HEIGHT / 2)) # add last epicycles position to the path
  
          pg.draw.lines(screen, (80, 80, 80), False, [(p[0] * s + WIDTH / 2, p[1] * s + HEIGHT / 2) for p in samplepoints], 1) # drawing the sample points
  
          # draw the path on screen
          if len(path) &gt; 1:
              pg.draw.lines(screen, 'white', False, path, 1)
          
          pg.draw.circle(screen, (255, 128, 128), (ftx * s + WIDTH / 2, fty * s + HEIGHT / 2), 5) # drawing the last epicycle position
  
          pg.display.update()
          clock.tick(60)
  
  if __name__ == '__main__':
      main()
  </code></pre>
  <p>This is what I've got so far:</p>
  <p><a href="https://i.stack.imgur.com/UdPgf.gif" rel="nofollow noreferrer">https://i.stack.imgur.com/UdPgf.gif</a></p>
  <p>Can anyone explain what is wrong with my code?</p>