We present efficient and accurate approximation algorithms for computing the premium price of Asian options. First, we modify an algorithm developed by Aingworth et al. in SODA 2000 for pricing the Europian-Asian option and improve its accuracy (both theoretically and practically) by transforming it into a randomized algorithm. Then, we present a new option named Saving-Asian option, whose merit is in the middle of European-Asian and American-Asian options, and show that our method works for its pricing.