This article presents the Gibbs-Skovgaard algorithm for approximate frequentist inference. The method makes use of the double saddlepoint approximation of Skovgaard to the conditional cumulative distribution function of a sufficient statistic given the remaining sufficient statistics. This approximation is then used in the Gibbs sampler to generate a Markov chain. The equilibrium distribution of this chain approximates the joint distribution of the sufficient statistics associated with the parameters of interest conditional on the observed values of the sufficient statistics associated with the nuisance parameters. This Gibbs-Skovgaard algorithm is applied to the cases of logistic and Poisson regression.