MHB Computing The Arbitrary-Precision Nth Root Of Positive (X) In PHP

Jay1 · Aug 22, 2014

PHP has some powerful arbitrary-precision (BC or binary calculator) arithmetic functions which seem to be greatly underused and only consist of the basic arithmetic operations, a square root function, a mod function and an integer power function.

However, those basic operations can be used to perform some very fancy computations much harder to do in most other languages used on the WWW.

There is an arbitrary-precision square root function, but what if we wanted the arbitrary-precision cube root or sixth root, etc.?

For roots higher than the square root, we have to create a custom function built from the basic operations.

Given:
a = Current approximation to Nth root of (x)
N = Root for which to solve (2,3,4 ...)
x = Argument for which to find the Nth root
b = Next generation approximation derived from current generation (a)

Given any initial starting approximation (a) to the Nth root of (x),
the next approximation (b) may be computed by the general formula:

$$b = \frac{\frac{x}{a^{N-1}} + a\cdot(N-1)}{N}$$

The resulting value of (b) is then substituted as the new value of (a) and the process is repeated, each time giving a closer and closer approximation (b) of the Nth root of (x) until it reaches whatever level of precision (decimals) we require.

Below is an arbitrary-precision PHP function designed to compute the Nth root of positive argument (x) to any given number of decimals based on the above recursion formula.

The argument (x) should be given in the form of a numerical string, such as "12.345"

Code:

   function bcNth_Root_Of_x ($N, $x, $NumDecimals=16)
{
   $a = sprintf("%1.16f", pow($x, 1/$N));
   $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"), ".");
}

EXAMPLE:
Below is a small, ready-to-run PHP example program calling the function to compute the 5th root of 100, rounded to 75 decimals.

Code:

<?php

$N = 5;
$x = "100";
$decimals = 75;

print bcNth_Root_Of_x ($N, $x, $decimals);

// ------------------------------------------------

 function bcNth_Root_Of_x ($N, $x, $NumDecimals=16)
{
 $a = sprintf("%1.16f", pow($x, 1/$N));
 $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"), ".");
}

?>

The returned result should be:

Code:

2.511886431509580111085032067799327394158518100782475428679888420908243247724

Here is a commented listing of the above function.

Code:

/*
   ------------------------------------------------------------------
   This function computes the arbitrary-precision Nth root of a given
   numerical string (x), rounded at 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)
{
// Compute first seed approximation.
   $a = sprintf("%1.16f", pow($x, 1/$N));
   $n = $N - 1;
   $d = $NumDecimals;

// Add 8 extra decimals precision as rounding fuzz buffer
   $D = $d + 8;

// 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 (b) to Nth root of (x) from the
// current generation approximation (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"), ".");
}

If you happen to be a PHP math coder, like me, this Nth root function could be part of a library of custom arbitrary-precision PHP math functions.

Some example test values are:

Code:

Cube (3) root of 10 to 32 decimals:
= 2.15443469003188372175929356651935

7th root of 18435.57209 to 50 decimals:
= 4.0679866312376590401866108430333983477514

4th root of 4646545.65686847759871677987 to 80 decimals:
= 46.42827543473103234672521339464313742938263307554617373866851061590663732382853491

etc.

Cheers and tally-ho

P.S.
The formula given above is based on Newton's method for finding roots.

Ref:
https://en.wikipedia.org/wiki/Newton's_method:)

kienvannguyen · Nov 29, 2014

Jay said:
PHP has some powerful arbitrary-precision (BC or binary calculator) arithmetic functions which seem to be greatly underused and only consist of the basic arithmetic operations, a square root function, a mod function and an integer power function.

However, those basic operations can be used to perform some very fancy computations much harder to do in most other languages used on the WWW.

There is an arbitrary-precision square root function, but what if we wanted the arbitrary-precision cube root or sixth root, etc.?

For roots higher than the square root, we have to create a custom function built from the basic operations.

Given:
a = Current approximation to Nth root of (x)
N = Root for which to solve (2,3,4 ...)
x = Argument for which to find the Nth root
b = Next generation approximation derived from current generation (a)

Given any initial starting approximation (a) to the Nth root of (x),
the next approximation (b) may be computed by the general formula:

$$b = \frac{\frac{x}{a^{N-1}} + a\cdot(N-1)}{N}$$

The resulting value of (b) is then substituted as the new value of (a) and the process is repeated, each time giving a closer and closer approximation (b) of the Nth root of (x) until it reaches whatever level of precision (decimals) we require.

Below is an arbitrary-precision PHP function designed to compute the Nth root of positive argument (x) to any given number of decimals based on the above recursion formula.

The argument (x) should be given in the form of a numerical string, such as "12.345"
Code:
   function bcNth_Root_Of_x ($N, $x, $NumDecimals=16)
{
   $a = sprintf("%1.16f", pow($x, 1/$N));
   $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"), ".");
}
EXAMPLE:
Below is a small, ready-to-run PHP example program calling the function to compute the 5th root of 100, rounded to 75 decimals.
Code:
<?php

$N = 5;
$x = "100";
$decimals = 75;

print bcNth_Root_Of_x ($N, $x, $decimals);

// ------------------------------------------------

 function bcNth_Root_Of_x ($N, $x, $NumDecimals=16)
{
 $a = sprintf("%1.16f", pow($x, 1/$N));
 $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"), ".");
}

?>
The returned result should be:
Code:
2.511886431509580111085032067799327394158518100782475428679888420908243247724
Here is a commented listing of the above function.
Code:
/*
   ------------------------------------------------------------------
   This function computes the arbitrary-precision Nth root of a given
   numerical string (x), rounded at 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)
{
// Compute first seed approximation.
   $a = sprintf("%1.16f", pow($x, 1/$N));
   $n = $N - 1;
   $d = $NumDecimals;

// Add 8 extra decimals precision as rounding fuzz buffer
   $D = $d + 8;

// 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 (b) to Nth root of (x) from the
// current generation approximation (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"), ".");
}
If you happen to be a PHP math coder, like me, this Nth root function could be part of a library of custom arbitrary-precision PHP math functions.

Some example test values are:
Code:
Cube (3) root of 10 to 32 decimals:
= 2.15443469003188372175929356651935

7th root of 18435.57209 to 50 decimals:
= 4.0679866312376590401866108430333983477514

4th root of 4646545.65686847759871677987 to 80 decimals:
= 46.42827543473103234672521339464313742938263307554617373866851061590663732382853491

etc.
Cheers and tally-ho

P.S.
The formula given above is based on Newton's method for finding roots.

Ref:
https://en.wikipedia.org/wiki/Newton's_method:)

please help me code C# with algorthrm this

MHB Computing The Arbitrary-Precision Nth Root Of Positive (X) In PHP

Thread 'What Exactly is Dirac’s Delta Function? - Insight'

Thread 'Fermat's Last Theorem'

Thread 'Useless continued fraction for 1'

Similar threads

Hot Threads

Insights Why Vector Spaces Explain The World: A Historical Perspective

Insights Fermat's Last Theorem

B How is it that law of sines does not work in this exercise?

B What could prove this wrong? I'm having a dispute with friends

B About a definition: What is the number of terms of a polynomial P(x)?

Recent Insights

Insights Quantum Entanglement is a Kinematic Fact, not a Dynamical Effect

Insights What Exactly is Dirac’s Delta Function? - Insight

Insights Relativator (Circular Slide-Rule): Simulated with Desmos - Insight

Insights Fixing Things Which Can Go Wrong With Complex Numbers

Insights Fermat's Last Theorem

Insights Why Vector Spaces Explain The World: A Historical Perspective