A Kiefer-Wolfowitz or simultaneous perturbation algorithm that uses either one-sided or two-sided randomized differences and truncations at randomly varying bounds is given in this paper. At each iteration of the algorithm only two observations are required in contrast to 2l observations, where l is the dimension, in the classical algorithm, The algorithm given here is shown to he convergent under only some mild conditions. A rate of convergence and an asymptotic normality of the algorithm are also established.