current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 5 down vote favorite

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.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));
            guess = numOne.add(numTwo);
            if (numOne.equals(numTwo)) {
                go = false;
            }
            if (guess.mod(TWO).equals(BigInteger.ONE)) {
                guess = guess.add(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;
        }
        return guess.add(BigInteger.ONE);
    }

    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);
            guess = numOne.add(numTwo).divide(THREE);
            if (numOne.equals(numTwo)) {
                go = false;
            }
            if (guess.mod(TWO).equals(BigInteger.ONE)) {
                guess = guess.add(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;
        }
        return guess.add(BigInteger.ONE);
    }

    public static int[] fac() {
        //Factor method TODO, does nothing, never called
        return new int[5];
    }

    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);
        BigInteger maxError = ((c.multiply(c)).multiply(THREE)).add(c.multiply(THREE));
        if (margin.compareTo(maxError) == -1) {
            return true;
        }
        return false;
    }

    public static String abbreviate(BigInteger n) {
        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)");
        char c = s.nextLine().charAt(0);
        if (c == 'N' || c == 'n') {
            return false;
        }
        if (c == 'Y' || c == 'y') {
            return true;
        }
        return ask("");
    }
}
share|improve this question

1 Answer 1

up vote 1 down vote

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();
}
share|improve this answer
    
Why is the removal of static necessary, I'm confused, and removing it breaks the code. I know I could probably fix it by writing a second class, but I'm concerned with the possibility of performance degradation. –  David Green Jan 14 '14 at 16:28
    
It is basically a global variable that gets altered at a whim, multi-threading will yield obscure results and maintainability is not that good either. If you write static methods, they should be self-contained or it should be clear why they need some sort of static variable to save their state. Additionally testing of these methods is complex at best. It would be best to refactor your methods so that they can stand on their own, or if you need to keep something, make it an instance. –  Bobby Jan 14 '14 at 20:18
    
Well, all those variables are only written to once, but read many times in many methods across (possibly) multiple classes. Wouldn't that be what static is for? I read the link and my statics are 1: Needed for the entire length of the program, and 2: (I think) are thread safe, since they will only need to be read by later calls. –  David Green Jan 14 '14 at 22:50
    
@DavidGreen Static variables are practically always wrong (constants are fine). How to ged rid of them: 1. Remove all static modifiers. 2. Rename main to something else, e.g., go. 3. Write a trivial main creating an instance and calling go on it. 4. Be assured that this can't influence the performance. –  maaartinus Jun 14 '14 at 23:26
1  
@Bobby Agreed, there should be usually a separated class for main doing the boring things. But this is the next step after getting rid of static. And wrapping the whole process in a static method is fine, too (unless you need more flexibility later). –  maaartinus Jun 15 '14 at 17:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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