# Performance of Large BigInteger square root and cube root functions, and excessively large array

This is a continuation of this: Performance of BigInteger square root and cube root functions in Java

I've made most of the changes suggested, but since I'm loading literally the largest array possible on the computer, I'd like some review before I implement Sieve of Atkin.

Code follows, just over 300 lines, formatted by Netbeans ALT-SHIFT-F function.

package pfactor;

import java.io.File;
import java.io.IOException;
import java.math.BigInteger;
import java.util.ArrayList;
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");
static int[] arrayData;
static BigInteger pArray;

public static void main(String[] args) {
abbrev = ask("Do you want to abbreviate numbers? ");
try {
number = new BigInteger(getFile());
} catch (IOException ex) {
}
System.out.println("Factoring: \n\n" + abbreviate(number));
sqrt = sqrt(number);
System.out.println("The square root is: " + abbreviate(sqrt));
BigInteger testNum = sqrt.multiply(sqrt);
System.out.println("Difference: " + abbreviate(number.subtract(testNum).abs()));
System.out.println("Check returns: " + checksqrt());
cbrt = cbrt(number);
testNum = cbrt.multiply(cbrt).multiply(cbrt);
System.out.println("The cube root is: " + abbreviate(cbrt));
System.out.println("Difference: " + abbreviate(number.subtract(testNum).abs()));
System.out.println("Check returns: " + checksqrt());
testNum = sqrt.subtract(cbrt);
System.out.println("Search size: " + abbreviate(testNum));
arrayData = getLargestArray();
System.out.println("Prime stats determined at " + arrayData[0] + " dimension(s) of size(s) " + getArrayData());
System.out.println(FreeRAM() + " of RAM remaining.");
System.out.println("Beginning prime load...\tExpect heavy RAM/CPU usage.");
IntializeArray();
System.out.println(FreeRAM() + " of RAM remaining.");

}

public static String getFile() throws IOException {
Scanner scanner = new Scanner(new File("Number.dat"));
StringBuilder content = new StringBuilder();
while (scanner.hasNextLine()) {
content.append(scanner.nextLine());
}
return content.toString();
}

public static BigInteger sqrt(BigInteger n) {
BigInteger guess = n.divide(BigInteger.valueOf((long) n.bitLength() / 2));
boolean go = true;
int c = 0;
BigInteger test = guess;
while (go) {
BigInteger numOne = guess.divide(TWO);
BigInteger numTwo = n.divide(guess.multiply(TWO));
if (numOne.equals(numTwo)) {
go = false;
}
if (guess.mod(TWO).equals(BigInteger.ONE)) {
}
//System.out.println(guess.toString());
c++;
c %= 5;
if (c == 4 && (test.equals(guess))) {
return guess;
}
if (c == 2) {
test = guess;
}
}

if ((guess.multiply(guess)).equals(number)) {
return guess;
}

}

public static BigInteger cbrt(BigInteger n) {
BigInteger guess = n.divide(BigInteger.valueOf((long) n.bitLength() / 3));
boolean go = true;
int c = 0;
BigInteger test = guess;
while (go) {
BigInteger numOne = n.divide(guess.multiply(guess));
BigInteger numTwo = guess.multiply(TWO);
if (numOne.equals(numTwo)) {
go = false;
}
if (guess.mod(TWO).equals(BigInteger.ONE)) {
}
//System.out.println(guess.toString());
c++;
c %= 5;
if (c == 4 && (test.equals(guess))) {
return guess;
}
if (c == 2) {
test = guess;
}
if (c == 3) {
}
}

if ((guess.multiply(guess)).equals(number)) {
return guess;
}

}

public static int[] getLargestArray() {
ArrayList<Object> test = new ArrayList<Object>();
int x = 1, y = 1, z = 1, a = 1, b = 1;
int scale = 100000;
int d = 1;
boolean go = true;
while (go) {
try {
switch (d) {

case 1:
x += scale;
break;
case 2:

y += scale;
break;

case 3:
z += scale;
break;
case 4:
a += scale;
break;
case 5:
b += scale;
break;
default:

}
if (x == Integer.MAX_VALUE) {
d++;
}
if (y == Integer.MAX_VALUE) {
d++;
}
if (z == Integer.MAX_VALUE) {
d++;
}
if (a == Integer.MAX_VALUE) {
d++;
}
if (b == Integer.MAX_VALUE) {
d++;
}
test.clear();
} catch (OutOfMemoryError e) {
scale %= 10;
//System.out.println(d + " " + scale + " " + x);
} catch (Exception e) {
e.printStackTrace();
}
if (scale == 0) {
go = false;
}
}
int[] results = new int[6];
results[0] = d;
results[1] = x;
results[2] = y;
results[3] = z;
results[4] = a;
results[5] = b;
return results;
}

