1. A method, implemented in an encoder having at least one calculator, of searching an algebraic codebook during encoding of a sound signal, wherein the algebraic codebook comprises a set of codevectors formed of a number of pulse positions and a number of pulses each having a sign and distributed over the pulse positions, and wherein the algebraic codebook searching method comprises: calculating, using the at least one calculator, a reference signal for use in searching the algebraic codebook; in a first stage, (a) determining, using the at least one calculator, in relation with the reference signal and among the number of pulse positions, a position of a first pulse; in each of a number of stages subsequent to the first stage, using the at least one calculator to (a) recompute an algebraic codebook gain, (b) update the reference signal using the recomputed algebraic codebook gain and (c) determine, in relation with the updated reference signal and among the number of pulse positions, a position of another pulse; computing, using the at least one calculator, a codevector of the algebraic codebook using the signs and positions of the pulses determined in the first and subsequent stages, wherein a number of the first and subsequent stages corresponds to the number of pulses in the codevectors of the algebraic codebook.