The multi-pulse speech coding with pitch prediction has been known as an efficient speech coding method. In this paper, a new pulse search method is proposed for improving speech quality with small amount of computation. Characteristics of this pulse search method are listed below. 1. Modifying pulse amplitude in pulse search loop. 2. Controlling pulse search conditions. 3. Quantization of pulse positions. This pulse search method improves S/Nseg of the multi-pulse speech codec with pitch prediction on a single-chip 32-bit floating-point signal processor, by 1.0 to 1.3 dB.