In this paper, the performance of Auto-Regressive (AR) and Periodic Auto-Regressive (PAR) algorithms when used to predict cyclostationary signals is analyzed and evaluated. Both analytical and computer simulation results indicate that when predicting cyclostationary signals, the PAR predictor significantly outperforms the AR predictor at the expense of higher computational complexity. Various trade-offs between performance improvement and the knowledge of certain signal characteristics as well as computational efficiency are thoroughly investigated. For implementation purposes, a new adaptive algorithm for realizing the PAR predictor is proposed and its performance has been evaluated by means of computer simulations.