Adaptive optics (AO) allows one to derive the point spread function (PSF) simultaneously to the science image, which is a major advantage in post-processing tasks such as astrometry/photometry or deconvolution. Based on the algorithm of Veran et al. (1997), PSF reconstruction has been developed for four different AO systems so far: PUEO, ALFA, Lick-AO and Altair. A similar effort is undertaken for NAOS/VLT in a collaboration between the group PHASE (Onera and Observatoire de Paris/LESIA) and ESO. In this paper, we first introduce two new algorithms that prevent the use of the so-called "Uij functions" to: (1) avoid the storage of a large amount of data (for both new algorithms), (2) shorten the PSF reconstruction computation time (for one o...