3
\$\begingroup\$

I'm working on a program to handle simplifying square roots (radicals). My biggest issue is, in order to stay precise, I can't have input any longer than 15 digits. Whenever a number is longer than 15 digits, it loses precision when converted to double when I try to determine if the square is actually a factor. I realize I can just use an int and call it a day, but I'd really like to be able to use bigger numbers. Is there a better way I can do this to handle numbers longer than 15 digits? Also, any other optimization or readability ideas would be greatly appreciated! This is the best algorithm I could come up with for finding square roots.

import java.util.Scanner;

public class SimpRad
{
    public static final String SQUARE_ROOT_SYMBOL = "\u221A";
    public static final int INPUT_FAILURE = -1;


    static long[] simplify( long square )
    {
        double outside = 1;
        double inside = square;
        long[] simplified = { 1, square };

        // Check if it's already a perfect square
        outside = Math.sqrt(square);
        if (outside == Math.floor(outside))
        {
            simplified[0] = (long)outside;
            simplified[1] = 1;
            return simplified;
        }

        // Find all the squares that could be factors and see if they are
        for (long factor = 2, sqr = 4; sqr <= (square / 2); factor++, sqr = (factor * factor))
        {
            // Is this square a factor?
            double in = (double)square / sqr;
            if (in == Math.floor(in))
            {
                simplified[0] = factor;
                simplified[1] = (long)in;
            }
        }

        // Otherwise, since it hasn't simplified, return the original radical
        return simplified;
    }

    public static String display( long radicand, long multiplier, long newRad, boolean negative )
    {
        String i = negative ? "i" : "";
        String negativeStr = negative ? "-" : "";


        // If it's already simplified
        if (multiplier == 1)
        {
            return (SQUARE_ROOT_SYMBOL + negativeStr + radicand + " = " + i
                        + SQUARE_ROOT_SYMBOL + newRad);
        }
        // If it's a perfect square
        else if (newRad == 1)
        {
            return (SQUARE_ROOT_SYMBOL + negativeStr + radicand + " = " + multiplier + i);
        }
        else
        {
            return (SQUARE_ROOT_SYMBOL + negativeStr + radicand + " = " + multiplier + i
                        + SQUARE_ROOT_SYMBOL + newRad);
        }
    }



    public static void main( String[] args )
    {
        Scanner userInput = new Scanner(System.in);
        long radicand;
        long[] rads;
        String radStr;
        boolean isNegative = false;

        do
        {
            System.out.print("Please enter the current radicand:  ");
            radStr = userInput.next();

            try {
                radicand = Long.parseLong(radStr);
            } catch (NumberFormatException e) {
                System.out.print("That's not an integer! ");
                radicand = INPUT_FAILURE;
                continue;
            }

            if (radicand < 0)
            {
                radicand = -radicand;
                isNegative = true;
            }

            if (radicand > 999999999999999l)
            {
                System.out.print("Please enter a radicand that is 15 digits or less. ");
                radicand = INPUT_FAILURE;
            }
        } while (radicand < 0);

        rads = simplify(radicand);
        System.out.println(display(radicand, rads[0], rads[1], isNegative));
    }
}
\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

Better approach

First, if you got rid of all floating point and just use long, that would fix your inaccuracy problems.

Second, your loop is trying to find the greatest factor of the number that is a square. But for a large number it will run for a long time because you check every number up to \$\sqrt n\$. You can shorten the time by dividing any factors you find along the way. For example, if 2 divides into \$n\$ 7 times, then \$2^3\$ can be factored out of the square root and \$2\$ will remain under the radical. I.e.:

If: \$n = 2^7 * m\$
\$\sqrt n = 2^3 \sqrt {2 * m}\$

If a factor divides an even number of times into your number, then it can be pulled out without leaving anything under the radical.

After you simplify for each factor, you keep going to find factors of \$m\$, which is smaller, so you only need to check factors up to \$\sqrt m\$. You just need to keep track of the internal and external factors as you go.

In the worst case (if the number is prime), it will still take the same amount of time. You could research factorization algorithms if you want something better.

\$\endgroup\$
6
  • \$\begingroup\$ First, if you got rid of all floating point: Wouldn't that result in even less precision when I divide factors since then it would lose any floating precision at all? Is there a solution to do this without division at all? If not, I do love your idea about taking out the factors as I go, although that definitely still requires division, which would require double. \$\endgroup\$
    – BrainFRZ
    Sep 30, 2015 at 23:53
  • \$\begingroup\$ @TerryWeiss Why can't you divide a long with a long? Or better yet use the modulo operator? If you are looking for a factor, if (n % factor == 0) tells you if factor divides perfectly into n. \$\endgroup\$
    – JS1
    Oct 1, 2015 at 1:54
  • \$\begingroup\$ If I divide by a long, 4 / 3 == 1 just like 5 / 3 == 1. Or 15 / 4 == 15 / 5. There are an enormous number of instances just like these where that kind of loss of precision would be devastating to the algorithm. That's why I used division and compared to the quotient's floor to make sure it's truly an even factor and not just an even factor because of being rounded. (This is also why with my current algorithm I can't safely use anything longer than 15 digits with double.) Also my same process would be necessary to implement your idea of pulling out factors as I go, wouldn't it? \$\endgroup\$
    – BrainFRZ
    Oct 1, 2015 at 2:08
  • 1
    \$\begingroup\$ in = square / sqr; if (in * sqr == square) { ... }. Or use the modulo operator as mentioned in my previous comment, i.e. if (square % sqr == 0) { ... } \$\endgroup\$
    – JS1
    Oct 1, 2015 at 3:02
  • 1
    \$\begingroup\$ @TerryWeiss A double has 53 bits of precision. A long has 63 bits of precision. This is why your 18 digit numbers don't convert properly. If you leave everything as a long, you don't lose precision. \$\endgroup\$
    – JS1
    Oct 3, 2015 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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