arone-Adesi and Whaley (1987) provide a fast way to compute the values of American options.  This method is called the quadratic approximation.  The method works by defining a "cutoff" value of the stock.  For a put option, there is an early exercise premium only if the stock price is less than the cutoff value.  For a dividend-paying call option, early exercise matters only if the stock price exceeds a similar cutoff value.