In the n-period binomial tree model, fast algorithms are provided for computing very accurate lower and upper bounds on the value of a European-style Asian option. These algorithms are inspired by the continuous-time analysis of Rogers and Shi (J. Appl. Probab., 32 (1995), 1077-1088). Specifically lower bounds are considered that are given by grouping stock-price paths in a group as having the same arithmetic stock-price average, namely the average of the arithmetic average over the group. For a specific Z, Rogers and Shi show analytically that the error in the lower bound is small. However, they are only able to estimate the lower and upper bounds numerically as integrals in continuous time. Indeed, for their choice of Z, these bounds are difficult to compute exactly in the binomial tree model. The present authors show how to choose Z so that the bounds can be computed exactly in time proportional to n4 by forward induction. Moreover, the bounds given here are strictly better.