We address the mathematical challenge that arises as a computational bottleneck in solving problems such as 6D Fokker-Planck equations, multi-body Hamiltonian systems, or inferring the governing equations of complex self-organizing systems. Specifically, the challenge is to numerically compute function expansions and their derivatives fast, while simultaneously ensuring high approximation power, delivering geometric approximation rates for regular problems. Our contribution is based on a novel design of multivariate interpolation algorithms (FNT), setting a new standard in the field. While the Fast Fourier Transform (FFT) undeniably belongs to the greatest achievements in computational sciences of the last century, the polynomial interpolation approach we propose addresses its limitations, such as the requirement for periodicity and its sensitivity to the curse of dimensionality. In addition to mathematically proving that the approximation capabilities of the FNT extend beyond those of the FFT to non-periodic problems, we empirically demonstrate its superiority in terms of runtime and memory consumption, compared to both the FFT and state-of-the-art non-periodic interpolation alternatives.