nth root algorithm

ID:155663
 
Apr 20 2011, 2:18 pm
I am trying to expand upon hobnobs bignum datum but I can not figure out how to solve for nth roots.

I cam across this algorithm:
(http://en.wikipedia.org/wiki/Shifting_nth_root_algorithm).

It seems to be the best way to find the nth root of a number that is stored as a string. However, I can't figure out how to get a generic version of this algorithm working. I can kind of get it working for square root and cube root but not for any nth root. Does anyone have an implementation of this algorithm for BYOND or perhaps a pseudo code example or any other method for solving the nth root of a number stored as a text string of arbitrary length?

Here are a couple other example of the algorithm as used to solve square roots and cube roots.
http://xlinux.nist.gov/dads//HTML/cubeRoot.html
http://xlinux.nist.gov/dads//HTML/squareRoot.html


Apr 21 2011, 12:09 am
Source: http://en.wikipedia.org/wiki/Nth_root_algorithm

proc
    div(a, b, c)
        for(var/i = 1; i < b; i++)
            a = a / c
        return a

    root(num, root)
        root = round(root)
        var
            epsilon = 0
            estimate = num / root
            lastEst = 0
        do
            lastEst = estimate
            estimate = ((root - 1) * estimate + div(num, root, estimate)) / root
            epsilon = max(lastEst, estimate) / min(lastEst, estimate)
        while(epsilon > 1.0001)
        return estimate

mob/verb/test()
    world << root(5, 2)
    world << root(5, 3)
    world << root(5, 4)
    world << root(5, 5)
    world << root(275274.0, 8)
    world << root(275274.0, 9)


It's general algorithm. I assume your big numbers have basic operations as multiplication, division, adding.
Apr 21 2011, 2:13 am
In response to Zaoshi
Nice algorithm. Looks like it's based on a technique by Newton.