This paper describes a fast digital background calibration algorithm for pipeline or cyclic analog-to-digital converters. The proposed method corrects for the finite gain/bandwidth of the interstage operational amplifier and for capacitor mismatch in multiplying digital-to-analog converters stages. The new algorithm, fast gain error correction, converges more than 100 times faster than other correlation-based correction techniques presented in literature. The high speed of convergence of the error estimation is due to the use of a polynomial interpolation that cancel the interference in the error estimation process caused by the input signal. This new method does not need any added analog circuitry, does not perturb the output samples, and requires only a digital finite-impulse response filter to implement the polynomial interpolation as opposed to existing fast converging correlation techniques.