Free energy calculations at finite temperature based on ab initio molecular dynamics (AIMD) simulations have become possible, but they are still highly computationally demanding. Besides, achieving simultaneously high accuracy of the calculated results and efficiency of the computational algorithm is still a challenge. In this work we describe an efficient algorithm to determine accurate free energies of solids in simulations using the recently proposed temperature-dependent effective potential method (TDEP). We provide a detailed analysis of numerical approximations employed in the TDEP algorithm. We show that for a model system considered in this work, hcp Fe, the obtained thermal equation of state at 2000 K is in excellent agreement with the results of standard calculations within the quasiharmonic approximation.