Just for practice in the mathematical side of programming, I decided to rewrite the math functions, with the addition of the root()
function, which the Math library does not provide, but can be easily done with Math.pow(x, 1 / y)
where you want to find out x
to the y
th root.
I also wrote this to review the Newton's Method, which works like this:
Given an approximate \$x\$-intercept \$x_n\$, a better estimate \$x_{n+1}\$ is calculated with the following:
$$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$$
Where \$f(x)\$ is the function to find the \$x\$-intercept, and \$f'(x)\$ is the derivative.
In the case of roots, to find \$\sqrt[z]y\$, \$f(x) = {x_n}^z - y\$, and \$f'(x) = zx^{z-1}\$, resulting in:
$$x_{n+1}=x_n-\frac{{x_n}^z - y}{z{x_n}^{z-1}}$$
public class MathUtils {
/**
* <p>
* Returns the given root of the given number.
* </p>
*
* <p>
* Assuming <code>n</code> is the first argument, and <code>m</code> is the
* second argument, the result is <code>n</code> to the <code>m</code>th
* root.
* </p>
*
* @param number
* the number
* @param root
* the root
* @return the result
*
* @see #root(double, long)
*/
public static double root(double number, double root) {
return pow(number, 1 / root);
}
/**
* <p>
* Returns the given root, which is an integer, of the given number.
* </p>
*
* <p>
* This method is very similar to the {@link MathExt#root(double, double)}
* method, but with optimization improvements as the algorithm is different.
* </p>
*
* @param number
* the number
* @param root
* the root
* @return the result
*
* @see #root(double, double)
*/
public static double root(double number, long root) {
double approx = 1;
// x2 = x1 - fx1 / f'x1
// fx1 = x^n - y
// f'x1 = n * x ^ (n - 1)
for (int i = 0; i < 1000; i++) {
approx = approx - (pow(approx, root) - number) / (root * pow(approx,
root - 1));
}
return approx;
}
/**
* <p>
* Returns the given power of the given number.
* </p>
*
* <p>
* Assuming <code>n</code> is the first argument, and <code>m</code> is the
* second argument, the result is <code>n ^ m</code>.
* </p>
*
* @param number
* the number
* @param exponent
* the power
* @return the result
*
* @see #pow(double, long)
*/
public static double pow(double number, double exponent) {
String temp = Double.toString(exponent).split("\\.")[1];
long denominator = (long) pow(10, temp.length());
long numerator = Long.parseLong(temp) + floor(exponent) * denominator;
long GCF = getGCF(numerator, denominator);
numerator /= GCF;
denominator /= GCF;
return pow(root(number, denominator), numerator);
}
/**
* <p>
* Returns the given power, as an integer, of the given number.
* </p>
*
* <p>
* This method is very similar to the {@link MathExt#root(double, double)}
* method, but with optimization improvements as the algorithm is different.
* </p>
*
* @param number
* the number
* @param exponent
* the power
* @return the result
*
* @see #pow(double, long)
*/
public static double pow(double number, long exponent) {
double result = number;
for (; exponent > 1; exponent--) {
result *= number;
}
return result;
}
/**
* Gets the GCF (Greatest Common Factor, or Greatest Common Divisor) of the
* given numbers.
*
* @param nums
* the numbers
* @return the GCF of the given numbers
*/
public static long getGCF(long... nums) {
if (nums.length == 0) {
// TODO except
}
long result = nums[0];
for (int i = 1; i < nums.length; i++) {
result = getGCFOfTwoNumbers(result, nums[i]);
}
return result;
}
private static long getGCFOfTwoNumbers(long num1, long num2) {
for (long result; num2 != 0;) {
result = num1 % num2;
num1 = num2;
num2 = result;
if (num1 == 1 || num2 == 1) {
return 1;
}
}
return num1;
}
/**
* Gets the LCM (Least Common Multiple) of the given numbers.
*
* @param nums
* the numbers
* @return the LCM of the given numbers
*/
public static long getLCM(long... nums) {
if (nums.length == 0) {
// TODO except
}
long result = nums[0];
for (int i = 1; i < nums.length; i++) {
result *= nums[i];
}
return result / getGCF(nums);
}
/**
* Rounds down from the given number.
*
* @param number
* the number to round down
* @return the result of rounding down
*/
public static long floor(double number) {
if (number >= 0 || number % 1 == 0) {
return (long) number;
}
return (long) number - 1;
}
/**
* Rounds up from the given number.
*
* @param number
* the number to round up
* @return the result of rounding down
*/
public static long ceil(double number) {
if (number >= 0 || number % 1 == 0) {
return (long) number + 1;
}
return (long) number;
}
/**
* Rounds to the nearest integer.
*
* @param number
* the number to round
* @return the result of rounding
*/
public static long round(double number) {
return (long) (number + 0.5);
}
}
Concerns:
Is my math efficient? Now, I got this formula to specifically calculate roots here:
Here is one approximation method (called Newton's Method) for finding the nth root of a number y:
$$x_2 = x_1 * (1-1/n) + y/n/{x_1}^{n-1}$$
But it didn't work, so I did it on my own, ending up with:
$$x_{n+1}=x_n-\frac{{x_n}^z - y}{z{x_n}^{z-1}}$$
My guess is that either I got it wrong, or the person writing the formula made a mistake in simplifying.
Is my JavaDoc good? I feel like it has some redundant or missing information there...