jacob:~/CS/cs325/hw7% ./classical 3 1 2 3 4 1 2 3 4
1x^6 4x^5 10x^4 20x^3 25x^2 24x^1 16x^0
jacob:~/CS/cs325/hw7% ./fft 3 1 2 3 4 1 2 3 4
1x^6 4x^5 10x^4 20x^3 25x^2 24x^1 16x^0

jacob:~/CS/cs325/hw7% ./classical 3 25 80 -101 1 1 -1 1 -1
25x^6 55x^5 -156x^4 157x^3 -182x^2 102x^1 -1x^0
jacob:~/CS/cs325/hw7% ./fft 3 25 80 -101 1 1 -1 1 -1
25x^6 55x^5 -156x^4 157x^3 -182x^2 102x^1 -1x^0

jacob:~/CS/cs325/hw7% ./classical 3 1 0 0 -1 1 0 0 -1
1x^6 -2x^3 1x^0
jacob:~/CS/cs325/hw7% ./fft 3 1 0 0 -1 1 0 0 -1
1x^6 -1.57009e-16x^5 -1.11022e-16x^4 -2x^3 5.55112e-17x^2 1.57009e-16x^1 1x^0
[*] Really mean of me to pick this case as it has root pairs that
    clearly are running over my precision during the interpolation.

jacob:~/CS/cs325/hw7% ./classical 7 1 2 3 4 5 6 7 8 8 7 6 5 4 3 2 1
8x^14 23x^13 44x^12 70x^11 100x^10 133x^9 168x^8 204x^7 168x^6
133x^5 100x^4 70x^3 44x^2 23x^1 8x^0
jacob:~/CS/cs325/hw7% ./fft 7 1 2 3 4 5 6 7 8 8 7 6 5 4 3 2 1
8x^14 23x^13 44x^12 70x^11 100x^10 133x^9 168x^8 204x^7 168x^6
133x^5 100x^4 70x^3 44x^2 23x^1 8x^0

jacob:~/CS/cs325/hw7% ./classical 7 1 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 1
-1x^14 2x^7 -1x^0
jacob:~/CS/cs325/hw7% ./fft 7 1 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 1
-1x^14 1.08154e-17x^13 -3.27998e-16x^12 4.22553e-18x^11
-9.13961e-17x^10 -9.70182e-17x^9 -1.11022e-16x^8 2x^7
-1.66533e-16x^6 4.46743e-16x^5 -5.06865e-18x^4 1.06797e-16x^3
-1.30648e-16x^2 8.3549e-17x^1 -1x^0
[*] Once again here's a case where the interpolation hits a bumpy
    little singularity and looses some significance.  Looks like
    subtraction of similars to me.

jacob:~/CS/cs325/hw7% ./classical 7 1235 67 13 4 46 123 46 245
123 4 64 42 234 3 45 23
151905x^14 13181x^13 80907x^12 56702x^11 298310x^10 35498x^9
68080x^8 72518x^7 21992x^6 47011x^5 23585x^4 64061x^3 5634x^2
12083x^1 5635x^0
jacob:~/CS/cs325/hw7% ./fft 7 1235 67 13 4 46 123 46 245 123 4
64 42 234 3 45 23
151905x^14 13181x^13 80907x^12 56702x^11 298310x^10 35498x^9
68080x^8 72518x^7 21992x^6 47011x^5 23585x^4 64061x^3 5634x^2
12083x^1 5635x^0

jacob:~/CS/cs325/hw7% ./classical 7 4 0 -34 0 24 0 234 -1 54
-34 0 6 0 -34 0 67
216x^14 -136x^13 -1836x^12 1180x^11 1296x^10 -1156x^9 12636x^8
-6442x^7 34x^6 -1690x^5 -6x^4 -6348x^3 34x^2 15678x^1 -67x^0
jacob:~/CS/cs325/hw7% ./fft 7 4 0 -34 0 24 0 234 -1 54 -34 0 6
0 -34 0 67
216x^14 -136x^13 -1836x^12 1180x^11 1296x^10 -1156x^9 12636x^8
-6442x^7 34x^6 -1690x^5 -6x^4 -6348x^3 34x^2 15678x^1 -67x^0
[*] Fairly evenly spread values make it easier to interpolate.

jacob:~/CS/cs325/hw7% ./classical 15 1 2 3 4 5 6 7 8 9 a b c
d e f 16 1 2 3 4 5 6 7 8 9 0xa 0xb 0xc 0xd 0xe 0xf 16
1x^30 4x^29 10x^28 20x^27 35x^26 56x^25 84x^24 120x^23 165x^22
201.25x^21 227.875x^20 244x^19 248.75x^18 241.25x^17 220.625x^16
216x^15 194.375x^14 154.75x^13 183.625x^12 210x^11 233.75x^10
254.75x^9 272.875x^8 288x^7 20x^6 22x^5 24x^4 26x^3 28x^2 30x^1
256x^0
jacob:~/CS/cs325/hw7% ./fft 15 1 2 3 4 5 6 7 8 9 a b c d e f
16 1 2 3 4 5 6 7 8 9 0xa 0xb 0xc 0xd 0xe 0xf 16
1x^30 4x^29 10x^28 20x^27 35x^26 56x^25 84x^24 120x^23 165x^22
201.25x^21 227.875x^20 244x^19 248.75x^18 241.25x^17 220.625x^16
216x^15 194.375x^14 154.75x^13 183.625x^12 210x^11 233.75x^10
254.75x^9 272.875x^8 288x^7 20x^6 22x^5 24x^4 26x^3 28x^2 30x^1
256x^0
[*] FFT works really well when you don't give it gaps.  :)

jacob:~/CS/cs325/hw7% ./classical 15 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 -1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
1x^30 -2x^15 1x^0
jacob:~/CS/cs325/hw7% ./fft 15 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
1x^30 -1.94454e-17x^29 5.7438e-16x^28 4.48995e-17x^27
4.04345e-16x^26 -1.98025e-17x^25 1.52249e-16x^24 -2.82404e-16x^23
-3.61481e-17x^22 1.29417e-16x^21 4.43718e-17x^20 3.92814e-16x^19
6.46551e-17x^18 2.84939e-16x^17 -2x^15 -5.96964e-16x^13
1.72962e-17x^12 -4.92923e-16x^11 -3.81824e-17x^10 -1.08556e-16x^9
6.97955e-17x^8 6.03595e-17x^7 2.02682e-16x^6 -4.9071e-17x^5
-8.09366e-17x^4 -1.66835e-16x^3 -2.08773e-16x^2 -6.46072e-17x^1
1x^0
[*] But _man_ it's sure fun to play with it's brain...