A novel fast calculation algorithm (FCA) for calculating the decision metric of the multiple-symbol differential detection (MSDD) considering the autocorrelation of a received sequence is proposed. In correspondence to the star quadrature amplitude modulation (QAM), the M algorithm is adopted to MSDD over Rayleigh fading channels, in order to reduce the number of search paths. The computational complexity of the decision metric can be greatly reduced by the proposed FCA and the M algorithm. Through computer simulations, it is confirmed that the symbol error rate (SER) performance of the MSDD considering autocorrelation is closer to that of the ideal coherent detection as the length of an observed sequence becomes larger over Rayleigh fading channels.