10
\$\begingroup\$

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 yth 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:

  1. 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.

  2. Is my JavaDoc good? I feel like it has some redundant or missing information there...

\$\endgroup\$
3
\$\begingroup\$

Make MathUtils final and give it a private constructor. It should be neither extended nor constructed.

Don't use abbreviations in method names.

Your javadoc needs improvement. You do a reasonable job of explaining what methods do when everything is on the happy path, but you don't discuss error conditions or corner cases at all. For instance, compare your ceil() javadoc to the javadoc for Math#ceil(). Double.MAX_VALUE is significantly larger than Long.MAX_VALUE. The best way to fix it is think of every corner case you can, add unit tests for all of them, and then document what happens. If you don't like what happens, adjust your test to the behaviour you want, document that, and then fix the code to return it. Repeat that for every method you have. Then find a buddy and ask them to read the docs only and tell you what corner cases you didn't mention.

\$\endgroup\$
2
\$\begingroup\$

Slow pow function

Your pow(double, long) function is \$O(n)\$ on the exponent. This means that given a very large exponent, your program will never finish. You should use an exponentiation by squaring algorithm instead. That would make your function take \$O(\log n)\$ time instead.

Negative exponent

Both your pow(double, long) and your pow(double, double) functions do not correctly handle a negative exponent. You could simply test for a negative exponent, flip it to a positive exponent, and then compute \$x^{-n} = 1/x^n\$.

\$\endgroup\$
2
\$\begingroup\$

String should never be used in Numerical code

String is way slower than numeric primitives, each time you create a String you create a full object that should also eventually be garbage collected.

String temp = Double.toString(exponent).split("\\.")[1];

Can be re-written as:

int integerPart = (int) exponent;
double decimalPart = expoenent - integerPart

( Never use temp as a variable name, you mostly have good names, so this was probably just a slip. )

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.