User Tools

Site Tools


nth_root_of_x

This is an old revision of the document!


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. 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 normal floating point value.

A general-purpose root computation function is 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 = 2 = Root
X = '1718335380956183169'
Decimals = 80

Y = 2/Root of X  rounded to 80 decimals =
1310852921.17620242537070743777725475116776972173354816187302409449122169111586097662309485

 Orig X = 1718335380956183169     
Check X = 1718335380956183168.99999999999999999999999999999999999999999999999999999999999999999999999949220499
      Y = 1310852921.17620242537070743777725475116776972173354816187302409449122169111586097662309485
  Error = -0.00000000000000000000000000000000000000000000000000000000000000000000000050779501

<?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.1396324079.txt.gz · Last modified: 2014/03/31 23:47 by Jay.Tanner.x@PHPScienceLabs.us