(WIP) Integer root fix

[b-mehta]

Fix for issue #177.

[Bodigrim]

Huge thanks for investigation, now it makes sense.

It is probably worth to change otherwise case below in a similar fashion.

Also, when k >= 1024 even nshiftRInteger(h# *# k#) may appear larger than 2^1024 and thus be converted to Infinity :: Double. We can resort to a simpler approximation in this case:

appKthRoot k@(I# k#) n
  | k >= 1024 = 1 `shiftLInteger` (integerLog2# n `quotInt#` k# +# 1#)
  | otherwise = ...

[b-mehta]

Perhaps I'm missing something, but would

1 `shiftLInteger` (integerLog2# n `quotInt#` k#)

not be a better approximation?

[b-mehta]

Also, do you have suggestions for further test cases that could be added to verify these?

[Bodigrim]

I would probably just copy-paste Math.NumberTheory.Powers.GeneralTests.integerRootProperty to focus on huge inputs. Something along these lines:

integerRootHugeProperty :: Huge Natural -> Large Word -> Bool
integerRootHugeProperty (Huge n) (Large pow') = pow == 0 ||
  toInteger root ^ pow <= toInteger n && toInteger n < toInteger (root + 1) ^ pow
    where
      pow = pow' `mod` 2000
      root = integerRoot pow n

[b-mehta]

Huge inputs are already tested in testIntegral2Property, I think...

[Bodigrim]

Correct, but only for small powers, I believe.

[b-mehta]

Ah, I see!

[Bodigrim]

Nice, well done!