Gravity interpretation of large sedimentary basins requires a large number of observations and of parameters estimations, so the development of very efficient gravity inversion methods applicable to such environments is of utmost importance. We found that the highly efficient Bott’s method can be cast in the framework of Gauss-Newton’s method for minimizing nonlinear functions. Also, we extended Bott’s method to (1) be applicable to sedimentary basins with density contrast between the sediments and the basement decreasing with depth according to different laws, (2) optimize the modulus of the parameter correction vector, (3) stabilize the solution by imposing that it be smooth, and (4) quit the iteration according to an objective and effective criterion. To keep up the efficiency of Bott’s method, stable solutions were obtained by applying a moving average to the usually unstable solution obtained at the last iteration. Solutions as efficacious as those obtained by the usual nonlinear method were produced by the present extension at a much smaller computation time. Nonlinear methods, with different implementations for solving a linear system of equations, required between one and two orders of magnitude more time to produce similar solutions using between 2000 and 3000 parameters and observations, for example.