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

In summary: These operations can be used to perform fancy computations that are difficult to do in most other programming languages used on the WWW. However, for higher roots such as the cube root or sixth root, a custom function must be created using the basic operations. The resulting value of the next approximation can be substituted as the new value and the process is repeated until the desired level of precision is reached. This is based on Newton's method for finding roots.
  • #1
Jay1
14
0
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:)
 
Last edited:
Mathematics news on Phys.org
  • #2
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
 

Similar threads

MHB Computing The Arbitrary-Precision Value Of N-Factorial In PHP
Replies
1
Views
2K
MHB Polynomial with five roots: determine the roots of the equation x^5+ax^4+bx^3+cx^2+dx+e=0 as functions of a,d and e
Replies
1
Views
1K
MHB Program for Approximating nth root of a Number
Replies
4
Views
3K
MHB A PHP Function To Perform Nth-Order Lagrange Interpolation
Replies
1
Views
4K
How are recurrence relations used in mathematics and computer science?
Replies
1
Views
2K
MHB Implementation of numerical method
Replies
1
Views
2K
MHB My methods for solving the July 8, 2013 High School POTW
Replies
4
Views
2K
MATLAB What is the process for finding nth roots of a matrix in MATLAB?
Replies
11
Views
11K
If f(x+y)=f(x)+f(y) and f(x.y)=f(x)f(y) then f(x)=x , x in R
Replies
9
Views
7K
I On the approximate solution obtained through Euler's method
Replies
1
Views
2K

Hot Threads

Recent Insights

Back
Top