counting rows

i need to get a row count on a large table. it appears that
  select count(*) from <table>;
always does a table scan, whether i have an index or not, and that is too
slow.

so i found this:
  select reltuples from pg_class where relname = '<table>';

this is nice and fast, but not all that accurate at any given time. but, i
*did* notice that it is pretty accurate if i run analyze just before.

so, i am wondering if analyze also does a table scan, in which case i am
back to where i started. it *seems* to run fairly quickly, even on a large
table, but i am just wall-clocking all of this.

or any other ideas on counting rows are welcome.

thanks.
pg