In this paper we provide lower and upper bounds on the prices of American call and put options written on a dividend paying asset. Based on the bounds, we provide two option price approximations. Our second approximation, which uses both lower and upper bound information, has an average accuracy comparable to a 1000-step binomial tree with a computation speed comparable to a 50-step binomial tree. Put another way, our second approximation is 6 times more accurate than a 200-step binomial tree and is about 15 times faster than a 200-step binomial tree. Furthermore, the approximations are sufficiently simple that they can be computed in a spreadsheet. In addition, we conduct a careful large-scale evaluation of many recent methods for computing American option prices. Comparisons are made on the basis of accuracy and speed of computation and lead to some surprising results.