To meet accuracy requirements of SINS that the gyro output angular rate and the accelerometer output velocity increment in harsh environments, a new paddling error compensation algorithm is redesigned. The algorithm is deduced in the condition of curve fitting angular rate and specific force. And the algorithm is optimized when carrier for rowing so that it can meet the accuracy requirements in high dynamic environment. Simulation results show that the compensation effect of optimized algorithm is better ordinary algorithm when carrier movement dramatically and it meet the accuracy requirements in high dynamic environment.