Implement iroot

[wbhart]

Currently Julia has isqrt for the integer floor of the square root of an integer. We propose adding iroot to both AbstractAlgebra and Nemo to give the floor of the integer root of its input, as we are going to make root raise an exception if the root is not exact.

[fieker]

agreed

[wbhart]

@fieker Yes, I think this one is totally uncontentious.

We will eventually get around to sorting out the root stuff. The problem is, we need to rewrite parts of GMP, which we cannot do. So I really don't know how to solve this problem without substantially slowing things down.

[fieker]

I am dumb: why do we have to rewrite gmp?

[wbhart]

I'm talking more broadly here, e.g. in line with stuff we've been discussing at Nemocas/Nemo.jl#862

E.g. GMP has functions for determining whether something is a perfect power, but doesn't tell you what the power is! There's no way to get that efficiently from any of their functions.

They have functions for computing sqrt and sqrtrem, but not a function that efficiently computes the square root assuming exactness. And for example, neither do modular tests to exclude nonsquares in issquare.

There's no function exposed in GMP for determining whether something is a perfect n-th power for a specified n, full stop.

In short, we'd have to rewrite some of their functions and add others. But they don't expose enough internals in their official mpn interface to do this efficiently. So we'd either have to reproduce large chunks of GMP in Flint and add all the machinery to build assembly code for different architectures (which is tens of thousands of lines of stuff), or we'd have to do things especially inefficiently.

[wbhart]

And for example, neither do modular tests to exclude nonsquares in issquare.

Fredrik sent me some code to do this in Flint, but it's 3x slower for perfect squares, on my machine. He thinks that's not an issue. I'm still not convinced.

[fieker]

I have a "pure" Julia implementation for computing exact roots of fmpz. It is much faster than gmp, especially for larger n-th roots.
I use 2-adic lifting, 1st iterations using longs, then mpz.
Oscar/examples/PerfectPowers.jl
root_exact(a::fmpz, n::Int) will return the exact n-th root - or garbage.
It might be slower than existing for small n, but much faster than everything else for large n
ispower_bernstein(a::fmpz) finds the largest n s.th. a is an n-th power. Should be fast

[wbhart]

Sure, that's exactly how I would do it. But most of the time you will want to use the function on small inputs, not large.

We had a lot of people try to contribute such "improvements" to MPIR over the years. But the real work is in the efficient implementation.

As I said below, I can either slow things down, or I can do it in GMP where the infrastructure exists. But I can't do the latter.

Anyhow, I am glad you have a Julia implementation that works for you. That saves me putting too much thought into it (I had been thinking of finding a way to add a wrapper around GMP, with access to their internals, to add all the stuff we want).

[fieker]

my main missing "optimization" is some mul_low or mul_mod_2^k as this is only what I do....

[wbhart]

I am quite sure there are many standard optimisations you do not have. Writing mpn arithmetic is very time consuming, but the results are usually very impressive if you know all the tricks.

[wbhart]

I'll list just two important tricks GMP uses to great effect: 1) reusing temporary space optimally 2) allocating temporary space at the top level function and reusing it all the way down.