public static boolean checksqrt() {
if ((sqrt.multiply(sqrt)).equals(number)) {
return true;
}
BigInteger margin = number.subtract((sqrt.multiply(sqrt))).abs();
BigInteger maxError = (sqrt.subtract(BigInteger.ONE)).multiply(TWO);
if (margin.compareTo(maxError) == -1) {
return true;
}
return false;

}

public static boolean checkcbrt() {
if ((cbrt.multiply(cbrt).multiply(cbrt)).equals(number)) {
return true;
}
BigInteger margin = number.subtract((cbrt.multiply(cbrt).multiply(cbrt))).abs();
BigInteger c = cbrt.subtract(BigInteger.ONE);
if (margin.compareTo(maxError) == -1) {
return true;
}
return false;

}

public static String abbreviate(BigInteger n) {
if (n.toString().length() < 7) {
return n.toString();
}
if (abbrev) {
return n.toString().substring(0, 3) + "..." + n.mod(new BigInteger("1000")) + "(" + n.toString().length() + " digits)";
}
return n.toString();
}

public static boolean ask(String prompt) {
Scanner s = new Scanner(System.in);
System.out.println(prompt + "(Y/N)");
String input = s.nextLine();
char c;
if (input.length() != 0) {
c = input.charAt(0);
} else {
}
if (c == 'N' || c == 'n') {
return false;
}
if (c == 'Y' || c == 'y') {
return true;
}
}

public static String getArrayData() {
String result = "";
for (int i = 0; i < arrayData[0]; i++) {
result = result += arrayData[i + 1] + ",";
}
return result.substring(0, result.length() - 2);
}

public static String FreeRAM() {
long bytes = Runtime.getRuntime().freeMemory();
if (bytes > 1073741823) {
return String.format("%.4f GB", (bytes / 1073741824.0));
}
if (bytes > 1048575) {
return String.format("%.4f MB", (bytes / 1048576.0));
}
if (bytes > 1023) {
return String.format("%.4f KB", (bytes / 1024.0));
}
return bytes + " bytes";
}

public static void IntializeArray() {
switch (arrayData[0]) {

case 1:
break;
case 2:
break;
case 3:
break;
case 4:
break;
case 5:
break;
default:

}
//Figure out way to assign n-dimensional array to a static object
}

System.out.println(FreeRAM());
System.out.println("Number of cores: " + Runtime.getRuntime().availableProcessors());
}

}


This is only a form/style review and not algorithm review, as I don't really know what some of your algorithms are supposed to do. There are some changes that I would do in your code.

The first one would be replace the while loops for do while loops, and get rid of the flag go. In case of sqrt this would be something like:

do{
BigInteger numOne = guess.divide(TWO);
BigInteger numTwo = n.divide(guess.multiply(TWO));
if (guess.mod(TWO).equals(BigInteger.ONE)) {
}
//System.out.println(guess.toString());
c++;
c %= 5;
if (c == 4 && test.equals(guess)) {
return guess;
}
if (c == 2) {
test = guess;
}
}while(!numOne.equals(numTwo));


The same goes for cbrt and getLargestArray.

In getLargestArray I would create the result array at the beginning and accumulate the results there. By doing that I could use a for statement and get rid of your 5 ifs. like:

ArrayList<Object> test = new ArrayList<Object>();
int[] results = new int[6]{1,1,1,1,1,1}; //d x y z a b
//map the variables as indexes in results for readability!
int d = 0, x = 1, y = 2, z = 3, a = 4, b = 5;
int scale = 100000;
do {
try {
switch (results[d]) {

case 1:
results[x] += scale;
break;
//other cases...
default:

}
for(int i = x; i < results.lenght; ++i){
//I doubt that this condition will ever be true, and also that this is what you really want to check, but I follow the algorithm as yours
if(results[i] == Integer.MAX_VALUE){
results[d]+=1;
}
}
test.clear();
} catch (OutOfMemoryError e) {
scale %= 10;
//System.out.println(d + " " + scale + " " + x);
} catch (Exception e) {
e.printStackTrace();
}
}while(scale != 0);
return results;


Also take note that a n-dimensional array is just a abstraction for a 1 dimensional contiguous array, and that should be no major differences in your results.

I would also get rid of your magic constants in FreeRam. Write 1024 * 1024 * 1024 instead of 1073741824 etc. If you need that the value produced is a double than you can write 1024.0 * 1024...

• I have a few questions. 1. Where could I get algorithm review? 2. Wouldn't calculating the value instead of constants be slower, especially if i call FreeRAM() multiple times? Commented Jan 17, 2014 at 17:00
• To your first question: Somebody that knows more math than me and also have a bit understanding of programming, that may be a user of codereview that are willing to contribute with an answer. To your second question: Actually no, the compiler can evaluate the result of 1024 * 1024 (since it is a constant arithmetic expression) at compile time so it doesn't need to be evaluated at run time. Commented Jan 17, 2014 at 17:15
• If you do not want to rely on the compiler then you can declare some constants in your class with that values, so the expression is only evaluated one time. example: private static final int MEGA = 1024 * 1024; Commented Jan 17, 2014 at 17:40