0

Wikipedia has a small article on finding the nth root of reals and another article on a more efficient implementation, both obviously adaptable to floats. And of course, efficient integer square root algorithms also exist - there's multiple questions on this site just about efficient implementations for that.

But all those deal with reals, and all I'm concerned about here are integers. I did find an existing question on the topic where this may seem almost a duplicate of, but where that's asking about if an efficient algorithm exists, I'm looking for what the most efficient algorithm is.

For context, this would only be used with 32-bit two's complement integers (specifically coerced signed JS integers) and it would be as part of a generic signed integer exponentiation algorithm int iexp(int base, int exp), handling the case of negative exponents. Bit hacks and other two's complement hacks are fair game here - I don't care and I do understand them to some extent. (It's for a standard library implementation for a language I'm working on, so I'd rather this not be slow.)

And language doesn't matter - I can translate whatever, whether it's C, JS, Python, or even OCaml.

Claudia
  • 1,197
  • 15
  • 30
  • 1
    Did you see [Calculate Nth root with integer arithmetic](https://stackoverflow.com/questions/8826822/calculate-nth-root-with-integer-arithmetic)? – RobertBaron Jun 04 '19 at 11:05
  • **The** most efficient algorithm never exists. This is context dependent. –  Jun 04 '19 at 12:34
  • @RobertBaron I saw that, but I forgot to mention it. Also, it's more about how to calculate it in the first place, not about any efficient means of doing it. – Claudia Jun 05 '19 at 01:46
  • @YvesDaoust I mean the most efficient known algorithm for general 32-bit input with exact results and rounded towards 0, where the root exponent is always positive. Of course, this is normally context dependent and I know this, but my context is pretty generic and this is a pretty limited (albeit not uncommon) domain. – Claudia Jun 05 '19 at 01:50
  • @IsiahMeadows: anyway, **the** most efficient algorithm does not exist. There is no total ordering between algorithms. –  Jun 05 '19 at 07:33

1 Answers1

2

For n>2, a serious option is dichotomic search in a lookup-table. For n=3, the table takes 1290 entries (hence 11 dichotomic steps). For n=4, 215 entries (8 steps) and n=5, 75 entries (7 steps)…

If I am right, you can even compress the tables because for large numbers the low order bits make no difference and the arguments can be down-scaled. (This needs to be expanded.)

For n>30, the only (truncated) values are 0 or 1.