Calculating the n-th root of an integer using PHP/GMP

Question

How can I calculate the n-th root of an integer using PHP/GMP?

Although I found a function called gmp_root(a, nth) in the PHP source, it seems that this function has not been published in any release yet*: http://3v4l.org/8FjU7

*) 5.6.0alpha2 being the most recent one at the time of writing

1) Please make it clearer you are talking of integers. 2) Your comment on the PHP sources is not clear, it seems implemented in your link. Do you mean that code hasn't been included in a release yet? 3) Do make it clear in the question, not just the tags, that you want to compute the root in PHP. From the title of your question, the answer is `mpz_root`. It is nice that you are sharing your ideas, but you need to spend time writing the question properly or the answer will be wasted. — Marc Glisse, Feb 22 '14 at 18:16
@MarcGlisse Thanks for your comment. You're right, I had not taken enough time. I hope the question and the answer are better after my edits now. Feel free to make further remarks or to edit the posts yourself ;) — ComFreek, Feb 22 '14 at 18:28
possible duplicate of [Calculating Nth root with bcmath in PHP](http://stackoverflow.com/questions/11242920/calculating-nth-root-with-bcmath-in-php) — Carsten, Feb 22 '14 at 18:37
@Carsten It is **not** a duplicate. Your linked question asks for a solution usign bcmath. In fact, I have even used the code provided in the answer on that question for my answer below. — ComFreek, Feb 22 '14 at 18:38
@ComFreek You are right, thanks. Sorry about that. I have retracted my vote. — Carsten, Feb 22 '14 at 18:47

score 3 · Accepted Answer · edited May 23 '17 at 12:03

Original source: Calculating Nth root with bcmath in PHP – thanks and credits to HamZa!

I've rewritten the code to use GMP instead of BCMath:

function gmp_nth_root($num, $n) {
    if ($n < 1) return 0; // we want positive exponents 
    if ($num <= 0) return 0; // we want positive numbers 
    if ($num < 2) return 1; // n-th root of 1 or 2 give 1 

    // g is our guess number 
    $g = 2; 

    // while (g^n < num) g=g*2 
    while (gmp_cmp(gmp_pow($g, $n), $num) < 0) { 
        $g = gmp_mul($g, 2); 
    } 
    // if (g^n==num) num is a power of 2, we're lucky, end of job 
    if (gmp_cmp(gmp_pow($g, $n), $num) == 0) { 
        return $g; 
    } 

    // if we're here num wasn't a power of 2 :( 
    $og = $g; // og means original guess and here is our upper bound 
    $g = gmp_div($g, 2); // g is set to be our lower bound 
    $step = gmp_div(gmp_sub($og, $g), 2); // step is the half of upper bound - lower bound 
    $g = gmp_add($g, $step); // we start at lower bound + step , basically in the middle of our interval 

    // while step != 1 

    while (gmp_cmp($step, 1) > 0) { 
        $guess = gmp_pow($g, $n); 
        $step = gmp_div($step, 2); 
        $comp = gmp_cmp($guess, $num); // compare our guess with real number 
        if ($comp < 0) { // if guess is lower we add the new step 
            $g = gmp_add($g, $step); 
        } else if ($comp == 1) { // if guess is higher we sub the new step 
            $g = gmp_sub($g, $step); 
        } else { // if guess is exactly the num we're done, we return the value 
            return $g; 
        } 
    } 

    // whatever happened, g is the closest guess we can make so return it 
    return $g; 
}

Calculating the n-th root of an integer using PHP/GMP

1 Answers1

Linked