Nonlinear Fourier Transforms (NFTs) are generalizations of the conventional Fourier transform that allow to solve specific nonlinear evolution equations in a way that is analogous to how Fourier solved the heat equation. The evolution of the nonlinear Fourier spectrum is, exactly like in the linear case, much simpler than the evolution of the original signal. The celebrated fast Fourier transform (FFT) algorithms are linear approximations of the Fourier transform. For smooth signals the result of the FFT convergences very quickly to the true Fourier transform. Unfortunately, unlike for the FFT, the accuracy of the FNFTs remains (at most) second-order even when the signal is smooth. In this work we developed an NFT algorithm that requires only O(D log^2 D) floating point operations, but achieves a sixth-order [O(D ^−6 )] error decay.