User Tools

Site Tools


nth_root_of_x

This is an old revision of the document!


Back to: Arbitrary-Precision Math

Nth Root of X

Sometimes we may want to compute a square root or a cube root or a fifth root some other root of a number to some specified degree of precision. The function below will compute the arbitrary-precision Nth root of argument X. As with all BC math functions, the X argument should be given as a numerical string, between quotes, like "1.2345" or '1.2345', so as not to be misinterpreted as a standard floating point value.

A general-purpose, arbitrary-precision, Nth root computation
function based on a simple iterative algorithm.

Let:
X = Arbitrary-precision argument for which we seek the Nth root
N = Root to iterate (2=Square root, 3=Cube root, 4=4th root, ...)
a = Current approximation to Nth root of X
b = Next generation approximation derived from (a)
d = Decimals precision limit

================
Given (N, X, a):

Let:
n = N-1

START:
b = (a + X/(a^n)) / n

If (a == b) to (d) decimals, then finished, (b) is the root value.

If not, then at least one more approximation cycle is needed.
For next approximation, let current output (b) become next input (a):
a = b
and repeat the process from START with this updated (a) value. 

Each successive value of (b) will be closer to the root than the
previous value.

The root computing function is listed below.

/*
   ------------------------------------------------------------------
   This function computes the arbitrary-precision Nth root of a given
   numerical string X, rounded to any specified number of decimals.

   ARGUMENTS:
   N = Root = Integer 2, 3, 4, ..., etc.
   X = Numerical argument string for which we seek the Nth root

   NumDecimals = Number of decimals at which to round off the result
                 if exact resolution is not possible.
   ERRORS:
   NO special error checking is done.
   ------------------------------------------------------------------
*/

   function bcNth_Root_Of_X ($N, $X, $NumDecimals=16)
{
   $a = sprintf("%1.16f", pow($X, 1/$N)); // Compute first approximation
   $n = $N - 1;
   $d = $NumDecimals;
   $D = $d + 8; // Add 8 extra decimals precision as rounding fuzz buffer

// Initialize iteration control loop.  The limit is set to 100 to prevent 
// an infinite loop lockup, which would hang the function.  This limit
// should be far more than sufficient and never likely to be reached.
   for ($i=1;  $i <= 100;   $i++)
  {
// Compute next generation approximation to Nth root of X from current (a).
   $b = bcdiv(bcadd(bcmul($n,$a,$D), bcdiv($X, bcpow($a,$n,$D),$D),$D),$N,$D);

// If (a == b) to desired precision, then done, (b) is root.
// Else current (b) becomes the new (a) for the next cycle.
   if (bccomp($a,$b,$D) == 0) {break;} else {$a = $b;}
  }
// Round off root to (d) decimals, then trim redundant zeros and/or decimal.  
   return rtrim(rtrim(bcadd($b, "0." . str_repeat(0,$d) . "5", $d), "0"), ".");
}


Below is a program demonstrating the function followed by the full PHP source code.

Given:
N = 8 = Root
X = '8874232865188808'
Decimals = 69

Y = 8/Root of X  rounded to 69 decimals =
98.518173736814174322651035564345354158737206615390495889277543071810938

 Orig X = 8874232865188808     
Check X = 8874232865188808.000000000000000000000000000000000000000000000000000000253505175082131
      Y = 98.518173736814174322651035564345354158737206615390495889277543071810938
  Error = 0.000000000000000000000000000000000000000000000000000000253505175082131

<?php

// Generate random example values.

$N = mt_rand(2, 20);
$X = bcmul(mt_rand(), mt_rand());
$decimals = mt_rand(10, 112);
  
$Y = bcNth_Root_Of_X($N, $X, $decimals);

$CheckX = bcPoW($Y, $N, $decimals);
$CheckXminusX = bcsub($CheckX, $X, $decimals);
   
print
"<pre>
Given:
N = $N = Root
X = &#39;$X&#39;
Decimals = $decimals

Y = $N/Root of X  rounded to $decimals decimals =
$Y

 Orig X = $X     
Check X = $CheckX
      Y = $Y
  Error = $CheckXminusX
</pre>";   
 



   function bcNth_Root_Of_X ($N, $X, $NumDecimals=16)
{
   $a = sprintf("%1.16f", pow($X, 1/$N)); // Compute first approximation
   $n = $N - 1;
   $d = $NumDecimals;
   $D = $d + 8;

   for ($i=1;  $i <= 100;   $i++)
  {
   $b = bcdiv(bcadd(bcmul($n,$a,$D),bcdiv($X, bcpow($a,$n,$D),$D),$D),$N,$D);

   if (bccomp($a,$b,$D) == 0) {break;} else {$a = $b;}
  }
   return rtrim(rtrim(bcadd($b, "0." . str_repeat(0,$d) . "5", $d), "0"), ".");
}


?>
nth_root_of_x.1396936565.txt.gz · Last modified: 2015/06/22 23:47 (external edit)