Adding one more version of the last code, faster by cutting the number of extra digits used, and by playing "the usual" low-level CPython speed tricks.

I don't claim it's always correctly rounded - although I haven't found a specific case where it isn't.  I do claim it will return the exact result whenever the exact result is representable as a float.

I also claim it's "fast enough" - this version does on the high end of 50 to 100 thousand roots per second on my box, pretty much independent of `n`.

    import decimal
    c = decimal.DefaultContext.copy()
    c.prec = 25
    def rootn(x, n,
              D=decimal.Decimal,
              pow=c.power,
              mul=c.multiply,
              add=c.add,
              div=c.divide):
        g = D(x**(1.0/n))
        n1 = D(n-1)
        g = div(add(mul(n1, g),
                    div(D(x), pow(g, n1))),
                n)
        return float(g)
    del decimal, c