I wrote a 2-adic Newton implementation of exact rth root. I don't think it's quite ready for a pull request, but let me know what you think. It might be a useful replacement for perfect powers in your library, perhaps for certain values of r and x. It seems to run a few times faster for small roots of big numbers, and it doesn't die as badly for huge roots.
Issue #10 new