In this paper an all-optical soliton method for calculating the Fast Fourier Transform (FFT) algorithm is presented. The method comes as an extension of the calculation methods (soliton gates) as they become possible in the cubic non-linear Schrödinger equation (3NLSE) domain, and provides a further proof of the computational abilities of the scheme. The method involves collisions entirely between first order solitons in optical fibers whose propagation evolution is described by the 3NLSE. The main building block of the arrangement is the half-adder processor. Expanding around the half-adder processor, the "butterfly" calculation process is demonstrated using first order solitons, leading eventually to the realisation of an equivalent to a full Radix-2 FFT calculation algorithm.