View Single Post
Old 2011-04-13, 23:22   #5
science_man_88's Avatar
"Forget I exist"
Jul 2009

100000110000002 Posts

Originally Posted by CRGreathouse View Post
With ispower() there's no need to loop at all -- ispower(N) does the right thing. ispower(N, b) is only when you want to check for a particular base and no others.

You should look at the code for it some time, it's fascinating. They check for 2nd, 3rd, and 5th powers separately, then move on to general testing for larger bases. Some amount of trial division is also done so you don't have to check quite as high, IIRC.

Incidentally, Bernstein has a nice paper about doing this test efficiently, in almost-linear time. Pretty impressive stuff.
Bernstein ? I don't have a math degree and have never read the name to my knowledge.
science_man_88 is offline   Reply With Quote