Performance of BigInteger square root and cube root functions in Java

I am writing a program to factor stupidly large integers (5000 digits+), and performance is obviously critical. A currently TODO feature is to factor semiprimes, specifically RSA, which is why the cube root function is included. Don't tell me it's impossible. I'm trying to learn, not actually do it. Before I start on the actual factorization, I would love review on the current program. I'm not 100% on the check methods, and any help on general performance would be helpful.

```
package pfactor;

import java.io.File;
import java.math.BigInteger;
import java.util.Scanner;

public class Factor {

static BigInteger number;
static BigInteger sqrt;
static BigInteger cbrt;
static boolean abbrev;
static final BigInteger TWO = new BigInteger("2");
static final BigInteger THREE = new BigInteger("3");

public static void main(String[] args) throws Exception {
System.out.println("Abbreviate Numbers?");
abbrev = ask("Do you want to abbreviate numbers? ");
number = new BigInteger(getFile());
System.out.println("Factoring: \n\n" + abbreviate(number));
sqrt = sqrt(number);
System.out.println("The square root is: " + abbreviate(sqrt));
System.out.println("Difference: " + abbreviate(number.subtract((sqrt.multiply(sqrt))).abs()));
System.out.println("Check returns: " + checksqrt());
cbrt = cbrt(number);
System.out.println("The cube root is: " + abbreviate(cbrt));
System.out.println("Difference: " + abbreviate(number.subtract((cbrt.multiply(cbrt).multiply(cbrt))).abs()));
System.out.println("Check returns: " + checksqrt());
}

public static String getFile() throws Exception {
Scanner s = new Scanner(new File("Number.dat"));
String i = "";
while (s.hasNextLine()) {
i = i + s.nextLine();
}
return i;
}

public static BigInteger sqrt(BigInteger n) {
BigInteger guess = n.divide(BigInteger.valu

The following review is about the style only, I'll leave the review of the functionality to somebody who can actually do the math.

package pfactor;

Package names should associate the package with a person or organization. For testing code it is okay to omit it, but if you ever release code "into the wild" or onto a production system, the package name should be in the format:

package com.mycompany.mypackage;
package com.gmail.username.mypackage;
package com.github.username.mypackage;

static BigInteger number;

Static variables that get modified? That's bad...refactor all your code into an instance-class or get rid of those (static) variables. Using static variables that get modified only begs for trouble, thread-safety is only one of the issues.

public static void main(String[] args) throws Exception {

This is evil, your main method should never throw exceptions, and especially not Exception, it's the "I really just don't care and can't be bothered" of error handling.

Handle exceptions in the main method and fail gracefully.

public static String getFile() throws Exception {

Okay, here goes rule number 1 for error handling:

Never, ever, for whatever reason...and let me get this straight, there is no reason, never, absolutely never, ever, you can't come up with one, to throws Exception.

Handle exceptions where you need to handle them, rethrow or wrap them. Or at the least declare the exceptions explicitly thrown by the method.

Why is this so important? Imagine that you wrote a library with some useful functions which only declare throws Exception. How is the client supposed to handle specific error conditions? Testing the exception for a certain instance of a class? Parsing the error message? How does the client know that all exceptional cases are handled? How can the client guarantee that the code relying on your functions does not break? The answer is, not at all...and that's unacceptable.

Scanner s = new Scanner(new File("Number.dat"));

You're only entitled to use one-letter-variable names in two situations:

• for loops (i, j, k)

• Dimensions (x, y, z)

There is not a single reason to not use a fully understandable name for your variables. So, whenever you want to use a single letter as a variable name, stop, think by yourself "what does this variable hold" and then you name it according to it.

Scanner scanner = new Scanner(new File("Number.dat"));
String content = "";
while (scanner.hasNextLine()) {
    content = content + scanner.nextLine();
}
return content;

You can now start reading in the middle of the function and you still know what's going on. Overall, most of your variables need better naming.

String i = "";

This is pure evil. i is traditionally only used for for counters.

i = i + s.nextLine();

The + operator for concatenating strings is a very bad choice. Under the hood the folllowing happens:

• Get String A

• Get String B

• Allocate new memory (C) in the size of A + B

• Copy A into C

• Copy B into C

• Override A with C

This is slow. You should use a StringBuilder instead, like this:

StringBuilder content - new StringBuilder();
content.append(line);
return content.toString();

This performs roughly these operations under the hood:

• Allocate some more memory

• Copy B into that memory

The speed difference between Strings + and StringBuilder is extreme, in a tight loop with many iterations, + might take 5 minutes, StringBuilder will be done in less then 30ms.

//Factor method TODO, does nothing, never called

That's not true, it does return an empty int array. Either remove it or make sure that it can not be called.

if (abbrev)
return n.toString()

That's badly formatted, you should always use braces, even for one-line ifs.

if (abbrev) {
    return n.toString();
}

StackExchange Code Review Q#39197, answer score: 2